알고리즘의 수행 시간을 분석하는 것. 알고리즘을 구성하는 함수에 따른 수행 시간은 아래와 같다.
http://stackoverflow.com/questions/7830727/n-log-n-is-on
시간 복잡도의 표기는 여러개가 있지만, 기본적인 것 3개만 정리한다.
알고리즘 시간의 하한선을 나타내는 표기법. 알고리즘 수행 시간이 아무리 빨라도 비교 함수에 비해 같거나 빠르다.
표기는 대문자 O 다음의 괄호안에 비교하는 함수를 넣는다. ex) $O(g(n)), O(n), O(n^{2}), O(\log n), O(n \log n)...$
알고리즘 시간의 상한선을 나타내는 표기법. 알고리즘 수행 시간이 아무리 빨라도 비교 함수에 비해 같거나 느리다.
표기는 Ω(오메가) 다음의 괄호안에 비교하는 함수를 넣는다. ex) $\Omega(g(n)), \Omega(n), \Omega(n^{2}), \Omega(\log n), \Omega(n \log n)...$
알고리즘 시간의 상한-하한 범위선을 나타내는 표기법. 빅오와 오메가의 교집합을 의미한다.
$\Theta(g(n)) = O(g(n)) \cap \Omega(g(n))$
표기는 Θ(세타) 다음의 괄호안에 비교하는 함수를 넣는다. ex) $\Theta(g(n)), \Theta(n), \Theta(n^{2}), \Theta(\log n), \Theta(n \log n)...$
알고리즘이 사용하는 메모리의 양을 분석하는 것.