Page 112 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)
P. 112
조금만 더! 컴퓨터에게 n / 2과 n의 차이는 크지 않아요!
n / 2번 실행했을 때 복잡도를 O(n / 2)가 아닌 O(n)으로 표현하는 이유는 n의 값이 무한히 커진다고 가정
했을 때, 그 값의 차이가 무의미해지기 때문입니다. 마찬가지로 100번만 실행하는 경우에도 O(100)이 아
닌 O(1)로 표기합니다. 컴퓨터가 100번을 계산하는 시간과 1번만 계산하는 시간의 차이는 사람이 느낄
수 없을 정도로 굉장히 작습니다.
[표 3-1] 선형 검색에서 각 단계의 실행 횟수와 복잡도
단계 실행 횟수 복잡도
1 1 O(1)
2 n / 2 O(n)
3 n / 2 O(n)
4 1 O(1)
5 n / 2 O(n)
6 1 O(1)
그런데 n이 점점 커지면 O(n)에 필요한 계산 시간은 n에 비례하여 점점 길어집니다. 이와
달리 O(1)에 필요한 계산 시간은 변하지 않습니다. 일반적으로 O(f(n))과 O(g(n))의 복잡
도를 계산하는 방법은 아래와 같습니다.
O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
max(a, b)는 a와 b 가운데 큰 쪽을 나타내는 함수입니다.
2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 더 높은 쪽의 복잡도를 우선
시합니다. 둘이 아니라 셋 이상의 계산으로 구성된 알고리즘도 마찬가지입니다. 다시 말해 전
체 복잡도는 차원이 가장 높은 복잡도를 선택합니다. 그러므로 선형 검색 알고리즘의 복잡도
를 구하면 아래처럼 O(n)이 됩니다.
O(1) + O(n) + O(n) + O(1) + O(n) + O(1) = O(max(1, n, n, 1, n, 1)) = O(n)
112 C 알고리즘
