O(log n), O(n log n) 사용을 왜하는 걸까? Google, Facebook의 경우 특정 테이블은 레코드가 몇십억, 몇백억 개가 있고, 테라 바이트, 페타 바이트 단위 이상이라고 합니다. 인덱스를 태우지 않고, 선형탐색으로 했을 때 레코드가 500만개만 있어도 요청 하나를 200초 안에도 처리하지 못합니다. O(n) 알고리즘을 사용했을 때 1000만번 계산해야 할 때, O(log n) 알고리즘을 사용할 때 수십 번만 계산해도 처리가 가능합니다. 그 차이는 데이터가 커질수록 기하급수적으로 커지겠죠. 그래서 대규모 서비스를, 아니 중규모 이상 서비스를 고려한다면 O(n) 알고리즘을 O(log n) 알고리즘을 사용하는 것이 중요합니다. 이런 이유로, Basic하게 배운 선형 탐색들을 사용하기 보다..
