모두의 알고리즘 문제07. 순차 탐색

def search_list (a, x):  # 리스트a, 찾는값x
    n=len(a)
    for i in range(0, n):  # a[0]부터 a[n-1]까지 탐색.
        if a[i]==x:
            return i  #값을 찾으면 리스트 내의 위치를 반환함
    return -1

v=[17, 32, 21, 2, 32, 52, 12]

print(search_list(v, 17)) #0
print(search_list(v, 12)) #6
print(search_list(v, 124)) #-1

이 알고리즘을 보수적인 관점에서, 최악의 경우로 분석하면 리스트 길이가 n일 때 비교가 최대 n번 필요하므로 계산 복잡도는 O(n)이다.

 

물론 찾는 값이 리스트의 맨 처음에 있을 수 있고 중간에 있을 수도 있지만 일단 보수적인 관점에서 최악의 경우를 상정하고 분석한다면 O(n)이 된다.

 

하지만 이 분석방법이 '정렬'과 만나게 된다면 더 효율적이게 된다고 한다.