03.검색 알고리즘-(2)

검색에 대한 세가지 기법
1.배열 검색
2.선형 리스트 검색
3.이진검색트리 검색

 

배열 검색
1.선형 검색: 무작위로 늘어놓은 데이터 모임에서 검색을 수행
2.이진 검색: 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행
3.해시법: 추가, 삭제가 자주 일어나는 데이커 모임에서 아주 빠른 검색을 수행
  -체인법: 같은 해시 값의 데이터를 선형 리스트로 연결하는 방법
  -오픈 주소법: 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법

 

선형 검색(linear search)
배열에서 검색하는 가장 기본적인 알고리즘
선형검색: 요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색(=순차검색(sequential Search))

 

검색 종료되는 2가지
-검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우(검색 실패)
-검색할 값과 같은 요소를 발견한 경우(검색 성공)

보초법: 검색 종료조건 비용을 50%줄이는 방법
-검색하기 전에 검색하고자 하는 키 값을 맨 끝 요소에 저장(이때 저장하는 값을 보초(sentinel)이라고 함.

  (검색 실패가 없음)

 

복잡도: 알고리즘의 성능을 객관적으로 평가하는 기준

-시간 복잡도(time complexity): 실행에 필요한 시간을 평가한 것

-공간 복잡도(space complexity): 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

-전체 복잡도: 2개 이상의 복잡도로 구성된 알고리즘(더 높은 쪽의 복잡도를 우선시 함)

 

이진 검색법을 이용하면 선형검색보다 검색할 요소의 범위를 절반씩 좁 힐 수 있음.

 

※문자열정렬, 자연정렬

-문자열 정렬: 1 - 10 - 100 - 2 - 21 ...

-자연 정렬: 1 - 2 - 10 -21 - 100 ...

사람은 자연 정렬이 자연스럽지만 컴퓨터는 문자열 정렬을 함..