시간복잡도

시간복잡도

시간복잡도는 알고리즘의 효율성을 측정하기 위하여 사용한다. 시간복잡도에는 몇 가지 규칙이 있다.

• input >= 0
  함수의 입력값은 0개 이상이 들어와야한다.
  

• function do more work for more input.
  입력값이 많아질 수록 함수가 처리하는데에 시간이 많이 든다.
  

• drop all constants
  시간복잡도를 표시할 떄 차수는 고려하지 않는다.
  $2n = 3n = 100n = n$
  

• ignore lower order terms
  시간복잡도를 표시할 때 최고차항만 고려한다.
  $2n^2+3n = 3^2 = 100n^2+5n+1 = n^2$
  

• ignore the base of logs
  시간복잡도를 표시할 때 로그의 밑은 고려하지 않는다.
  탐색 시 반을 나누거나 2를 곱하면 밑이 2인 $\log_{2}n$이 되고 10을 나누거나 10을 곱하면 $\log{10}n$이 되는데 이는 모두 $\log n$으로 표시한다.
  
  
  

시간복잡도를 그림으로 나타내면 위의 그림과 같다. 주황색 선을 n이라고 할떄, n의 아래는 o(스몰 오), n을 포함한 아래는 O(빅오), n은 Θ(쎄타), n의 위는 ω(스몰 오메가), n을 포함한 위는 Ω이다.

• O (<= n) : n과 같거나 빠르다
• o (< n) : n보다 빠르다
• Θ (= n) : n과 같다
• ω (> n) : n보다 느리다
• Ω (>= n) : n과 같거나 느리다
  
  

알고리즘의 효율성을 예측할 때는 주로 빅오 표시법을 사용한다. 빅오 표시법을 쉽게 계산하는 방법은 큰 값을 n에 대입하여 생각하는 것이다.
$n^{4/3} = O(nlog{n})$ 이 참인지 거짓인지 판단해보자

$$ \begin{align} n=1000, \\ & (1000)^{4/3}= 10,000 > 1000 \ (log{1000})=3000 \\ &\therefore n^{4/3} \neq O(nlog{n})\end{align} $$

빅오가 되기 위해서는 큰 값을 대입했을 때, $ \text{시간복잡도를 표시할 값}<= O(nlog{n})$ 으로 되어야 성립된다.그림으로 표시하면 다음과 같다.

분홍선 안에 값이 있어야 시간복잡도가 $O(nlog{n})$라 할 수 있다.