대문자 O 표기법은 알고리즘의 대략적인 성능을 표시하는 방법입니다. 따라서 굉장히 세밀한 계산 횟수나 소요 시간을 표현한다기보다 입력 크기 n과 필요한 계산 횟수와의 ‘관계’에 더 주목하는 표현이라고 기억해 두기 바랍니다.
• O(n): 필요한 계산 횟수가 입력 크기 n과 비례할 때
• O(1): 필요한 계산 횟수가 입력 크기 n과 무관할 때
어떤 문제를 푸는 알고리즘이 두 개 있는데 하나는 O(n)이고 다른 하나는 O(1)이라면 어떤 것을 골라야 할까요? 문제에 주어지는 평균 입력 크기나 각 알고리즘의 실제 계산 방식 등에 따라 차이는 있지만, 입력 크기가 큰 문제를 풀 때는 보통 O(1)인 알고리즘이 훨씬 더 빠릅니다.
잠깐만요
계산 복잡도: 시간 복잡도와 공간 복잡도
알고리즘의 계산 복잡도는 시간 복잡도(time complexity)와 공간 복잡도(space complexity)로 나눌 수 있습니다.
이름에서 알 수 있듯이 시간 복잡도는 어떤 알고리즘을 수행하는 데 얼마나 오랜 시간이 걸리는지 분석한 것입니다. 마찬가지로 공간 복잡도는 어떤 알고리즘을 수행하는 데 얼마나 많은 공간(메모리/기억 장소)이 필요한지 분석한 것입니다.
앞에서 우리는 사칙연산 횟수로 계산 복잡도를 생각해 보았는데 이것은 시간 복잡도에 해당합니다. 어떤 알고리즘을 수행하는 데 필요한 사칙연산의 횟수가 많아지면 결국 알고리즘 전체를 수행하는 시간이 늘어나기 때문입니다.
이 책에서 나오는 ‘계산 복잡도’는 특별한 말이 없는 한 ‘시간 복잡도’를 의미합니다.