더북(TheBook)

따라서 빅 오에서 서로 다른 카테고리에 속하는 두 효율성을 비교할 때 일반적인 카테고리로 분류하는 것으로 충분하다. O(2N)과 O(N2)을 비교하는 것은 2층집과 고층 건물을 비교하는 것과 다를 바 없다. O(2N) 역시 일반적인 O(N) 카테고리에 속한다고 말하는 편이 훨씬 낫다.

O(1), O(logN), O(N), O(N2)처럼 지금까지 다룬 모든 빅 오 유형이나 이 책에서 앞으로 나올 유형은 서로 차이가 큰 일반적인 빅 오 카테고리다. 지수가 아닌 수로 단계 수를 곱하거나 나눈다고 카테고리가 바뀌지 않는다.

하지만 두 알고리즘이 같은 카테고리에 속하더라도 서로 처리 속도가 다를 수 있다. 버블 정렬과 선택 정렬은 둘 다 O(N2)이지만 어쨌든 버블 정렬은 선택 정렬보다 두 배 느리다. 따라서 빅 오에서 서로 다른 카테고리에 속하는 알고리즘을 대조할 때는 빅 오가 완벽한 도구지만 같은 카테고리에 속하는 두 알고리즘이라면 어떤 알고리즘이 더 빠를지 알기 위해 더 분석해야 한다.

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.