CH1-2 알고리즘의 성능분석 방법(3)
가정1 : 탐색 대상이 배열에 존재하지 않을 확률 50%
가정2 : 배열 첫 요소부터 마지막 요소까지 탐색 대상이 존재할 확률은 동일하다.
즉 50%확률로 배열 내 타겟이 존재할때(횟수는 $n$번, 확률은 $1\over2$)와 타겟이 존재하지 않을때 경우의 횟수를 더하면 됨.
50%확률로 타겟이 존재할때 평균 연산횟수는?
이 경우 나는 다음과 같은 방식으로 결론을 이끌어 냈음.
길이가 $n$일때, 1번째에 타겟이 있을때, 2번째에 타겟이 있을때… $n$번째에 타겟이 있을때.. 전체 탐색 횟수분의 타겟을 찾을때의 탐색횟수는 $1\over 2$이다.
이 그림을 참고하자.
(사실 정확히 $1\over 2$는 아니다. 하지만 $n$이 충분히 커지면 $1\over 2$에 수렴함)
따라서 평균적인 탐색 횟수는 $n \times {1\over2}$라고 생각할 수 있음. (여기가 부정확한데.. 일단은 이렇게 넘어가고 나중에 확률에 대한 이해가 더해지면 다시 돌아보자. 일단 저자는 이런식으로 짚고 넘어가는 듯 함. 이걸 정확하게 하는게 메인은 아니니까.)
그래서 평균적인 경우의 시간복잡도는 다음과 같다.
CH1-2 알고리즘의 성능분석 방법(4)
이진탐색 알고리즘을 소개한다.
이진 탐색 알고리즘(Binary Search Algorithm)은 주어진 데이터가 배열 내에서 정렬(array)되어 있어야 한다는 제약이 있다.