2.1.3 방심은 금물!: 빅오의 함정

지금까지 빅오를 알아보았는데, 그렇다고 너무 맹신해서도 안 됩니다. 빅오는 연산 횟수를 기반으로 한 상대적인 기준이기 때문에 하드웨어나 다른 외부적인 요소를 전혀 고려하지 않습니다. 한 가지 예를 들어 볼까요? 메모리에서 값을 두 개 가져와 더한 후 다시 메모리에 저장하는 동일한 알고리즘을 한 컴퓨터에서는 메인 메모리에서 값을 가져와 저장한다 하고, 다른 컴퓨터에서는 하드 디스크에서 값을 가져와 저장한다고 가정하겠습니다. 컴퓨터 내부에는 클럭(clock)이라는 시계 개념의 장치가 있습니다. 자세한 내용은 이 책 범위를 벗어나므로 지금은 단순히 시간이 얼마 걸리는지 잴 수 있다고만 해 두죠. 메인 메모리에서 값을 가져오거나 저장하는 데는 20~100클럭이 필요한 반면, 하드 디스크에서 값을 가져오거나 저장하는 데는 50~500만 가까운 클럭이 필요합니다. 엄청난 차이가 나지요. 이런 상황을 고려한다면 동일한 알고리즘을 실행할 때 ‘둘 모두 같은 빅오를 가지므로 비슷한 성능을 내겠구나’라고 판단하는 것은 옳지 못합니다. 그러므로 명세에서 빅오가 O(n)이라고 표기되어 있더라도 반드시 벤치마킹 등을 이용하여 실제 성능을 테스트해 보는 것이 좋습니다.