탐색 알고리즘

읽기 전 참고사항>> 본 포스팅은

『윤성우의 열혈 자료구조 』

를 참고했다.

 

 

 

탐색 알고리즘의 성능을 평가하는 방법:

 

==연산의 횟수가 얼마나 큰지 분석한다.

 

순차 탐색 알고리즘

최악의 경우

데이터의 수가 n개일 때, 최악의 경우에 해당하는 연산횟수는 n이다.

즉 최악의 경우 O(n)

 

평균적인 경우

평균적인 경우의 연산횟수 계산을 위해서 다음과 같이 두 가지 가정을 한다.

 

1. 탐색 대상이 배열에 존재하지 않을 확률은 50퍼센트이다.

2. 배열의 첫 요소부터 마지막 요소까지 탐색 대상이 존재할 확률은 동일하다.

 

배열이 탐색 대상에 존재하지 않는 경우 n

배열이 탐색 대상에 존재하는 경우         n/2(각 요소별 평균 비교연산횟수)

 

그런데 탐색 대상이 배열에 존재하지 않는 경우와 존재하는 경우의 확률이 각각 50퍼센트이니 둘을 하나의 식으로 묶어야 한다.

 

1/2*n+1/4*n=3/4*n

즉 T(n)=3/4n

이진 탐색 알고리즘

이진 탐색은 탐색의 대상을 반씩 떨구어 내는 알고리즘이다.

배열을 대상으로 이진 탐색 알고리즘을 수행하기 위해서, 배열에 저장된 데이터들은 정렬되어 있어야 한다.

O(lon2n)

 

 
 
int search(int* arr, int first, int last, int target)
{
    if (first > last) return -1;
 
    int mid = (first + last) / 2;
    if (arr[mid] == target) return mid;
    else if (target < arr[mid]) return search(arr, first, mid - 1, target);
    else return search(arr, mid + 1, last, target);
 
}