탐색 알고리즘의 설명으로 가장 옳지 않은 것은? | [7급 서울시 자료구조론] 26년 1회차 기출문제 상세 페이지

1[7급 서울시 자료구조론] 26년 1회차
탐색 알고리즘의 설명으로 가장 옳지 않은 것은?
1
순차 탐색의 시간 복잡도는 O(n)O(n)이다.
2
색인 순차 탐색에서 인덱스 테이블의 크기가 줄어들면, 배열의 인덱스를 저장하는 간격이 커지므로 배열에서 탐색해야 하는 범위도 커진다.
3
색인 순차 탐색의 시간 복잡도는 O(m+m/n)O(m+m/n)이다. (단, nn: 배열의 크기, mm: 인덱스 테이블의 크기)
4
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21과 같이 정렬되었을 때 이진 탐색으로 찾고자 하는 수가 17일 경우, 비교 횟수는 2번이다.
해설

색인 순차 탐색의 시간 복잡도는 O(m+n/m)O(m+n/m)이므로, O(m+m/n)O(m+m/n)이라는 설명이 옳지 않다.

크기 mm인 인덱스 테이블을 먼저 탐색한 뒤, 찾은 구간(크기 약 n/mn/m)을 배열에서 순차 탐색하기 때문이다.

  • 순차 탐색은 원소를 처음부터 하나씩 비교하므로 O(n)O(n)이다.
  • 인덱스 테이블이 작아지면 인덱스 간격이 커져 배열에서 탐색할 구간이 넓어진다.
  • 11개 원소의 이진 탐색은 중간값 11과 비교한 뒤 오른쪽 구간의 중간값 17과 비교하므로 비교는 2회이다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 서울시 자료구조론] 26년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 서울시 자료구조론 기출문제 암기장 전체 보기