하지만 실제로 선택 정렬을 빅 오로 표현하면 버블 정렬과 똑같이 O(N2)이다. 지금부터 최초로 소개할 빅 오의 규칙 때문이다.
빅 오 표기법은 상수를 무시한다.
빅 오 표기법은 지수가 아닌 수는 포함하지 않는다는 것을 단순히 수학적으로 표현한 문장이다. 표현식에서 이러한 수는 그냥 버린다.
앞선 예제에서 알고리즘에는 N2 / 2단계가 필요했지만 “/ 2”를 버리고 효율성을 O(N2)으로 표현했다.
몇 가지 예를 더 살펴보자.
N / 2단계가 필요한 알고리즘은 O(N)으로 표현한다.
N2 + 10단계가 필요한 알고리즘은 지수가 아닌 10을 버리고 O(N2)으로 표현한다.
2N단계(N × 2라는 의미)가 필요한 알고리즘은 2를 버리고 O(N)으로 표현한다.
O(N)보다 100배나 느린 O(100N)이라 해도 마찬가지로 O(N)이다.
빅 오로는 정확히 똑같이 표현하는 두 알고리즘에 대해 한쪽이 다른 한쪽보다 100배나 빠를 수 있다는 이 규칙은 빅 오 표기법을 완전히 쓸모없어 보이게 만든다. 선택 정렬과 버블 정렬에서도 정확히 마찬가지다. 두 알고리즘 모두 빅 오로는 O(N2)이지만 선택 정렬은 사실 버블 정렬보다 두 배나 빠르다.
대체 어떻게 된 일일까?