[Algorithm] 점근적 표기법(Asymptotic Notation)

점근적 표기법(Asymptotic Notation)은 알고리즘의 효율성을 분석하기 위해 사용되는 수학적 표기법이다. 이는 주로 알고리즘의 시간 복잡도와 공간 복잡도를 표현하는 데 사용되며, 입력 크기가 커질 때 알고리즘의 성능을 이해하는 데 도움을 준다. 점근적 표기법에는 크게 O, Ω, Θ가 있다. 각각 빅-오(Big-O), 빅-오메가(Big-Omega), 빅-세타(Big-Theta)라고 부른다.

간단한 예제로 점근적 표기법 이해하기

간단한 다항식 5n³ + 2n² + n - 7 이라는 식이 있다고 가정해보자.

1. 빅-오 표기법 (O Notation)

   • O는 가장 높은 차수보다 같거나 높은 식을 뜻한다. 즉, 5n³ + 2n² + n - 7 에서 가장 높은 차수는 n³ 이므로 O(n³), O(n⁴), O(n⁵) 모두 맞는 말이다. 하지만 우리는 좀 더 타이트하게 O(n³)라고 부르게 되며, 이것이 바로 시간복잡도를 재는 척도로 쓰인다.
   • 예시: 5n³ + 2n² + n - 7 = O(n⁴) 로도 나타낼 수 있지만, 타이트하게 5n³ + 2n² + n - 7 = O(n³) 라고 한다.

2. 빅-오메가 표기법 (Ω Notation)

   • Ω는 가장 높은 차수보다 같거나 낮은 식을 뜻한다. 즉, 5n³ + 2n² + n - 7 에서 가장 높은 차수는 n³ 이므로 Ω(n³), Ω(n²), Ω(n) 모두 맞는 말이다.
   • 예시: 만약 f(n) = 5n³ + 2n² + n - 7 이고, g(n) = n² 라면, f(n) = Ω(g(n)) 로 나타낼 수 있다. 이는 f(n)의 차수가 g(n)의 차수보다 같거나 크다는 의미다.

3. 빅-세타 표기법 (Θ Notation)

   • Θ는 최고차항(가장 높은 차수)을 뜻한다. 즉, 5n³ + 2n² + n - 7에서 가장 높은 차수는 n³이므로 Θ(n³)로 나타낸다.
   • 예시: 5n³ + 2n² + n - 7 = Θ(n³)로 나타낸다. 이는 알고리즘의 시간복잡도가 정확히 n³에 비례함을 의미한다.

또한, 점근적 표기법은 n이 무한히 커졌을 때의 상황에 관심이 있기 때문에 식 앞에 있는 상수값은 항상 무시한다. 즉, O(9n³ - 2) = O(n³)을 만족하며, 이는 9n³ + 2n² + n - 1 식을 O(n³)로 나타낼 수 있음을 뜻한다. Ω, Θ 역시 마찬가지로 상수값을 전부 무시하게 된다.

점근적 표기법 요약

• 빅-오 (O): 최악의 경우 시간복잡도. 예: O(n³)
• 빅-오메가 (Ω): 최선의 경우 시간복잡도. 예: Ω(n)
• 빅-세타 (Θ): 평균 혹은 정확한 시간복잡도. 예: Θ(n³)

점근적 표기법을 통해 알고리즘의 효율성을 평가하고 비교할 수 있으며, 이를 통해 더 나은 알고리즘을 설계할 수 있다.