big O vs big Ω vs big Θ
O (Big O)학계에서 big-O 는 시간의 상한을 나타낸다. 배열의 모든 값을 출력하는 알고리즘은 O(N) 으로 표현할 수도 있지만, 이 외에 N 보다 큰 big-O 시간으로 표현할 수도 있다. 예를 들어, O(N2),O(N3),O(2N)O(N^2), O(N^3), O(2^N)O(N2),O(N3),O(2N) 도 모두 옳은 표현이다. 다시 말해 실제 알고리즘의 수행시간은 적어도 이들 중 하나보다 빠르기만 하면 된다.Ω (Big Omega)학계에서 Ω 는 하한을 나타낸다. 해당 알고리즘은 Ω 수행 시간보다 빠를 수 없다.Θ (Big Theta)학계에서 Θ 는 O 와 Ω 둘다를 의미한다. 즉, 어떤 알고리즘의 수행시간이 O(N) 이면서 Ω(N) 이라면, 이 알고리즘의 수행 시간을 Θ(N) 으로 표현할 수..
