• 알고리즘의 효율성을 논하게 되는 때는 입력의 크기가 충분히 클 때이다. 이 때, 점근적 분석을 하게 되며 이를 통해 나타난 시간과 입력의 함수 관계를 시간 복잡도라고 한다.
• 시간 복잡도가 높다는 말은 입력한 크기가 증가할 때 알고리즘의 수행 시간이 더 빠르게 증가한다는 뜻이다.
• 알고리즘마다 최선의 수행 시간, 최악의 수행 시간, 평균적인 경우의 수행 시간(수행 시간의 기대치)이 있겠지만 주로 최악의 수행 시간과 수행 시간의 기대치를 중심으로 시간 복잡도를 판단하며, 따라서 Big-O Notation으로 표기한다. 이는 뒤에서 다뤄보도록 하자.
• 반복문이 시간 복잡도를 좌우한다.

점근적 표기

• 고등학교 때 배우는 무한의 개념(lim n→∞)과 비슷하다. 하지만 알고리즘에서 다루는 표기법은, 차수는 중요하되 계수는 중요치 않게 본다.

• 증가율 측면에서 볼 때 아래와 같다.

  • logN < N < NlogN < N^2 < N^3 < 2^N
• 점근적 표기법은 모두, 점근적 의미에서 같다고 볼 수 있는 함수의 ‘집합’을 의미한다.

Θ-표기법(Theta)

• Θ(f(n))은 점근적 증가율이 f(n)과 일치하는 모든 함수의 집합이다.

  • Θ(N^2)는 N^2, 3N^2-50 등을 포함한다.

O-표기법(Oh)

• O(f(n))은 점근적 증가율이 f(n)보다 작거나 같은 모든 함수의 집합이다.

  • O(N^2)는 N^2, 3N^2-50 뿐만 아니라, 5N+15, 2NlogN+3N, 500 등을 포함한다.
• 앞서 설명한 Big-O Notation이 바로 이것이다.

Ω-표기법(Omega)

• Ω(f(n))은 점근적 증가율이 f(n)보다 크거나 같은 모든 함수의 집합이다.

  • Ω(N^2)는 N^2, 3N^2-50 뿐만 아니라, 5N^3+15, 2N^2logN+1 등을 포함한다.

그밖에 ‘엄밀한’ 표기법들

o-표기법(Little Oh)

• Big Oh가 아닌 Little Oh 표기법도 있다.
• Big Oh와의 차이점은, (1/2)N^2이 o(N^2)에 포함되지 않는다는 것이다.
• 즉, o-표기는 함수 기울기상의 여유 있는 상한을 나타낸다.

ω-표기법(Little Omega)

• Big Omega가 아닌 Little Omega 표기법도 있다. 이는 Little Oh와 반대의 의미다.
• Big Omega와의 차이점은, 2N^2이 ω(N^2)에 포함되지 않는다는 것이다.
• 즉, ω-표기는 함수 기울기상의 여유 있는 하한을 나타낸다.

점화식을 통해 재귀호출 알고리즘의 수행 시간 표현하기

반복 대치, 추정 후 증명, 마스터 정리라는 대표적인 세 가지 방법에 대해 알아보자.

1. 반복 대치

   • T(n)을 T(n-1)로 대치하고, T(n-1)을 T(n-2)로 대치하고, …, T(1)까지 대치해가는 방식을 사용해 점근적 복잡도를 구하는 방법이다.

   • 예시로, n!를 구하는 데 소용되는 시간을 구해보자.

     T(n)
     = T(n-1) + c
     = (T(n-2) + c) + c
     = ((T(n-3) + c) + c) + c
     ...
     = T(1) + (n-1)c
     = O(n)

   • 병합정렬도 위와 같이 구하면, NlogN이 나옴을 알 수 있다.(참고로, 여기서 log는 밑이 2인 log을 의미)

2. 추정 후 증명

   • 식의 모양을 보고 복잡도를 추정한 다음, 이를 귀납적으로 증명하는 방법이다.
   • 예시는 생략하겠다.

3. 마스터 정리

   • 특정한 모양을 가진 재귀식(아래 형태)에서 바로 결과를 알 수 있게 해주는 유용한 정리다.

     T(n) = a*T(n/b) + f(n)

     병합 정렬이 대표적인 예로, a = b = 2, f(n) = n인 경우다.

   • a >= 1, b >= 1에 대해 위 형태의 점화식에서, N^(logba) = h(N)이라 할 때 f(n)과의 무게 비교를 통해 전체 복잡도를 알아볼 수 있다. 문병로 교수님의 책에는 “다항식의 비율로 압도한다”라는 표현이 쓰였다.

     • 참고로, logba라고 위에 작성한 것은 ‘밑이 b인 log a’를 의도한 것이니 착오 없기 바란다.

   • 직관적으로, 결과를 이해하자면 이렇다.

     1. h(N)이 더 무거우면 h(N)이 수행시간을 결정한다. Θ(h(N))
     2. f(N)이 더 무거우면 f(N)이 수행시간을 결정한다. Θ(f(N))
     3. 만일 이 둘이 같은 무게이면 h(n)에 logN을 곱한 것이 수행시간이 된다. Θ(h(N)logN)

---

[참고자료]
문병로(2018). 관계 중심의 사고법, 쉽게 배우는 알고리즘. 한빛아카데미.