홍라이프 계산기이진 탐색·비교 횟수 계산기 쉽게 이해하기 — 개념과 원리
원하는 값을 찾거나 목록을 정렬하려면 비교를 몇 번 해야 할까요? 이 계산기는 원소 n개에 대해 정렬된 자료에서 이진 탐색의 최악 비교 횟수, 순차 탐색의 평균 비교 횟수, 비교 기반 정렬이 넘을 수 없는 이론적 하한, 병합 정렬의 정확한 최악 비교 횟수를 함께 보여 줍니다. 한 번 정렬해 두고 여러 번 찾는 것이 왜 유리한지 숫자로 확인할 수 있습니다.
계산 방법
- 이진 탐색 최악: ⌊log₂ n⌋ + 1회
- 순차 탐색 평균: (n + 1) ÷ 2회이며, 찾는 값이 반드시 있고 어느 위치든 확률이 같다고 가정합니다.
- 정렬 하한: log₂(n!)이며, n!이 너무 커서 로그 감마 함수로 계산합니다.
- 병합 정렬 최악: n·⌈log₂ n⌉ − 2^⌈log₂ n⌉ + 1이며, n log₂ n − n + 1에 가깝습니다.
원리
이진 탐색은 비교할 때마다 남은 범위를 절반으로 줄이므로 j번 비교하면 후보가 n ÷ 2ʲ개 이하로 남고, 약 log₂ n번이면 끝납니다. 정렬 하한은 정보량으로 설명됩니다. 정렬은 가능한 n!가지 순서를 모두 구별해야 하는데, 예·아니요로 답하는 비교 한 번은 경우의 수를 많아야 절반으로 줄일 뿐입니다. 따라서 최악의 경우 최소 log₂(n!)번이 필요합니다. 스털링 공식으로 log₂(n!) ≈ n log₂ n − 1.443n이므로 어떤 비교 정렬도 Θ(n log n)보다 빠를 수 없습니다.
예제 풀이
- 입력값: n = 1,000,000입니다.
- 이진 탐색: log₂ 10⁶ ≈ 19.93이므로 ⌊19.93⌋ + 1 = 20회입니다.
- 순차 탐색: (1,000,000 + 1) ÷ 2 = 평균 500,000.5회입니다.
- 정렬 하한: log₂(1,000,000!) ≈ 18,488,884.82회입니다.
- 병합 정렬: ⌈log₂ 10⁶⌉ = 20이므로 10⁶ × 20 − 2²⁰ + 1 = 20,000,000 − 1,048,576 + 1 = 18,951,425회입니다.
| 항목 수 | 최악의 비교 횟수 (이진 탐색) |
|---|---|
| 250,000 | 18 |
| 500,000 | 19 |
| 750,000 | 20 |
| 1e+06 | 20 |
| 1.25e+06 | 21 |
| 1.5e+06 | 21 |
| 2e+06 | 21 |
결과 해석
이 예에서 이진 탐색은 순차 탐색보다 약 25,000배 적게 비교하지만, 자료가 정렬되어 있어야 합니다. 정렬에 약 1,900만 번의 비교가 들므로 같은 자료를 수십 번 이하로만 찾는다면 순차 탐색이 전체적으로 더 쌀 수도 있습니다. 병합 정렬의 최악값은 하한보다 약 2.5% 많을 뿐이어서 비교 횟수를 더 줄일 여지는 거의 없습니다.
흔한 실수
- 정렬되지 않은 자료에 이진 탐색을 쓰면 오류 없이 틀린 답이 나옵니다.
- 중간값을 (low + high) ÷ 2로 계산하면 고정 길이 정수에서 넘침이 생길 수 있으므로 low + (high − low) ÷ 2를 씁니다.
- 계수 정렬이나 기수 정렬처럼 비교하지 않는 정렬에도 하한이 적용된다고 오해합니다.
자주 묻는 질문
왜 log₂ n이 아니라 ⌊log₂ n⌋ + 1인가요?
비교 횟수는 정수여야 하고, 후보가 하나 남아도 마지막 확인 비교가 필요하기 때문입니다.
10억 개라면 몇 번 비교하나요?
2³⁰이 10억을 조금 넘으므로 30번이면 충분합니다.
해시 테이블이 이진 탐색보다 빠른가요?
평균적으로는 그렇지만, 해시 테이블은 범위 검색이나 가장 가까운 값 찾기를 하지 못합니다.
출처: D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley · T. H. Cormen 외, Introduction to Algorithms, MIT Press