01 검색 알고리즘
- 배열 검색을 다룸
01-1 선형 검색 (linear search) -> O(n)
: 무작위로 늘어놓은(선형) 데이터 집합에서 검색을 수행(가장 기본적인 배열 검색 알고리즘)
▶ 선형 검색의 종료조건
- 검색 실패 # n+1
- 검색 성공 # n
i = 0
"""sequence a에서 key와 값이 같은 원소를 선형 검색"""
while True:
if i == len(a):
# 검색 실패
if a[i] == key:
# 검색 성공
i += 1 # index 증가
- 값이 정렬되지 않은 배열에서 검색할 때 사용하는 유일한 방법
01-1 추가) 보초법(sentinel method)
: 종료 조건 검사 비용(cost)를 반으로 줄이는 방법
- 종료 조건1이 while문에서 삭제될 수 있음!
01-2 이진 검색 (bineary search) -> O(log n)
: 일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색을 수행
- 정렬된 데이터!
pl: 맨 앞 원소 인덱스
pc: 중앙 원소 인덱스
pr: 맨 끝 원소 인덱스
▶이진 검색의 종료 조건
- a[pc]와 key가 일치하는 경우
- 검색 범위가 더 이상 없는 경우
def bin_search(a: Sequence, key: Any) -> int:
"""시퀀스 a에서 key와 일치하는 원소를 이진 검색"""
pl = 0 # 검색 범위 맨 앞 원소의 인덱스
pr = len(a) - 1 # 검색 범위 맨 끝 원소의 인덱스
while True:
pc = (pl + pr) // 2 # 중앙 원소의 인덱스
if a[pc] == key:
return pc # 검색 성공
elif a[pc] < key:
pl = pc + 1 # 검색 범위를 뒤쪽 절반으로 좁힘
else:
pr = pc - 1 # 검색 범위를 앞쪽 절반으로 좁힘
if pl > pr:
break
return -1 # 검색 실패
필요한 평균 비교 횟수 = 평균 log n
복잡도(complexity)
- 시간 복잡도: 실행하는 데 필요한 시간
- 공간 복잡도: 메모리(기억 공간)와 파일 공간이 얼마나 필요한 지
01-3 해시법 (hashing)
: 추가 or 삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색을 수행
'데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것
+검색, 추가, 삭제 효율적 수행
- 원소 값(key)
- 해시값(hash value): 원소값 % 13
- hash table: 해시값을 인덱스로 하여 원소를 새로 저장
- hash function: 키를 해시값으로 변환하는 과정
해시 충돌
일반적으로 키와 해시값은 다 대 1(n : 1)이다.
저장할 버킷이 중복되는 현상 -> 충돌(collision)
+ 버킷(bucket): 해시 테이블에서 만들어진 원소
해시값이 같은 데이터 저장하기(해시 충돌 해결법)
1) 체인법 (chaining) = 오픈 해시법(open hasing)
: 같은 해시값 데이터를 연결 리스트로 연결
2) 오픈 주소법
: 데이터를 위한 해시값이 충돌할 때 재해시(rehash)
