탐색 알고리즘

우리가 늘상 사용하는 index(list, data)는 과연 어떤 원리로 동작하는 것일까?

기본적으로 어떠한 리스트에서 데이터의 위치를 찾는 것을 목표로 동작해야한다.

 

즉, 데이터의 값이 어디있는지 찾고, 그 값의 인덱스를 리턴해주어야 한다.

 

우리는 보통 무언가를 찾을 때 처음부터 쭈욱~ 찾아보거나 어떤 기준을 잡고 살펴보기 시작한다.

한 뭉텅이씩 눈에 들어오는 양만큼 그룹을 묶어서 찾는다거나, 절반을 먼저보고 나머지를 본다거나...

 

컴퓨터도 똑같이 리스트에서 데이터를 찾을 때, 처음부터 쭉 살펴보거나 어떠한 기준을 가지고 리스트를 살펴보기 시작한다.

 

가장 기본적인 탐색 방법으로 선형 탐색과 이진 탐색에 대해서 살펴보자.

 

선형 탐색

선형 탐색은 말 그대로 리스트를 linear하게 살펴보면서 데이터의 위치를 찾는 탐색 방식이다.

아래 코드를 살펴보자.

def linear_search(element, some_list):
    
    for i in range(len(some_list)):
        if element == some_list[i]:
            return i
        
            
    return None

 

1. for 문을 통해서 리스트의 처음부터 끝까지 살펴볼 준비를 한다.
2. 만일, 파라미터로 들어온 데이터가 리스트에 존재하면,
3. 인덱스를 리턴해준다.
4. 처음부터 끝까지 살펴보았음에도 불구하고 찾지 못한다면 찾지 못했다는 의미로 None을 리턴한다.

 

시간복잡도는?

 

알고리즘을 평가할 때에는 최악의 경우를 상정해놓고 평가한다. (Big-O notation)

위 알고리즘에서 최악의 경우는 None을 리턴하는 경우이며, 이때 시간 복잡도는 list의 길이에 비례한다.

즉, T(n) = n 이다. (O(n))

 

이진 탐색

이진 탐색은 선형 탐색과 달리 정렬된 리스트를 필요로 한다. 

왜냐면 컴퓨터가 기준 잡기를, 우리가 파라미터로 넘겨준 데이터와 리스트의 데이터를 크기순서를 바탕으로 추적해 범위를 좁혀나가기 때문이다.

 

범위를 좁힌다는 뜻은, 우리가 살펴볼 index를 줄여나간다는 것이고 이를 위해선

1. 시작점
2. 끝점
3. 기준점

이 세가지가 필요하다.

 

이 세 개의 지표중에서 기준점은 데이터의 위치를 추정할 수 있도록 도와주는 역할을 한다.

 

def binary_search(element, some_list):
    start = 0
    end = len(some_list)-1
    while True:
        idx = (min_ + end) //2
        if element == some_list[idx]:
            return idx
        elif element > some_list[idx]:
            start = idx
            if element == some_list[idx+1]:
                return idx+1
        elif element < some_list[idx]:
            end = idx
        
        if start == end:
            return None

 

이진 탐색의 이름을 보면, 절반을 기준으로 탐색을 진행한다는 뜻이 있는데, 이를 위해 idx를 중간값으로 설정해준다.

1. 파라미터 데이터와 리스트의 중간값이 같을 때 중간값 인덱스를 리턴해준다
2. 파라미터 데이터가 리스트의 중간값보다 클 때 시작점 인덱스를 중간값 인덱스로 해주어서 범위를 좁혀준다
3. 파라미터 데이터가 리스트의 중간값보다 작을 때 끝점 인덱스를 중간값 인덱스로 해주어서 범위를 좁혀준다
4. 2,3을 진행하면서 시작점 인덱스와 끝점 인덱스가 같아진다면, 결국에 리스트에 찾는 값이 없는 것이므로 None을 리턴해준다.

 

시간복잡도는?

 

매 탐색을 진행할 때 마다 조사해야할 범위가 절반씩 줄어드므로

O(log_2[n])

 

첫 시행 후 : N/2
두 번째 시행 후 : 1/2 * N/2
세 번째 시행 후 : 1/2*1/2*N/2
.
.
.
k 번째 시행 후 : (1/2)^(k)*N

시행 횟수가 k 이므로, K → log_2[n]
따라서 O(log_2[n])

 

 

 

2021-10-16