알고리즘 - 복잡도

복잡도

---

알고리즘의 복잡도

• 문제의 계산이 얼마나 어려운가를 나타내는 측정치이다.

• 계산을 위한 비용에 대한 측정치이다.

• 시간복잡도, 공간복잡도가 있으며 알고리즘에서 말하는 복잡도는 주로 시간복잡도를 의미한다.

 

점근표기법

1. O표기: upper bound를 표현한다.
2. Ω표기: lower bound를 표현한다.
3. Θ표기: upper bound와 lower bound를 동시에 표현한다.

 

빅오(Big -O)표기법 

• 증명: n > k > 0일때, f(n) <= c * g(n)를 만족하는 c, k가 존재 한다면 f(n) = O(g(n))이다.
• n이 무한히 커질때를 기준으로 한다. (고등학교 수학시간에 배운 '극한'의 개념을 떠올리면 쉽다. 그러나 프로그램에서는 고려할 조건이 많으므로 무조건 극한값과 같지는 않다.)
• 예제
  1.  f(n) = 1 + 2 + 3 + ... + x <= n + n + n + ... + n = n^2 = O(n^2)
  2.  f(n) = n! = n(n - 1)(n - 2)...1 <= n * n * n ... * n = n^n = O(n^n)
  3.  f(n) = log(n!) <= log(n^n) = nlogn = O(nlogn)

 

reference