알고리즘 자료구조 - 3

3장
 - 선형검색, 이진검색
 - 어떤 목적을 이루기위한 알고리즘이 다양하게 있을 때, 용도, 목적, 실행속도, 자료구조등을 고려하여 알고리즘을 선정한다

1)
key: 데이터 집합에서 검색을 위해 기준으로 잡는 항목
검색방법의 예: 배열검색, 선형리스트 검색, 이진트리 검색
 ** 배열검색은 검색이 빠르지만, 데이터를 추가하기 위한 비용은 많이 든다

배열검색에서 사용하는 알고리즘
 - 선형검색 : 무작위 데이터 배열에서 검색수행
    ** 선행검색은 무작위로 정렬되어 있는 데이터 배열에서 검색을 수행하는 유일한 방법이다
 - 이진검색 : 정렬되어 있는 데이터 배열에서 빠른 검색 수행
 - 해시법 : 추가, 삭제가 자주일어나는 데이터 배열에서 빠른 검색 수행
     ex) 체인법: 같은 해시 값의 데이터를 선형리스트로 연결하는 방법
     ex) 오픈 주소법: 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법

2)
선형검색(linear search)
 - 순차검색(sequential search)이라고도 함
 - 배열에서 원하는 키 값을 가지는 요소를 찾기 위해 첫번째 요소부터 끝 요소까지 순차적으로 검색하는 방법
 - 종료조건: 검색 성공, 배열끝까지 검색


보초법
 - 선형검색에서 종료조건 검사비용을 줄이는 방법
 - 검색전 찾하고자 하는 키값을 제일 끝 요소에 저장(이때 끝에 저장하는 키값을 보초(sentinel)이라고 한다)
 - 종료조건을 검색 성공만 남긴다
 - 이렇게 하면 배열에 저장하는 데이터는 1만큼 더 늘어나지만 종료조건이 2개에서 1개로 줄어든다

3)
이진검색(binary search)
 - 데이터가 정렬되어 있어야 한다
 - 전체 배열에서 중간 요소를 검색, 검색 키 값이 중간 값보다 크면 중간요소+1~끝 요소 범위를, 키 값이 중간 값보다 작으면 처음~중간요소-1 범위를 검색
 - 반복
   ** 이진검색은 검색을 반복할 때마다 검색범위가 절반으로 줄어들며, 시간 복잡도는 log n이다


4)
복잡도
 - 시간복잡도(time complexity) : 실행에 필요한 시간을 평가한 것, 단, 절대적 시간(sec)이 아닌 해당 알고리즘이 실행시간, 즉 실행단계를 의미한다.
     ** 알고리즘에서의 데이터량에 따른 시간 복잡도를 O(n), Order n 라고 표현한다
 - 공간복잡도(space complexity) : 기억영역과 파일공간이 얼마나 필요한가를 평가한 것
 - 2개 이상의 복잡도로 구성된 알고리즘의 전체 시간 복잡도는 차원이 더 높은 쪽의 복잡도로 표현한다(즉, 시간이 더 걸리는 쪽으로 표현한다)
 - 시간복잡도의 대소관계
    : 1 < log n < n < nlog n < n^2 < n^3 < n^k < 2^n

5)
bsearch 함수
 - 정렬된 배열에서 검색하는 함수
 - 헤더: stdlib.h
 - 함수 형태: void *bsearch(const void *key, const void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *))
 - 반환값 : 키값과 일치 시 일치하는 요소를 가리키는 포인터 반환, 일치하는 요소가 없으면 NULL 반환
 - 설명: 첫번째 인수는 검색할 키값, 부번째인수는 배열포인터, 세번째인수는 배열 요소수, 네번째 인수는 요소크기, 다섯번째 인수는 비교함수
 - 비교함수: 첫째인수와 둘째 인수를 비교, 1 < 2 이면 음수, 1 == 2 이면 0, 1 > 2 면 양수를 반환



6)
함수 포인터
 - 함수를 가리키는 포인터
 - 표현 : 반환자료형 (*함수명)(매개변수)
 - 함수이름은 그 함수에 대한 포인터와 동일한 기능을 가진다
 - 매개변수로 입력받은 함수(매개변수로 함수를 입력받기 위해 함수포인터로 입력받은 함수)는 컴파일할 때가 아니라 프로그램 실행시 호출할 함수를 결정한다
   (그 전까지는 어떤 함수를 매개변수로 입력할지 모르기 때문에)
 - 매개변수 선언에서 함수포인터를 사용시 (*함수명)의 *와 ()를 생략하여 사용할 수 있다.