Time Complexity (시간복잡도)

 시간을 기준으로 알고리즘의 효율성을 분석할 때, CPU에서의 실제 작동시간을 재지 않는다. 왜냐하면 알고리즘을 수행하는 특정 컴퓨터에 따라서 결과가 달라 질 수 있기 때문이다. 컴퓨터, 프로그래밍언어, 프로그래머뿐만 아니라 루프 색인의 증가, 포인터의 세팅 등과 같은 모든 알고리즘 상의 복잡한 세부사항과는 독립적인 측정법이 필요하다. 실행시간은 입력의 크기가 커지면 증가하고, 총 실행시간은 단위연산이 몇 번 수행되는가에 거의 비례하기 때문에 단위연산이 수행되는 횟수를 분석하여 알고리즘의 효율성을 분석한다.

즉, Time Complexity란 입력크기를 기준으로 단위연산을 몇 번 수행하는지 구하는 것이다.

 단위연산의 횟수를 세는 데에는 차수가 중요하다. 복잡도 카테고리는 여러가지, 셀 수 없을 만큼 많지만 대표적인 것은 다음과 같다.

log(n) n nlog(n) n^2 n^3 2^n n!

 왼쪽에서 오른쪽으로 갈 수 록 Time Complexity가 높은 것이다. 물론 일정 범위에서는 순서가 맞지 않을 수 있다. 하지만 우리가 보고자하는 것은 궁극적으로 어떤 함수가 아래에 위치하는지가 중요하다. 이러한 Time Complexity에는 여러가지 기준에 따른 다양한 측정법이있다.

[그림1] 복잡도 함수

Time Complexity

1. T(n) : 일정 시간복잡도 (every-case time complexity)

2. W(n) : 최악 시간복잡도 (worst-case time complexity)

3. A(n) : 평균 시간복잡도 (average-case time complexity)

4. B(n) : 최선 시간복잡도 (best-case time complexity)

5. O(n)

6. Ω(n)

7. θ(n)
   

1. 일정 시간복잡도

 T(n)을 실행 횟수가 일정한 경우 입력크기 n에 대해서 알고리즘이 단위연산을 실행하는 횟수로 정의한다. 예를 들어 배열에 있는 모든 수의 합을 더하라는 것은 항상 배열의 크기만큼 연산을 해야한다.

 크기 n인 사례에 대해서 단위연산을 실행하는 횟수가 같지 않은 사례가 많다. 예를 들어 크기가 n인 배열에서 x를 찾으려고하면 맨 앞에 있는 경우 1번만에 찾을 수도 있고 최악의 경우 n일 수도 있다. 즉, 사례마다 단위연산 실행횟수가 다르다. 그래서 이에 대한 측정법이 3가지가 있다.

2. 최악 시간복잡도

 이때 W(n)을 입력크기 n에 대해서 알고리즘이 실행할 단위연산의 최대 횟수로 정의한다.

3. 평균 시간복잡도

 A(n)은 입력크기 n에 대해서 그 알고리즘이 수행할 단위연산의 평균 횟수(기대치)로 정의한다.

4. 최선 시간복잡도

 단위연산을 실행하는 최소 횟수를 구하는 것이다. 즉, 크기가 n인 배열에서 x를 찾으려고 하면 1번 실행할 수도 있고 n번 실행할 수도 있는 데 최악 시간복잡도로 측정하면 n이었고 최선 시간복잡도는 1로 측정된다. 일반적으로 최선의 경우 최악의 경우나 평균의 경우를 더 자주 채택한다.

차수를 엄밀하게 정식으로 정의하기 위한 이론을 소개한다.

주어진 복잡도 함수 f(n)에 대해서 O(f(n))은 정수 N 이상의 모든 이상의 모든 n에 대해서 다음 부등식이 성립하는 양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

5. Big O

g(n) <= c * f(n)

 예를 들어 n^2 + 10n은 2n^2보다 처음에 위에 있지만 나중에는 아래에 있게 된다. 따라서 n^2 + 10n은 O(n^2)이다.  g(n)이 O(n^2)이라면 g(n)은 궁극적으로 cn^2인 함수 아래에 놓이게 된다. 즉, 궁극적으로 빠르기가 최소한 2차함수만큼은 된다는 뜻이다. 이를 점근적인 상한이라고 한다.

6. 오메가 Ω

g(n) >= c * f(n)

 5n^2은 n^2에 대해서 위의 정의를 만족한다. 따라서 5n^2는 Ω(n^2)를 만족한다. 즉, 가장 빠른 경우 2차함수만큼 빠르기가 나온다는 것이다. 이를 점근적인 하한이라고 한다.

7. 세타 θ

주어진 복잡도 함수 f(n)에 대해서 다음과 같이 정의한다.

θ(f(n)) = O(f(n)) ∩ Ω(f(n))

θ(f(n))은 정수 N 이상의 모든 이상의 모든 n에 대해서 다음 부등식이 성립하는 양의 실수 c, d와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

c*f(n) <= g(n)  <= d*f(n)

만약 g(n) ∈ θ(f(n))을 만족하면 g(n)은 f(n)의 차수(order)라고 한다.

 일반적으로 Big O를 가장 많이 사용한다. 왜냐하면 가장 빠를 때를 알려주는 것보다 '우리 알고리즘은 아무리 못해도 이정도 성능은 보장한다'가 더 신뢰성이 높기 때문이다.

---

사진 출처 

· [그림1] : https://en.wikipedia.org/wiki/Big_O_notation