컴퓨터 과학자는 서로 간에 시간 복잡도를 쉽게 소통할 목적으로 자료 구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 수학적 개념을 차용했다.
이러한 개념을 형식화한 표현을 빅 오 표기법이라고 부른다. 빅 오 표기법을 사용해 주어진 알고리즘의 효율성을 쉽게 분류하고 이해시킬 수 있다.
빅 오는 특정 방식으로 알고리즘에 필요한 단계 수를 고려함으로써 일관성을 유지한다. 최악의 경우 선형 검색에는 배열의 원소 수만큼의 단계가 필요하다. 빅 오 표기법으로는 O(N)이라 표기한다.
O(N)은 데이터 원소가 N개일 때 알고리즘에 N단계가 필요하다.
배열에 원소가 N개일 때 선형 검색에 몇 단계가 필요할까? 선형 검색에는 N단계가 필요하므로 O(N)으로 표현한다. 그래서 O(N)인 알고리즘을 선형 시간을 갖는 알고리즘이라고도 부른다
배열 읽기에 필요한 단계 수는 배열에 크기와 상관없이 딱 하나 따라서 O(1)이라 표현하고 “오 1” 이라고 발음한다. 즉, 배열에 원소가 몇 개든 배열에서 읽기는 항상 한 단계면 된다.
이러한 이유로 O(1)을 “가장 빠른" 알고리즘 유형으로 분류한다. 데이터가 늘어나도 O(1) 알고리즘의 단계 수는 증가하지 않는다.
O(1) 알고리즘을 상수 시간을 갖는 알고리즘이라고도 표현한다.
빅 오 표기법은 머릿속에 새겼던 핵심 질문. 즉, 데이터 원소가 N개일 때 알고리즘에 몇 단계가 필요한가에 대한 답이다.
데이터가 몇 개든 항상 3단계가 걸리는 알고리즘을 가정해보면 원소가 N개일 때 알고리즘에 항상 3단계가 필요하다 이를 빅 오로 표현하면 O(3)이 아니라 O(1)이다.
빅 오의 본질이란 빅 오가 진정으로 의미하는 것 즉, 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는지를 말한다. 빅 오는 단순히 알고리즘에 필요한 단계 수만 알려주지 않는다. 데이터가 늘어날 때 단계 수가 어떻게 증가하는지 설명한다.
만일 데이터 크기에 상관없이 항상 100단계가 걸리는 상수 시간 알고리즘이 있다고 가정하자.
원소가 100개 이하인 데이터 세트에서는 100단계가 걸리는 O(1) 알고리즘보다 O(N) 알고리즘이 단계 수가 적다.
하지만, 100보다 큰 모든 배열에서는 O(N) 알고리즘에 다 많은 단계가 걸린다.
100보다 큰 순간부터 무한대까지 O(N)은 O(1)보다 더 많은 단계를 필요로 한다. 100단계 뿐 아니라 백만 단계여도 마찬가지이다. 데이터가 증가할 수록 O(N)이 O(1)보다 덜 효율적인 어떤 지점에 반드시 다다르게 된다.
따라서, O(N)이 전반적으로 O(1)보다 덜 효율적이다.