O (Big-O)

학계에서 big-O는 시간의 상한을 나타낸다. < big-O

(여기서 "학계에서"라는 말을 꼭 짚고 넘어가자, 현업에선 아니라는 뜻이다)

예를들어 배열의 모든 값을 출력하는 알고리즘의 시간복잡도를 O(N)으로 표현할 수 있지만 이를 O(N^2) 이나 O(N!)와 같이 표현해도 문제될 표현은 아니다.

즉, 해당 알고리즘이 big-O로 표현된 시간보다 빠르기만 하면 된다.

Ω (Big-Omega)

학계에서 big-Ω는 등가 개념, 혹은 하한을 나타낸다. >=big-Ω

즉, 위처럼 배열의 모든 값을 출력하는 알고리즘으로 예를 들자면, Ω(N) 뿐만 아니라 Ω(logN), Ω(1)도 마찬가지로 얼마든지 표현이 가능하다.

θ (Big-Theta)

위 두 개념에 대해 읽어봤다면,

뭐야 이거 그럼 되게 쓸모없는 개념들인데?

라는 생각이 들었을지도 모른다. big-O의 경우 그냥 무슨 알고리즘이던 O(N!)때려버리면 되고, big-Ω은 그 반대로 Ω(1)로 해버리고 맞다고 우겨버리면 그만인 개념이니까!

그렇기 때문에 실질적으로 중요한 개념이 바로 이 big-θ이다.

학계에서 big-θ는 O와 Ω를 둘 다 만족하는 경우를 의미한다.

즉 어떤 알고리즘이 O(N)과 Ω(N)을 모두 만족했을 때야 비로소 θ(N)을 만족한다고 할 수 있는 것이다.

실질적으로 가장 쓸모있고, 가장 많이 쓰여야 할 개념이라고 생각하면 될 것같다.

그런데 실제로는 big-O만 쓰던데요?

사실 위에서 학계에서는을 게속 강조한 이유가 있다. 실제 업계에선 big-O를 big-θ처럼 쓴다.

즉, 딱 맞는 적절한 시간복잡도를 big-O표기법을 쓰며, 그렇기 때문에 길이가 N인 배열을 순회하는 알고리즘의 복잡도를 O(N)으로 표현하고

"엥 big-O는 시간의 상한이니까 O(N^2)도 맞는거잖아요"

라고 우기지 않기로 암묵적으로 동의한다.

최선의 경우 vs 최악의 경우

보통 정렬 알고리즘에 대해 얘기할 때, 최선의 경우와 최악의 경우를 따지곤 한다.

퀵 정렬을 예로들어 보자.

만약 최선의 경우, 그러니까 모든 원소가 동일하다면 퀵 정렬은 평균적으로 한 차례 배열을 순회하고 종료할 것이다. 즉 big-O 시간복잡도로 보면 O(1)이라고 할 수 있을것이다.

하지만 최악의 경우, 계속 pivot을 최소값, 혹은 최대값으로 잡게된다면 어떻게 될까? 퀵정렬의 부분정렬에 대한 이점은 사라지고 결국, O(N^2)의 시간이 걸리게 될 것이다.

이처럼 알고리즘의 수행시간을 따질 땐, 경우에 따라서 다른 시간복잡도가 나올 수 있다. 당연하지만, 이 중 최선의 시간보다는 평균적인 경우, 혹은 최악의 경우를 주로 고려한다.

⭐️ 최선/ 최악의 경우와 big-O, Ω, θ의 관계

무관한 개념이다.

참고

책 - 코딩인터뷰 완전분석