Page 114 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)
P. 114
[표 3-2] 이진 검색에서 각 단계의 실행 횟수와 복잡도
단계 실행 횟수 복잡도
1 1 O(1)
2 1 O(1)
3 log n O(log n)
4 log n O(log n)
5 1 O(1)
6 log n O(log n)
7 log n O(log n)
8 log n O(log n)
9 log n O(log n)
10 log n O(log n)
11 1 O(1)
이진 검색 알고리즘의 복잡도를 구하면 아래처럼 O(log n)을 얻을 수 있습니다.
O(1) + O(1) + O(log n) + O(log n) + O(1) + O(log n) + … + O(1) = O(log n)
그런데 O(n)과 O(log n)은 O(1)보다 큽니다. 다음 그림에 복잡도의 대소 관계를 나타냈습
니다.
작다 크다
L
ɹɹɹ MPH Oɹɹɹ Oɹɹɹ O MPH Oɹɹɹ O ɹɹɹ O ɹɹɹ O ɹɹɹ O
[그림 3-7] 복잡도와 증가율
114 C 알고리즘
