[파이썬 자료구조 3단원] - 검색알고리즘

검색알고리즘

검색알고리즘이란 데이터집합에서 원하는 값을 가진 원소를 찾아내는 것이다.

 

검색알고리즘 종류

선형검색 : 무작위로 늘어놓은 데이터 집합에서 검색을 수행한다.

이진검색 : 일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색을 수행한다.

해시법 :  추가, 삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색을 수행한다.

 

 

선형검색

선형검색이란 맨앞부터 스캔하여 순선대로 검색하는 알고리즘이다.

 

이진검색

이진검색 알고리즘을 사용하려면 정렬되어 있어야 한다.

이진은 '반으로 쪼개다' 라는 의미이다.

1. 정 가운데 숫자가 찾고자 하는 target숫자보다 큰지 작은 지를 비교해 보면된다.
2. n(중앙숫자) > target 이면 왼쪽으로 검색을 진행하고
3. n(중앙숫자) < target 이면 오른쪽으로 검색을 계속 진행한다.

이진검색이란 목표 숫자(target)를 검색해서 찾을때 까지 1번부터 3번 까지의 과정을 반복하는것이다.

 

단 이진검색에서 원소를 추가할때에는 정렬이 되어있기 때문에 선형검색의 경우보다 시간이 더 오래 걸린다.

하지만 검색에서 효율이 너무나 월등하고 좋기 때문에 아주 많이 쓰인다.

 

복잡도

 

시간복잡도(time complexity) : 실행하는 데 필요한 시간을 평가한다.

초,분 이런것이 아니라 알고리즘이나 데이터 구조를 수행하기위한 단계를 의미한다.

 

공간복잡도(space complexity) : 메모리(기억 공간)와 파일 공간이 얼마나 필요한지를 평가한다.

 

 

해시법

해시값 : 배열의 키(원소의 값)을 원소 개수로 나눈 나머지를 의미한다.

해시테이블 : 해시값을 인덱스로 하여 원소를 새로 저장한 배열을 의미한다.

버킷 : 해시테이블에서 만들어진 원소를 의미한다.

해시 충돌 :  저장할 버킷이 중복되는 현상을 의미한다.

 

해시충돌이 발생하는경우 대처방안

-체인법 : 같은 해시값 데이터를 연결 리스트로 연결하는 방법

-오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시하는 방법