이진탐색 알고리즘의 시간 복잡도 그리고 빅-오 표기법
'윤성우의 열혈 자료구조'의 Ch.1 을 보면서 요약한 내용입니다. 알고리즘의 시간복잡도 (Time Complexity)는 최악의 경우를 기준으로 계산한다. [EX] 이진탐색 알고리즘의 시간복잡도 계산해보기 n개의 데이터에 대해 이진탐색을 진행할 때, 최악의 경우는 데이터가 한 개 남을 때 까지 찾는 경우이다. 연산 횟수를 표현하면 다음과 같다. n이 1이 될 때까지 2로 나눈 횟수 : k 데이터가 한 개 남았을 때 마지막으로 비교연산 1회 진행 시간 복잡도 계산해보기 $ T(n) = k + 1 $ $k$ 구하기 n 이 1이 될 때까지 2로 나눈 횟수가 k 라면 식으로 다음과 같이 표현할 수 있다. $ n \times (\frac{1}{2})^{k} = 1 $ $ n \times 2^{-k} = 1 $ ..
공부기록/자료구조
2020. 12. 7.
