다음은 대표적인 빅오입니다.
표 15-1 대표적인 빅오의 종류
|
O(1) |
1은 상수(constant)를 의미합니다. 데이터가 증가해도 연산 횟수는 항상 같습니다. 예 배열(인덱싱을 통해 데이터에 접근할 때) |
|
O(n) |
증가 형태가 선형(linear)입니다. 데이터 개수가 늘면 개수에 비례하여 연산 횟수도 증가합니다. 예 연결 리스트(순회) |
|
O(log n) |
증가 형태가 로그(logarithmic) 함수의 그래프를 그립니다. 데이터가 증가해도 연산 횟수의 증가율이 매우 낮습니다(그림 15-6 참조). 굉장히 좋은 성능입니다. 예 이진 탐색 트리(탐색) |
|
O(n*log n) |
증가 형태가 선형과 로그 형의 곱(linear loagrithmic)으로 나타납니다. 선형 빅오보다는 성능이 떨어지지만, 제곱 형태의 함수(n2)와 비교하면 성능이 월등합니다. 예 퀵 정렬(정렬 알고리즘 중 성능이 가장 좋다고 알려져 있음) |
|
O(n2) |
증가 형태가 제곱(quadratic)입니다. 데이터 개수가 적을 때는 이용해도 괜찮지만, 데이터 개수가 조금만 많아져도 연산 횟수가 급격히 늘어나므로 이용하기에 부담스러운 성능입니다. 예 거품 정렬(2절) |