3장 정리 - 검색 알고리즘

2021-12-19

배열 검색 - 선형검색, 이진검색, 해시를 사용한 검색

복잡도 (complexity)

알고리즘을 평가하는 척도.

시간 복잡도 (time complexity) : 알고리즘을 수행하는 데 필요한 시간 평가
공간 복잡도 (space complexity) : 메모리와 파일 공간이 얼마나 필요한지 평가

Big-O 표기법

복잡도를 평가 시 사용하는 표기법.
최악의 경우를 고려하는 표기법이다.
종류.

O(1) : 데이터 입력량에 무관하게 실행시간이 일정함 (상수 시간)
O(n) : 선형 알고리즘, 데이터 입력량에 비례하여 실행시간이 증가
O(log n) : 로그형 알고리즘
O(n log n) : 선형-로그형 알고리즘
O(n^2) : 2차 알고리즘, 데이터 입력량의 제곱에 비례하여 실행시간이 증가
O(2^n) : 지수형 알고리즘, 데이터 입력이 추가될 때마다 실행시간이 2배로 증가
O(n!) : 팩토리얼형 알고리즘, 데이터 입력 추가될 때마다 실행시간이 n배로 늘어남

선형 검색 (linear search)

원하는 값을 가지는 원소가 나올 때 까지, 배열의 처음부터 끝까지 검색하는 방법. 순차검색(sequential search)으로도 불린다.

선형 검색의 종료 조건.

값을 찾지 못하고 배열의 끝을 지나간다.
검색하는 값과 같은 원소를 찾는다.

li = [1,4,7,8,22,35]
index=0
key = 22

def seq(arr,key):
    index=0
    while True:
        if index==len(arr):
            return -1
        if arr[index] == key:
            return index
        index+=1


res = seq(li,key)

if res==-1:
    print('찾는 값 없음')
else:
    print(f'찾는 값은 li[{res}]에 있음')

선형 검색의 시간복잡도는 O(n)이다.

보초법 (sentinel method)

선형 검색에서 검색을 종료하기 위해 2가지의 조건을 검사한다.
보초법은 선형검색에서 종료 조건을 검사할 때 발생하는 비용을 줄이기 위한 방법이다.

방법.
배열 마지막에 검색하고자 하는 값(키)을 저장한다. 저장하는 값을 보초(sentinel)이라고 부른다.
순차적으로 검색하며 키값이 나오면 반복을 종료한다.
반복 종료했을 때 인덱스값이 보초값을 추가한 배열의 길이와 같다면 검색에 실패한 것,
그렇지 않은 경우 검색에 성공한 것이다.
이 경우 선형검색의 종료 조건인 1번이 사라지게 되기 때문에,
판단 횟수가 절반으로 줄어든다.

import copy

def sentinel_seq(arr, key):
    copied_arr = copy.deepcopy(arr) #[1,4,7,8,22,35,찾으려고하는 값]
    copied_arr.append(key)
    index=0

    while True:
        if copied_arr[index] == key:
            break
        index+=1
    return -1 if index==len(arr) else index


li = [1,4,7,8,22,35]
k = 35  #값을 바꿔보세요.
res = sentinel_seq(li,k)

if res==-1:
    print('찾는 값 없음')
else:
    print(f'찾는 값은 li[{res}]에 있음')

이진 검색 (binary search)

배열을 반씩 잘라 검색하는 방법
주의 : 이진검색은 배열이 정렬되어 있어야 사용 가능하다

이진 검색은 한 단계마다 배열의 반을 날린다.
배열의 길이가 n일 때, 찾는 값이 없는 경우 수행하는 이진 검색의 횟수 = log n (밑이 2)

이진 검색의 시간 복잡도는 O(log n)이다.

해시법 (hashing)

key를 해시함수를 통해 해시값으로 변환한 후 해시값을 배열의 인덱스로 사용한다
해시테이블의 원소를 버킷이라고 한다

해시 충돌 (hash collision)

서로 다른 두 입력값에 대해 해시 함수가 동일한 출력값을 내보내는 것
해시 테이블에서 버킷이 중복되는 경우

해시 충돌을 해결하는 방법으로 체인법, 오픈 주소법이 있다

체인법 (chaining)

해시값이 같은 데이터를 연결리스트를 사용하여 연결하는 방법
해시테이블에는 인덱스를 해시값으로 하는 데이터가 저장된 노드의 주소값을 참조한다

오픈 주소법 (open addressing)

=closed hashing, linear hashing
데이터 추가 시 해시 충돌이 일어나면 재해싱(rehashing)을 하여 빈 버킷을 찾는다
문제점 : 데이터 삭제 시

오류 발생 방지를 위해 버킷에 3가지의 상태를 부여한다.

데이터가 저장된 상태
비어있는 상태
삭제 완료

chanheelee913