[Python] 선형 검색

선형 검색(linear search)

직선 모양(선형으로 늘어선 배열에서 검색하는 경우에 원하는 키 값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘이다.

* 선형 검색은 순차 검색이라고도 한다.

---

배열 맨 앞부터 순서대로 원소를 스캔하는 선형 검색은 원소의 값이 정렬되지 않은 배열에서 검색할 때 사용하는 유일한 방법이다.

from typing import Sequence, Any


def seq_search(a: Sequence, key: Any) -> int:
    """시퀸스 a에서 key와 값이 같은 원소를 선형 검색"""
    for idx, val in enumerate(a):
        if val == key:
            return idx
    return -1

if __name__ == '__main__':
    num = int(input("원소의 개수를 입력하세요 : "))
    arr = [None] * num

    for i in range(num):
        arr[i] = input(f"arr[{i}]의 값을 입력하세요 : ")

    key = input("검색하고 싶은 값을 입력하세요 : ")

    result = seq_search(arr, key)

    if result == -1:
        print("값을 찾지 못했습니다.")
    else:
        print(f"{key} 값은 배열의 {result} 인덱스에 존재합니다.")

- 시퀸스 a에 대해서 for문을 이용해 모든 원소를 하나씩 확인한다.

- 만약 key와 해당 인덱스의 value가 같다면 인덱스를 반환한다.

- for문이 끝날 때까지 반환 값이 없다면, key값이 없는 것이므로 -1을 반환한다.

---

시간복잡도

- 최선의 경우 : O(1) 

- 최악의 경우 : O(n)

 

def seq_search(a: Sequence, key: Any) -> int:
    """시퀸스 a에서 key와 값이 같은 원소를 선형 검색"""
    for idx, val in enumerate(a): --- 1
        if val == key:            --- 2
            return idx            --- 3
    return -1                     --- 4

단계	복잡도
1	O(n)
2	O(n)
3	O(1)
4	O(1)

3과 4는 1번만 실행되기 떄문에 복잡도는 O(1)이다. 반면 3, 4는 최악의 경우 원소의 개수만큼 실행되기 때문에 복잡도가 O(n)이다.

n이 점점 커지만 O(n)에 필요한 계산 시간은 n에 비례해서 점점 길어진다. 라지만, O(1)에 필요한 계산 시간은 변하지 않는다.  따라서 전체 복잡도는 차원이 가장 높은 복잡도를 고려해게 된다. 그러므로 선형 검색 알고리즘의 복잡도는 다음과 같이 O(n)이 된다.

O(n) + O(n) + O(1) + O(1) = O(max(n,n,1,1) = O(n)