1_4 자료구조와 알고리즘의 이해

※  순차 탐색 평균적 경우 시간 복잡도

 

가정 1. 탐색 대상이 배열에 존재하지 않을 확률 50%

가정 2. 배열 첫 요소부터 마지막 요소까지 탐색 대상 존재 확률 동일!

- 탐색 대상이 존재하지 않는 경우의 연산 횟수는 n

- 가정 2에 의해서 탐색 대상이 존재하는 경우의 연산횟수는 n/2

 

정리.

 

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

n = 데이터의 갯수

1/2 = 존재하지 않을 확률 50%

n/2 = 최악과 최상의 중간

 

따라서, T(n) = n * 1/2 * n/2 * 1/2