시간복잡도 계산법

1. 시간복잡도란?

• 문제를 해결하는데 걸리는 시간과 입력한 함수 관계로, "연산의 횟수(시행 횟수)"를 센다.
• 컴퓨터는 코드를 수행하는데 있어서, 유한한 메모리 자원과 시간을 사용한다.
• 이 때, 메모리를 사용하는 데 평가기준인 공간복잡도(Space Complexity)와 시간을 사용하는 데 평가기준인 시간복잡도(Time Complexity)를 알고리즘 평가 척도로 사용하기도 한다.

2. 중요성

• 요즘의 컴퓨터는 메모리의 성능향상으로 인해 시간복잡도를 더욱 중요시 판단한다고 한다.
• 물론 메모리의 낭비를 계산하는 공간복잡도도 중요한 판단 척도이다.

3. 알고리즘의 성능평가

  1. 최선의 경우 (Best Case, Big-Ω(오메가 표기법, Ω(n))

      - 최적의 입력을 한 상태에서 작업을 완료하는데 가장 빠른 시간이 걸리는 것

  2. 평균의 경우 (Average Case, Big-θ(세타 표기법, θ(n))

      - 여러가지 다른 경우의 수를 입력하여, 평균 실행 시간을 계산한 것

  3. 최악의 경우 (Worst Case, Big-O(빅오 표기법, O(n))

      - 최악의 입력을 한 상태에서 작업을 완료하는데 가장 오랜 시간이 걸리는 것

 

  * 일반적으로 최악의 경우를 통해 알고리즘의 성능을 파악함.

 

4. Big-O 표기법

• O(1) : 상수시간, 입력에 상관없이 일정한 출력 시간
• O(log n) : 입력 n이 증가함에 따라 출력 시간이 커짐
• O(n) : n개의 입력에 대한 n번의 수행 
• O(n log n) : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어드는 것을 말한다. 예: 이진검색
• O(n^2) : 주로 2중 for loop를 사용하여 조합가능한 모든 쌍을 대상으로 하는 경우가 전형적(quadratic)
• O(n^3) : 3차형(cubic)
• O(2^n) : 지수형 빅오, '지수적증가'는 무서운 연산횟수 증가를 야기한다.
• O(c^n) : 최악의 시간 복잡도
• O(n!) : 계승(factorial)

5. 시간복잡도 계산법

• Program Step에서 Elementary Operation의 수를 센다.

1. 대입연산
2. 사칙연산
3. 비교구문
4. 함수호출

• 계산법

1.  계수는 무시한다. 2N + 2, 3N + 1 과 같이, N에 붙은 계수는 무시하고 O(N)으로 계산함
2.  차수가 높거나 더 느린(우세한, 수행을 많이하는) 항을 이용한다. N^2 + N 인 경우, N^2이 N보다 느리기 때문에 (차수가 높기 때문에) O(N^2)으로 계산함. 또한 N + 1인 경우, 더 느린 O(N) 으로 표시함.
3. 실행문 안에 실행문은 곱하기, 실행문 이후 실행문은 더하기. 예를 들어 for문 안에 for문이면 N*N, for문 이후 for문이면 N+N

• 예제1

int sum = 0;
for (int i = 0; i < N; i++) {
	sum += N;
}

1) sum 변수에 = 0 대입 (1번)

2) i 변수에 = 0 대입 (1번)

3) i ++ (N번)

4) sum 변수에 + N (N번)

= 총 2N + 2 = O(N), 빅오 표기법에서는 계수를 무시하므로 O(N)의 시간복잡도를 갖는다.

 

• 예제2

int sum = (N + 1) * N / 2;

1) N +1 (1번)

2) N / 2 (1번)

3) 1) + 2) (1번)

4) sum에 N 대입 (1번)

= 총 4 = O(1), 즉 O(1)의 시간복잡도를 갖는다.