5.4 상수 무시하기
하지만 재미있게도 빅 오 표기법에서는 선택 정렬과 버블 정렬을 정확히 같은 방식으로 설명한다.
다시 강조하자면 빅 오 표기법은 데이터 원소가 N개일 때 얼마나 많은 단계 수가 필요한가라는 핵심 질문에 답한다. 선택 정렬에 대략 N2의 반 단계 정도가 걸리므로 선택 정렬의 효율성을 O(N2 / 2)로 설명하면 적당할 듯하다. 즉, 데이터 원소가 N개일 때 N2 / 2단계가 필요하다. 다음 표가 이를 뒷받침한다.
▼ 표 5-3
|
원소 개수(N) |
N2 / 2 |
선택 정렬에서 최대 단계 수 |
|
5 |
52 / 2 =12.5 |
14 |
|
10 |
102 / 2 =50 |
54 |
|
20 |
202 / 2 200 |
199 |
|
40 |
402 / 2 = 800 |
819 |
|
80 |
802 / 2 = 3239 |
3239 |