탐색·점근 시간·보조 공간

빠르다는 말에 입력과 단위를 붙이기

정렬된 배열 A[i]=i에서 target을 찾는 문제를 생각합니다. 선형 탐색은 왼쪽부터, 이진 탐색은 남은 구간의 가운데부터 확인합니다. 어느 방법이 빠른지 말하려면 입력 크기 N, target의 위치, 허용 연산과 비교 비용을 먼저 정해야 합니다. 이 실험은 CPU 시간을 가정하지 않고 한 번의 순서 질의를 한 key probe로 셉니다. 실제 언어의 두 branch 평가를 두 개의 기계 명령이라고 세는 모형과 다릅니다.

Target은 존재하는 상대 rank, 모든 key보다 큰 부재 값, 모든 key보다 작은 부재 값 중에서 정합니다. 그래프의 각 N에서도 같은 질의 생성 규칙을 다시 적용합니다. 파랑과 주황은 실제 실행한 선형·이진 탐색의 probe 수이며 마이크로초가 아닙니다.

Big O의 양화와 입력 가족

Omega는 장기적 하한, Theta는 양쪽 bound를 말합니다. 상수와 작은 N의 예외가 있지만 어떤 입력을 최대화하거나 평균냈는지가 더 중요합니다. Worst-case는 크기 N의 모든 허용 입력에서 최대를 취합니다. Average-case는 입력 분포가 필요합니다. 첫 원소만 묻는 가족에서 선형 탐색은 항상 한 번이므로 그 그림을 일반적인 최악 Theta(N) 곡선으로 부르면 틀립니다.

이진 탐색의 불변식

정렬성과 남은 구간 [lo,hi]가 핵심입니다. 찾는 값이 존재한다면 반드시 이 구간 안에 있다는 불변식을 유지합니다. 가운데보다 크면 왼쪽 절반을, 작으면 오른쪽 절반을 버리고 일치하면 반환합니다. 부재 질의는 lo>hi가 되면 끝납니다.

이 식은 비교 모형의 최악 bound이며 하나의 선택한 target이 항상 상한에 도달한다는 말은 아닙니다. 표에는 실제 probe index와 당시 구간을 남기므로 불변식을 직접 확인할 수 있습니다.

공간과 진단 기록

현재 핵심 탐색은 반복형이라 재귀 stack 깊이가 0이고 구간 index 등 상수 개의 보조 scalar로 실행할 수 있습니다. 입력 배열의 N개 원소는 별도입니다. 하지만 교육 화면은 probe trace와 여러 N의 비교 결과를 저장합니다. 이 진단 기록까지 포함한 프로그램 전체의 메모리를 O(1)이라고 주장하면 안 됩니다. 입력 저장, 알고리즘 보조 공간, 출력과 디버깅 기록을 나누어 보고하세요.

손계산과 직접 풀기

N=32에서 마지막 key 31을 선형으로 찾으면 32회입니다. 이진 탐색은 15,23,27,29,30,31을 조사하여 6회이며, 32라는 없는 key를 찾을 때도 같은 6회 뒤 종료합니다. 첫 key 0의 선형 탐색은 1회입니다.

직접 풀기: N=8에서 target 6의 이진 탐색 경로를 구하세요. 풀이: index 3의 값 3보다 크므로 [4,7], index 5의 값 5보다 크므로 [6,7], index 6에서 일치하여 3회입니다. 각 단계의 정렬 불변식과 반환 index를 표에서 검산하세요.

AI 시스템에서의 복잡도 보고

Retrieval index와 sparse data 구조는 사전 정렬·구축·갱신 비용을 숨기면 부당하게 유리해 보일 수 있습니다. Query probe 수, 구축 메모리, 실제 지연과 입력 분포를 함께 기록하세요. 유한 그래프는 계수와 경계 조건을 확인하는 증거이며 일반 bound는 위의 양화와 불변식으로 증명합니다.

참고: MIT 알고리즘 강의.