비교
점프 크기
선형 탐색이라면

  • 목표값
  • 현재 블록
  • 비교 중
  • 제외됨
  • 찾음

점프 탐색 자세히 알아보기

점프 탐색

점프 탐색은 선형 탐색과 이진 탐색의 중간쯤에 있습니다. 정렬된 목록을 m칸씩 점프하며 나아가고, 각 블록의 마지막 값만 확인하다가, 마지막 값이 목표값보다 작지 않은 블록에 이르면 멈춥니다. 그런 다음 그 블록을 처음부터 스캔합니다. 찾을 값과 점프 크기를 고르고, 점프와 스캔에 비교가 몇 번 드는지 살펴보세요. ‘재생’을 눌러 탐색을 보거나, ‘단계’와 ‘뒤로’로 비교를 하나씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 점선은 찾는 값을, 음영 부분은 현재 블록을 나타냅니다. 점프 탐색은 정렬된 목록이 필요하므로 정렬되지 않은 목록은 먼저 정렬합니다. 찾을 값, 점프 크기, 막대 개수를 고르거나 직접 숫자를 입력하세요. 보드를 선택한 상태에서는 화살표 키로 한 단계씩 이동하고, 스페이스 바로 재생과 일시 정지를 하며, Home과 End로 처음과 끝으로 이동합니다.

작동 원리

  1. 찾을 값, 점프 크기, 막대 개수를 고르세요. 직접 숫자를 입력해도 됩니다. 점프 탐색이 먼저 정렬합니다.
  2. ‘재생’을 누르거나, ‘단계’와 ‘뒤로’로 비교를 하나씩 진행하세요. 단계 슬라이더를 끌면 탐색의 원하는 지점으로 이동합니다.
  3. 막대 40개에서 점프 크기 2와 8을 시험해 보고, 비교 횟수를 √n일 때와 비교해 보세요.

점프 탐색의 원리

정렬된 목록을 m개씩의 블록으로 나눕니다. 첫 블록의 마지막 값을 봅니다. 그 값이 목표값보다 작으면 목표값은 그 블록 어디에도 없으므로, 다음 블록의 끝으로 점프해 다시 봅니다. 블록의 마지막 값이 작지 않게 되면 목표값은 그 블록에만 있을 수 있습니다. 블록의 처음으로 돌아가 목표값을 찾거나 지나칠 때까지 값을 하나씩 확인합니다.

점프 크기 고르기

값이 n개일 때 점프에는 최대 n/m번, 스캔에는 최대 m번의 비교가 듭니다. 점프 크기가 작으면 스캔은 짧지만 점프가 많아지고, 크면 그 반대입니다. 합계 n/m + m은 m = √n일 때 가장 작으며, 비교는 약 2√n번입니다. 값 40개라면 최대 13번으로, 선형 탐색은 40번, 이진 탐색은 6번입니다. 점프 탐색은 한 블록보다 더 뒤로 돌아가지 않으므로, 데이터를 거꾸로 따라가기가 느릴 때 유용합니다.

자주 묻는 질문

점프 탐색은 어떻게 동작하나요?

정렬된 목록에서 m칸씩 앞으로 점프하며 각 블록의 마지막 값을 확인합니다. 그 값이 더는 목표값보다 작지 않으면 목표값은 그 블록에만 있을 수 있으므로, 그 블록을 처음부터 스캔합니다.

가장 좋은 점프 크기는 얼마인가요?

√n을 반올림한 값입니다. 점프에는 최대 n/m번, 스캔에는 최대 m번의 비교가 들고, 둘이 같을 때인 m = √n에서 합이 가장 작습니다. 최악의 경우 비교는 약 2√n번입니다.

점프 탐색이 이진 탐색보다 빠른가요?

아니요. 이진 탐색이 비교가 더 적어서 약 log₂ n번이고, 점프 탐색은 약 2√n번입니다. 그래도 데이터를 거꾸로 따라가는 비용이 클 때는 점프 탐색이 나을 수 있습니다. 뒤로 돌아가는 일이 한 번, 한 블록의 처음까지뿐이기 때문입니다.

같은 값이 여러 개면 어느 것을 찾나요?

첫 번째 값입니다. 건너뛰는 블록은 모두 목표값보다 작은 값으로 끝나므로 그보다 앞선 블록에는 일치하는 값이 없고, 스캔은 블록의 처음부터 시작합니다.

입력한 숫자가 어딘가로 전송되나요?

아니요. 탐색은 브라우저에서 실행되며, 마지막 설정은 이 브라우저의 로컬 저장소에 저장됩니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

편집기로 이동