시간복잡도, Big O

Big O : O

Big O describes an upper bound on the time.

학문적으로, Big O는 시간의 상한선을 의미한다.

사람은 모두 최대 100살까지 산다고 가정하고, 이 때 사람의 나이를 x라고 하자.

이 때 x<=100, x<=1000, x<=10000 의 식은 모두 맞는 말이다.

따라서 사람의 나이를 Big O로는 O(N), O(N^2), O(N^3) 모두로 나타낼 수 있다.

이를 다시 알고리즘 관점으로 가져오면 실제 런타임 속도는 Big O로 표현한 속도보다 작거나 같다는 것을 의미한다.

 

Big Omega : Ω

Big omega is the equivalent concept but for lower bound.

학문적으로, Big Omega는 시간의 하한선을 의미한다.

다시 사람의 나이 비유를 빌려오자면, Big omega로는 Ω(N), Ω(log N), Ω(1)로 표현할 수 있다.

이를 다시 알고리즘 관점으로 가져오면 실제 런타임 속도는 Big Omega로 표현한 속도보다 크거나 같다는 것을 의미한다.

Big Theta : Θ

Big Theta means both Big O and Big Omega.

즉, Θ(N)는 O(N)과 Ω(N)를 모두 만족한다는 뜻이다.

사람의 나이 x가 x<=100, x>=100일 때, x=100을 뽑아내 Big Theta로 표현한다고 볼 수 있다.

---

 

 

위에서 알아보았듯이, 학문적으로 Big O는 시간의 상한선을 의미한다.

하지만 산업/현업에서 알고리즘을 이야기할 때에는, Big O와 Big Theta를 합친 것을 Big O로 이해하며 사용한다.

그냥 Big Theta의 의미를 Big O로서 사용한다고 봐도 무방할 것 같다.

 

즉, 길이가 n인 배열의 모든 원소를 출력하는 알고리즘의 Big O를 묻는다면 그 답은 O(N)이며, $O(N^2)$로 나타내면 틀린 답이 될 것이다.