big O notation(빅오 표기법)

모든 상수 시간 알고리즘은 O(1)이라는 집합에 속한다. 따라서 어떤 알고리즘이 상수 시간임을 다르게 말하고 싶다면 그것이 O(1)에 있다고 말하면 된다. 마찬가지로 모든 선형 알고리즘은 O(n)에 속하며 모든 이차 알고리즘은 O(n²)에 속한다. 이렇게 알고리즘을 분류하는 방식을 빅오 표기법(big O notation)이라고 한다.

 

이 표기법은 알고리즘을 작성할 때 알고리즘이 어떻게 동작하는지에 관한 일반적인 법칙을 표현하는 간편한 방법을 제공한다.

 

예를 들어, 상수 시간 알고리즘에 이어 선형 시간 알고리즘을 수행하면 총 실행시간은 선형이 된다. 이를 '〰️의 요소'라는 의미의 '∈' 기호를 사용하여 표현하면 f ∈ O(n)고 g ∈ O(1)면 f + g ∈ O(n)가 된다.

 

두개의 선형 연산을 수행하면 합은 여전히 선형이다. 이를 빅오 표기법으로 표현하면 f ∈ O(n)고 g ∈ O(n)면 f + g ∈ O(n)가 된다.

 

사실 k가 n에 의존하지 않는 상수인 한 선형 연산을 k번 수행하면 합은 선형이다. 이를 빅오 표기법으로 표현하면 f ∈ O(n)고 k가 상수라면 kf ∈ O(n)가 된다.

 

하지만 선형 연산을 n번 반복하면 결과는 이차가 된다. 이를 빅오 표기법으로 표현하면 f ∈ O(n)이면 nf ∈ O(n²)가 된다.

 

일반적으로 n의 가장 큰 지수만 신경 쓰기 때문에 총 연산 횟수가 2n + 1이라면 실행 시간은 O(n)이다. 선행 상수 2와 덧셈 항 1은 이러한 종류의 분석에서 중요하지 않다. 마찬가지로 n² + 100n + 1000도 O(n²)이 된다. 큰 숫자에 현혹되면 안됨!

 

증가 차수(order of growth)는 같은 개념의 다른 이름이다. 증가 차수는 실행시간이 같은 빅오 범주에 해당하는 알고리즘 집합이다. 예를 들어, 모든 선형 알고리즘은 실행시간이 O(n)에 있으므로 같은 증가 차수에 속한다.

 

이 문맥에서 차수(order)는 집단의 의미로, 원탁의 기사단(Order of the Knights of the Round Table)처럼 기사들의 집단을 가리키지 그들의 순서를 말하는 것이 아니다. 따라서 선형 알고리즘 차수(Order of Linear Algorithm)는 용감하고 예의 바르고 특히 효율적인 알고리즘 집합으로 생각하면 된다.