파이썬 순차탐색 알고리즘 sequential search #7

파이썬 순차탐색 알고리즘 sequential search #7

 

안녕하세요.

 

오랜만에 파이썬을 이용한 알고리즘 학습 포스팅을 합니다.

 

이번 챕터는 매우 심플! 매우 간단! 한 알고리즘입니다.

 

리스트에 값이 있고, 원하는 값을 첫 번째 자료부터 비교하면서 그 위치 값을 리턴해주는 알고리즘입니다.

 

순차 탐색이라고 하고, sequential search라고 영어로는 표현하면 되겠습니다.

 

바로 그럼 시작해 보겠습니다.

위 그림처럼 처음부터 18을 찾아 헤매기 시작합니다.

 

그렇게 번지수 2번에 도착하여 18을 찾아 해당 값을 리턴하고,

 

만약 끝까지 찾지 못하였다면 -1을 리턴하는 알고리즘입니다.

 

파이썬으로 표현해 보겠습니다.

# 리스트에서 특정 숫자 위치 찾기
# 입력: 리스트 a, 찾는 값 x 
# 출력: 찾으면 그 값의 위치, 찾지 못하면 -1

def search_list(a, x):
    n = len(a)  # 입력 크기 n
    for i in range(0, n):  # 리스트 a의 모든 값을 차례로
        if x == a[i]:      # x 값과 비교하여
            return i       # 같으면 위치 돌려줍니다.

    return -1   # 끝까지 비교해서 없으면 -1을 돌려줍니다.

v = [17, 92, 18, 33, 58, 7, 33, 42]
print(search_list(v, 18))   # 2(순서상 세 번째지만, 위치 번호는 2)
print(search_list(v, 33))   # 3(33은 리스트에 두 번 나오지만 처음 나온 위치만 출력)
print(search_list(v, 900))  # -1(900은 리스트에 없음)

자 , 그럼 이 순차 알고리즘으로 원하는 값을 찾으려면 비교를 몇 번 해야 할까요? 아마, 찾으려는 숫자가 어디에 있느냐에 따라 다르겠죠?

 

만약 10개의 값이 담겨있는 리스트에서 없는 숫자를 찾으려면 10번 비교를 하고 나서 -1을 리턴할 것입니다. 반대로 어떤 값을 찾을 때 그 값이 리스트의 0번지에 있다면? 한 번의 비교로 값을 찾아낼 수도 있고요.

 

이런 상황에서 우리는 계산 복잡도를 어떻게 구 할 수 있을까요? 이처럼 변수에 따라 계산 횟수가 달라지는 이런 상황에서는 최선의 경우와, 평균적인 경우, 그리고 최악의 경우로 나누어 생각해 보기도 합니다.

 

따라서 보수적인 관점에서 이 알고리즘의 계산 복잡도는 n번의 계산이 필요하며, 계산복잡도 O(n)이라고 표현할 수 있습니다.

 

DB적인 관점에서 보았을 때 이 알고리즘은 정렬되어 있지 않기 때문에 full scan을 하는 방법이라고 표현할 수 있습니다.

 

다음 시간에는 정렬에 관한 알고리즘을 배워보도록 하겠습니다.

 

감사합니다.

 

 

by.sTricky