[Time Complexity] 시간 복잡도

Algorithm의 수행시간을 이론적으로 분석하기 위한 개념

수행시간은 환경에 따라 달라진다.(구현한 언어, 컴파일러, 컴퓨터의 스펙 등)

 

즉, 같은 환경적 요인들을 가졌을 때의 수행시간을 비교

 

아래 3가지에 대한 시간 복잡도를 주로 분석한다.

 

 

 

● Big-Oh  Notation

빅오 표기법, 주로 사용하는 표기법이다.

왜 빅오표기법을 주로 사용하는가?

  - 'A라는 알고리즘이 최선의 경우 1초만에 문제를 해결한다.' 하지만, 최악의 경우 inf의 시간이 걸린다면, 의미가 있다고 할 수 있을까? 이보다는 'A라는 알고리즘은 최악의 경우에도 10초만에 문제를 해결해' 가 더 의미있을 것이다.

 

 

- 두 함수 간의 관계를 나타내는 표기법

시간복잡도를 나타내는데 주로 쓰이지만, 별개로 함수의 증가속도(growth rate of functions)를 비교하기 위한 표기법이다.

• f(n) = O(g(n))  :  함수 f의 증가속도가 g보다 빠르지 않다. (즉 비슷하거나 느리다)
• f(n) = Ω(g(n))  :  함수 f의 증가속도가 g보다 느리지 않다. (즉 비슷하거나 빠르다)
• f(n) = Θ(g(n))  :  함수 f의 증가속도가 g와 비슷하다.

* 이때의 증가속도는 n이 무한으로 갈 때 누가 더 빨리 증가하는지

 

 

- 빅오, 오메가, 세타의 비교

f(n)이 다음과 같을 때... 아래와 같다.

 

f(n) = O(n) (x)

f(n) = O(n^2) (o)

f(n) = O(n^3) (o)

 

f(n) = Ω(n) (o)

f(n) = Ω(n^2) (o)

f(n) = Ω(n^3) (x)

 

f(n) = Θ(n) (x)

f(n) = Θ(n^2) (o)

f(n) = Θ(n^3) (x)

 

 

 

● 증가속도에 따른 함수들의 서열

1	상수함수
logn, log(logn), ...	로그함수(polylogarithm)
logn
(logn)^2, (logn)^3, ...
n, n^2, n^3, ...	다항함수(polynomial)
2^n, 3^n, ...	지수함수(exponential)
n! (팩토리얼)
n^n(n의 n승)