Ω-표기법 정의는 다음과 같습니다.

모든 n > n₀에 대해 cg(n) <= f(n)인 양의 상수 c, n₀가 존재하면

f(n) = Ω(g(n))

Ω-표기법은 하한을 의미합니다. 실제로는 거의 사용하지 않습니다.

마지막으로 대표적인 빅오 종류를 성능이 빠른 순서대로 쭉 훑어보겠습니다.

1. O(1): 상수 시간이라고 합니다. 자료 구조에 저장된 데이터 개수와 상관없이 정해진 횟수의 연산 안에 알고리즘이 마무리됩니다. 가장 좋은 예로 동적 배열의 인덱싱이 있습니다. 동적 배열은 다음 장에서 알아봅니다.

2. O(log n): 로그 시간이라고 합니다. 로그의 그래프를 생각해 보면 이는 y=x로 그려지는 선형 시간에 비해 성능이 월등히 좋다고 할 수 있습니다. 대표적인 예로 이진 탐색 트리 계열에 속하는 자료 구조(이진 탐색 트리, 균형 이진 트리, B 트리)의 삽입과 탐색, 삭제 모두 로그 시간입니다.

3. O(n): 선형 시간입니다. 데이터 개수가 늘어날수록 선형으로 연산 횟수가 늘어납니다. 실제 함수를 만드는 데 O(n)으로 만들 수 있다면 충분히 만족할 만한 성능이라고 할 수 있습니다. 대표적으로는 연결 리스트의 탐색 연산과 동적 배열에서 배열 마지막에 원소를 추가하는 연산을 제외한 삽입·삭제 연산이 선형 시간입니다.

4. O(nlog n): 선형 로그 시간입니다. 그래프를 그려 보면 O(n)과 비교했을 때는 성능이 나쁘지만 O(n²)과 비교하면 성능이 매우 좋습니다. 대표적인 예로는 비교 정렬 중에서 가장 성능이 좋다고 알려진 퀵 정렬과 병합 정렬 등이 모두 O(nlog n)입니다.

5. O(n²), O(n³): 이제부터는 데이터 개수가 늘어날수록 연산 횟수가 가파르게 상승합니다. O(n²)은 이중 for 문을 실행할 때, O(n³)은 삼중 for 문을 실행할 때 성능입니다.

6. O(2ⁿ): 지수 시간입니다. O(n²)이나 O(n³)보다 훨씬 성능이 좋지 않습니다. 데이터 개수가 많을 때 이런 성능을 가진다면 함수 실행이 너무 늦어질 수 있겠지요. 정말 어쩔 수 없는 상황이 아니라면 좀 더 나은 알고리즘으로 구현할 수 없을지 고민해 보아야 합니다.