순차 탐색

정렬 x 순차 탐색(O(n))

정렬 o 순차 탐색(O(n)) : 키 값보다 큰 값은 찾을 필요가 없다

색인 순차 탐색(O(m+n/m))

(m : 인덱스 행의 길이, n: 배열의 크기)

이분 탐색(O(logn))

이분 탐색 알고리즘 설명

해싱(O(1)) : 산술적인 연산으로 키가 있는 위치를 계산하여 탐색하는 방법

해시함수 : 키값의 위치를 계산하는 함수

→ 해시 테이블에 고르게 분포할 수 있도록 주소를 만들어야 한다

• 제산 함수 : 나머지를 키값으로 정하는 해시함수

동거자 : 한 버킷에 저장된 서로 다른 키값들

충돌 : 키값이 서로 다름에도 버킷주소가 같은경우 → 슬롯이 비었으면 동거자관계로 키값 저장