[자료구조] 1.2 알고리즘의 성능분석 방법 (4)

알고리즘의 성능분석 방법 (4)

이진 탐색 알고리즘

최악의 경우 시간 복잡도

8을 1이 되도록 나눠야 하는 수 : 3회 = 비교연산 3회 남은 데이터가 1개일 때 = 비교연산 1회

따라서

n이 1이 되도록 나눠야 하는 수 : k회 = 비교연산 k회 남은 데이터가 1개일 때 = 비교연산 1회

T(n) = k + 1

**여기서 k = n을 1로 만들기까지 나눠야하는 횟수 **

n \times (\frac{1}{2})^{k} = 1

결론

T(n) =log_{2}n + 1

1은 시간복잡도에 영향력을 끼치지 않으므로 생략

T(n) =log_{2}n

참고

• 윤성우의 열혈 자료구조
  
• 윤성우의 열혈 자료구조 강의