평균적인 경우의 시간복잡도를 구할때의 가정 2가지 입니다. 1. 탐색 대상이 배열에 존재하지 않을 확률을 50%라고 가정 2. 배열의 첫 요소부터 마지막 요소까지 탐색 대상이 존재할 확률은 동일하다.
가정 1부터 연산횟수를 계산해 보겠습니다. (존재하는 경우와 존재하지 않는 경우)
* 배열에 탐색 대상이 존재하지 않는 경우 데이터의 수가 n개일 때, 총 n번의 비교연산을 진행해야 합니다 (총 n 번의 비교연산이 끝나야 비로소 탐색 대상이 존재하지 않음을 판단할 수 있다.) 따라서 배열에 탐색 대상이 존재하지 않는 경우의 연산횟수는 다음과 같습니다.
> 탐색 대상이 존재하지 않는 경우의 연산횟수 : N
* 배열에 탐색 대상이 존재하는 경우 나머지 50%의 확률에 해당하는 탐색 대상이 존재하는 경우의 연산횟수를 구합니다. 이 경우는 가정 2에 의해서 다음과 같이 계산이 됩니다.
> 탐색 대상이 존재하는 경우의 연산횟수 : N/2
* 위의 식의 예 - 데이터가 담긴 길이가 7인 배열이 있습니다. 그런데 각각의 배열요소에 탐색 대상이 존재할 확률이 동일하므로(가정 2의 의해) 이 배열을 대상으로 총 7회의 탐색이 진행된다면 모든 위치에서 한 번씩 탐색이 되어야 합니다.
따라서 각 위치에서 탐색 대상을 찾았을 때 비교연산횟수는 다음과 같이 정리할 수 있습니다.
위 그림에서 가장 위에 그려놓은 것이 배열이고 각 배열요소의 위치에서 탐색 대상이 찾아질 때 진행이 되는 비교연산의 횟수가 아래에 점으로 표시되어 있습니다.
즉 첫번째 요소에서 탐색 대상이 발견되면 1회의 비교연산을 진행하게 되고, 마지막 위치에서 탐색 대상이 발견되면
총 7회의 비교연산을 진행하게 됩니다. 이렇게 보면 각 요소별 평균적 비교연산의 횟수가 n/2 임을 알 수 있다.
그런데 사실 n/2보다는 몇 번 더 연산을 할 수 있습니다.
하지만 이 경우는 근사치 계산을 합니다. 이 근사치 계산을 수행함으로써 수식이 간결해지고 또 배열의 길이가 길어질수록 근사치 계산결과에 더 가까워지기 때문입니다.
결론을 내리기위해 평균적인 경우의 비교연산횟수를 정리할게요.
- 탐색 대상이 존재하지 않는 경울의 연산횟수 N - 탐색 대상이 존재하는 경우의 연산횟수 N/2
탐색 대상이 배열에 존재하지 않는 경우와 존재하는 경우의 확률이 각각 50%이니 (가정 1에 의해서) 다음과 같이 이 둘을 하나의 식으로 묶습니다. n * 1/2 * n/2 * 1/2 = 3/4*n 1/2씩 곱해서 더한 이유는 탐색 대상이 존재하지 않을 확률과 존재할 확률이 각각 50%이기 때문입니다. 따라서 순차탐색 알고리즘의 평균적인 경우의 시간 복잡도 함수는 T(n) = 3/4*n 입니다.
