컴퓨터/자료구조
[자료구조 / C++] 이진 탐색 알고리즘 시간복잡도와 순차 탐색 알고리즘과의 비교 (Binary Search Algorithm Time Complexity and Comparison with Linear Search Algorithm)
이진 탐색 알고리즘 역시 시간복잡도를 알아보고자 한다. 그리고 이전에 알아본 순차 탐색 알고리즘에 비해 얼마나 효율적인지도 시간복잡도를 통해 알아본다. 여기서 알아볼 시간복잡도는 최악의 경우만을 따진다. 최선의 경우는 한 번이고, 평균적인 경우는 따지기가 몹시 애매하기 때문이다. 아니, 솔직히 말하면 그냥 어려워서다. 나중에 알아보도록 하자. 여기선 오직 최악의 경우(Worst case)만을 다루도록 하겠다. 최악의 경우(Worst case) 시간복잡도 데이터의 개수가 n개인 경우, 이진 탐색 알고리즘을 이용했을 때의 연산 경우의 수는 아래와 같이 일반화할 수 있다. 1. n이 1이 되기까지 2로 나누고 나머지를 버린다. 비교연산 횟수 총 k회 2. n이 1이 되었을 때, 마지막 비교연산 1회 이제 k를..
