소개

검색 알고리즘은 대량의 데이터 중에서 특정 데이터를 찾는 방법입니다.
이번에는 대표적인 알고리즘인 선형 탐색법, 이분 탐색법, 해시법에 대해 설명합니다.

【YouTube 동영상】 선형 탐색법, 이분 탐색법, 해시법에 대해 기본 정보 기술자 시험

주문 (계산량, O)

여기서 말하는 순서는, 처리하는 수가 많아짐에 따라, 어느 정도 계산량이 많아지는 것인가의 기준입니다.
기호 O로 표기합니다.

요소의 수가 증가함에 따라 1차 함수적으로 증가하는 경우 O(n), 2차 함수라면 O(n^2)라고 표기합니다.
또, 아무리 요소가 늘어나도, 정수회로 처리가 끝나는 경우는 O(1)가 됩니다.

선형 탐색 방법 O(n)

선형 탐색 방법은 순차적으로 요소를 확인하는 방법입니다.
요소수가 n이면, 최악 전부 확인하면, 목적의 요소가 발견되므로, O(n)가 됩니다.

예를 들어, 다음 7개의 숫자에서 특정 숫자를 찾으려고 합니다.
왼쪽에서 1을 찾을 때까지 3회 확인 작업이 필요합니다.

8 4 1 3 5 9 6

이분 탐색법 O(log n)

이분 탐색법은 요소가 마지막 하나가 될 때까지 요소를 반으로 해 나가는 확인 방법입니다.
정렬과 함께 사용하면 위력을 발휘합니다 (정렬은 별도 기사에서 설명합니다!).

예를 들어, 다음과 같이 정렬된 7개의 숫자에서 11을 찾습니다.

우선, 중간의 수치를 보겠습니다.
7은 11보다 작기 때문에 7보다 왼쪽의 숫자는 무시합니다.

2 4 5 7 8 10 11 

다음 중간의 숫자는 10입니다.
10은 11보다 작기 때문에 왼쪽의 숫자를 무시합니다.

8 10 11

숫자가 하나뿐이었고 11을 찾을 수있었습니다.

11

이 이분 탐색 방법의 계산량은 log n입니다.

계산량 계산

계산량은 1개의 요소를 몇회 2배로 하면, 전체 요소수와 일치할까라고 생각합니다.

1 -> 2 -> 4 -> 8 -> 16 -> 32 -> ...

전체 요소수가 8이면 3회 2배하면 일치합니다(2^3 = 8).
일반화하면, 모든 요소수 n에 대해, m회 2배하면 일치합니다.

n = 2 ^m

로그를 취하면 계산량이 구해집니다 (바닥 2).

m = log n

해시법 O(1)

해시 방법은 해시 함수를 사용하여 탐색하는 방법입니다.
데이터를 저장하기 전에 수치화한 다음 수치화된 위치에 데이터를 저장합니다.
調べたい値 -> 対応表を確認 -> データにアクセス 로 진행하므로, 데이터량에 관계없이 계산량은 증가하지 않습니다.

요약

이번에는 대표적인 탐색 알고리즘을 소개했습니다.
이분 탐색 쪽으로 나온 소트에 대해서는, 다른 기사로 소개합니다!

트위터 이나 youtube 에서의 코멘트도 기다리고 있습니다!