알고리즘 복잡도 표기법

컴퓨터 과학에서는 알고리즘의 복잡도를 나타내는 데 $$T(n), O, \Theta, \Omega$$ 등의 표기법을 사용한다. 이러한 표기법은 알고리즘의 실행 시간이나 공간 요구사항의 상한, 하한, 또는 정확한 경계를 지정한다. 이러한 표기법을 빅 오 표기법이라고도 하며, 각각은 다음과 같은 의미를 가진다.

• Big O 표기법 (O): 함수의 상한을 설명한다. ( O(g(n)) )은 함수 ( f(n) )이 ( c \times g(n) )을 초과하지 않음을 의미한다. 이는 주로 최악의 경우 성능을 나타내는 데 사용된다.

• Theta 표기법 ((\Theta)): 함수의 정확한 성장률을 나타낸다. ( \Theta(g(n)) )은 ( f(n) )이 ( c_1 \times g(n) )과 ( c_2 \times g(n) ) 사이에 존재함을 의미한다. 즉, ( f(n) )은 ( g(n) )과 정확히 동일한 성장률을 가진다. 이는 알고리즘이 일반적인 경우에 어떤 성능을 보일지를 설명하는 데 사용된다.

• Omega 표기법 ((\Omega)): 함수의 하한을 설명한다. ( \Omega(g(n)) )은 ( f(n) )이 ( c \times g(n) ) 이상임을 의미한다. 이는 주로 최선의 경우 성능을 나타내는 데 사용된다.

예를 들어, 병합 정렬의 경우 최악의 경우에도 ( O(n \log n) )이고, 평균적으로도 ( \Theta(n \log n) )이다. 이는 병합 정렬이 ( n \log n )의 상한과 하한을 모두 가지며, 일반적으로 이 성장률을 유지한다는 의미이다. 반면, 최선의 경우 빠른 정렬(Quick Sort)은 ( \Omega(n \log n) )이고, 최악의 경우는 ( O(n^2) )이다.

따라서, ( \Theta ) 표기를 사용하는 이유는 알고리즘의 성능이 어느 정도 일관적으로 특정 함수의 성장률을 따른다고 말할 때이다. ( O ) 표기는 일반적으로 최악의 경우를 의미하므로, 정확한 성능 측정을 위해 ( \Theta )를 사용하는 것이 더 적절할 수 있다.