O(n)과 O(log n)의 성능 차이
O(n)의 경우 데이터가 증가함에 따라 동일하게 시간이 늘어나는 경우이며, O(log n)은 데이터의 개수가 커져도 log 연산이기 때문에 선형적인 n과 비교가 불가할 정도로 빠르다.
예를 들어 100명이 줄을 섰을 때 이 중에서 티켓을 들고 있는 친구를 찾아야 들어갈 수 있다고 치자. 앞에서부터 찾을 경우 가장 운이 좋은 경우 맨 앞에 있어서 즉시 찾을 수 있지만 그게 아니라 운이 안 좋을 경우 마지막 100명 째일 가능성도 있다. 바로 이 경우가 O(n)인 것이다.
하지만 log(n)의 경우 그 친구가 어디있는 진 모르니 정확히 절반인 50명에서 앞에 있을 지 뒤에 있을 지 찾고 또 그 반을 찾고 반을 찾고를 반복하면 100번째 자리에 있는 것보단 매우 빠르게 찾을 수 있다.
당장 100명 만으로도 이 정도 차이인데 그 데이터가 많아지면 많아질 수록 그 격차는 커질 것이 자명하다.
데이터 크기가 1백만 개일 때?
그렇다면 데이터 크기가 1백만 개 일 때는 어느정도 차이일까?
O(n)의 경우 앞에서 부터 찾는 경우기 때문에 최악의 경우 1백만 번 찾아야 할 수 있지만,
O(log n)의 경우 50만 - 25만 - 12.5만 - ... - 찾음 이기 때문에 약 20번의 연산으로 가능하다. 따라서 O(n)과 O(log n)은 데이터의 크기가 1백만 개 일땐 5만 배 이상 빠를 수 있다는 것이다.
