시간복잡도

시간 복잡도란

알고리즘을 수행하기 위해 프로세스가 수행해야하는 연산을 수치화 한 것.

시간 복잡도 분석은 알고리즘 성능의 핵심이다.

프로그램을 비효율적으로 작성하여 시간 제한을 넘기면 '시간 초과'로 오답 처리가 되기 때문이다.

문제의 조건을 파악 후 시간복잡도를 예상해 효율적인 알고리즘을 제시하는 능력이 필요하다.

시간복잡도를 표현할 때는 빅오 표기법을 사용한다.

---

빅오 표기법(Big-O Notation)

 

 

 

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

faster(good) slower(bad)

시간복잡도에서 중요하게 보는것은 가장 큰 영향을 미치는 것은 n(입력값)의 단위로,

왼쪽에서 오른쪽으로 갈수록 성능이 떨어진다.

---

O(1)

 

int a = 4;
int b = 8;

System.out.println(a + b);

단순히 더하기 연산 한 번이 수행되기 때문에 이는 상수 연산이므로 시간 복잡도는 O(1)로 표현할 수 있다.

---

O(logN)

 

이진 탐색을 예로 들 수 있습니다. 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하기 때문에 확인하는 데이터 개수가 절반씩 줄어든다는 점에서 O(logN)로 표현할 수 있다.

---

O(N)

 

int[] array = {3, 5, 2, 1, 4};
int sum = 0;

for(int i = 0; i < array.length; i++) {
   sum += array[i];
}

System.out.println(sum);

위 소스코드와 같이 array가 커짐에 따라 비례하여 연산을 수행하는 루프문 부분이므로 시간 복잡도는 O(N)으로 표현할 수 있다.

---

O(NlogN)

 

합병 정렬, 퀵 정렬을 예로 들 수 있다.

합병정렬의 분할 단계에서 분할되는 깊이가 logN에 비례한다.

각 깊이별로 분할이 수행되어 합병해야 되는 배열의 수는 많아지지만, 총 원소의 수는 똑같다. (N개)

따라서, 각 깊이별로 수행되는 merge의 시간복잡도는 O(N)이 되며, 이것을 모든 깊이에 대하(logN개만큼)

수행하기 때문에 시간 복잡도는 O(NlogN)으로 표현할 수 있다.

---

O(N^2)

 

int[] array = {3, 5, 2, 1, 4};

for(int i = 0; i < array.length; i++) {
   for(int j = 0; j < array.length; j++) {
      System.out.println(a+b);
   }
}

위 소스코드와 같이 array 크기만큼 중첩루프를 사용하여 연산 수행하므로 시간 복잡도는 O(N^2)으로 표현할 수 있다.

---

O(2^N)

 

대표적으로 피보나치 수열을 예로 들 수 있습니다. 재귀가 역기능을 할 경우 해당 대며,

데이터량이 많아질수록 처리시간이 기하급수적으로 증가한다.

---

코딩테스트 활용

우선 대략적으로 n으로 구성된 O() 를 계산했을 때의 값이 1억 정도면 1초 정도의 시간이 걸린다.

*(데이터 크기 = 입력값 범위)

예시:

제한시간 3초 , 범위 100,000 일때

• O(N)의 복잡도: 대략 100,000번의 연산이 필요해서 가능 (3억보다 훨씬 작음)
• O(NlogN)의 복잡도: 100,000×log2100,000 = 100,000×17 = 1,700,000번의 연산이 필요해서 가능(3억보다 훨씬 작음)
• O(N2)의 복잡도: 100,000×100,000 = 10,000,000,000 (100억)번의 연산이 필요해서 불가능 (3억보다 훨씬 큼)

결론:

문제를 볼때 아래 순서대로 우선 확인한다.

1. 제한시간 파악
2. 입력값 범위 파악
3. 어떤 시간 복잡도를 가진 알고리즘을 사용할지 생각하고 로직을 짠다.