이를 일반적인 배열에서 읽기의 효율성을 빅 오로 표현하는 법과 대조해 보자. 1장 자료 구조가 중요한 까닭에서 살펴봤듯이 배열 읽기에 필요한 단계 수는 배열의 크기와 상관없이 딱 하나다. 이를 빅 오로 어떻게 표현할지 알아내려면 핵심 질문을 다시 던져야 한다. 데이터 원소가 N개일 때 배열에서 읽기에 몇 단계가 필요할까? 읽기에는 딱 한 단계가 필요하다. 따라서 O(1)이라 표현하고 “오 1”이라고 발음한다.
N에 대해 질문을 던졌는데(데이터 원소가 N개일 때 알고리즘에 몇 단계가 필요할까?) 답은 흥미롭게도 N과 무관하다. 이 부분이 사실상 핵심이다. 바꿔 말하면 배열에 원소가 몇 개든 배열에서 읽기는 항상 한 단계면 된다.
이러한 이유로 O(1)을 “가장 빠른” 알고리즘 유형으로 분류한다. 데이터가 늘어나도 O(1) 알고리즘의 단계 수는 증가하지 않는다. N이 얼마든 항상 상수 단계만 필요하다. 그래서 O(1) 알고리즘을 상수 시간(constant time)을 갖는 알고리즘이라고도 표현한다.
Note ≡ 빅 오의 수학적 설명
앞서 언급한 대로 이 책은 이해하기 쉬운 방식으로 빅 오라는 주제를 설명한다. 물론 다른 방법도 있다. 전통적인 대학 교육에서 알고리즘을 배우면 수학적 관점에서 빅 오를 소개한다. 빅 오는 원래 수학 개념이므로 수학 용어로 설명되곤 한다. 가령 빅 오를 함수 증가율의 상한값으로 설명하거나 함수 g(x)가 함수 f(x)보다 빠를 수 없을 때 g는 O(f)에 속한다고 말하기도 한다. 수학적 지식 기반에 따라 의미를 이해할 수도 전혀 그렇지 못할 수도 있다. 이 책은 수학 지식이 많지 않아도 이러한 개념을 이해할 수 있도록 집필했다.
빅 오의 수학적 배경을 더 알려면 토머스 H. 코멘과 찰스 E. 레이서손, 로날드 L. 리베스트, 클리포드 스타인의 <Introduction to Algorithms>(MIT Press, 2009)에 나오는 자세한 수학적 설명을 참고한다. 저스틴 아브라함이 작성한 https://justin.abrah.ms/computer-science/understanding-big-o-formal-definition.html은 꽤 훌륭한 정의를 제공한다.