검색 알고리즘

백만 개의 이름에 대한 20가지 질문

• 전화번호부에는 백만 명의 이름이 들어 있습니다. 하나씩 확인한다면 원하는 이름을 찾을 때까지 반백만 번의 비교를 할 것으로 예상됩니다.
• 대신 중간에서 열고, 이름이 어느 반에 있는지 결정한 뒤 나머지 반은 버립니다. 이를 반복하십시오. 어떤 이름도 20번의 비교로 도달할 수 있습니다.
• 반백만 대 스무 개의 차이는 사소한 절감이 아니라, 작동하는 프로그램과 사용할 수 없는 프로그램의 차이입니다. 단, 조건이 하나 있습니다: 목록이 이미 정렬되어 있어야 한다는 점입니다.
• 이 수업은 선형 탐색과 이진 탐색이며, 각각의 성능과 선택 방법을 다룹니다.

선형 탐색

FOR i ← 1 TO n
    IF A[i] = target THEN
        RETURN i
    ENDIF
NEXT i
RETURN -1                     // not found

• 시작점에서 시작하여 각 요소를 타겟과 비교하고, 매칭을 찾거나 끝까지 도달하면 멈춥니다.
• 어떤 목록에도 적용되며, 정렬되었든 그렇지 않든 상관없으며, 순환할 수 있는 모든 구조에서도 작동합니다.
• 최악의 경우: 목표가 마지막에 있거나 없으므로, 모든 $n$ 요소를 비교해야 하므로 $O(n)$입니다. 평균적으로는 약 절반 정도입니다.

처음부터 하나씩

이진 탐색

low ← 1 ;  high ← n
WHILE low <= high DO
    mid ← (low + high) DIV 2
    IF A[mid] = target THEN
        RETURN mid
    ENDIF
    IF A[mid] < target THEN
        low ← mid + 1
    ELSE high ← mid - 1
ENDWHILE
RETURN -1

• 데이터가 정렬되어 있음을 요구합니다. 중간 요소를 타겟과 비교합니다: 매칭하면 멈추고, 타겟이 크면 아래쪽 반을 버리거나, 그렇지 않으면 위쪽 반을 버립니다.
• 각 비교마다 아직 탐색할 범위가 반으로 줄어드므로, 비교 횟수는 $O(\log_2 n)$입니다.
• 백만 개 항목에 약 20번의 비교가 필요한 이유입니다: $2^{20}$은 백만보다 약간 니다.

풀이 예제: 이진 탐색 추적

선택 기준

• 먼저 정렬하는 비용은 선형 탐색 한 번보다 크므로, 이진 탐색은 목록이 이미 정렬되어 있거나 여러 번 검색될 때만 유리합니다.
• 이진 탐색은 또한 중간 요소에 대한 직접 접근이 필요하며, 이는 배열은 가지고 있지만 연결리스트는 없습니다.

연습 예제: 선택의 근거 제시

파일을 정렬로 유지하는 비용

• 이진 탐색은 정렬된 목록에서만 가능하며, 그 정렬은 무료가 아닙니다. 선을 변명하라는 질문은 그 비용을 평가하라는 뜻입니다.
• 데이터가 자주 검색되고 드물게 변경된다면, 한 번만 정렬하고 이후 모든 검색은 $\log_2 n$입니다. 사전이나 조회표의 경우입니다.
• 데이터가 항상 변경된다면, 각 삽입 시 순서를 유지해야 하므로 이후 요소들의 이동 비용이 발생합니다. 비정렬 데이터에 대한 선형 탐색이 전체 비용 면에서 저렴할 수 있습니다.
• 숫자로 논리를 구체적으로 보일 수 있습니다: 백만 개의 기록은 선형 탐색 시 최대 백만 번의 비교가 필요하지만, 이진 탐색 시에는 20번만 필요하며, 이는 $2^{20} > 10^6$ 때문입니다.
• 따라서 표시된 답은 두 부분 모두를 포함합니다: 얼마나 자주 검색되고, 얼마나 자주 변경되는지.

놓칠 수 있는 점

이해했습니다