점근 표기법

빅 오 표기법은 알고리즘의 성능을 분석할 때 가장 널리 사용되는 점근 표기법이다. 이 표기법은 알고리즘이 최악의 경우에 입력 크기 n에 대해 얼마나 많은 자원(주로 시간)을 소모하는지의 상한을 점근적으로 나타낸다. 즉, 알고리즘의 실행 시간이 아무리 나빠도 특정 함수의 상수 배를 넘지 않음을 의미한다. 이는 알고리즘의 효율성을 비교하고 분류하는 데 핵심적인 도구로 작용한다.

빅 오 표기법의 수학적 정의는 다음과 같다. 두 함수 f(n)과 g(n)이 주어졌을 때, 모든 충분히 큰 n에 대해 f(n) ≤ C * g(n)을 만족하는 양의 상수 C와 n0가 존재하면 f(n) = O(g(n))이라고 표기한다. 이때 g(n)은 상한을 나타내는 함수이며, 예를 들어 알고리즘의 실행 시간이 2n^2 + 3n + 1이라면, 이는 O(n^2)으로 표현된다. 낮은 차수의 항(3n)과 상수항(1)은 n이 커짐에 따라 영향력이 미미해지기 때문에 제외하고, 가장 높은 차수의 항(n^2)만을 고려하는 것이다.

다양한 알고리즘의 시간 복잡도를 빅 오 표기법으로 표현하면 다음과 같은 표로 정리할 수 있다. 이는 알고리즘의 성능을 한눈에 비교하는 데 유용하다.

빅 오 표기법은 알고리즘의 성능을 추상화하여 비교할 수 있게 해주지만, 몇 가지 주의점이 있다. 이 표기법은 상한을 다루므로, 알고리즘이 항상 이보다 훨씬 빠르게 실행될 수 있음을 의미하지는 않는다. 예를 들어, 선형 탐색 알고리즘은 O(n)이지만, 찾는 값이 첫 번째에 위치하면 O(1)에 실행된다. 또한, 상수 계수와 낮은 차수의 항을 무시하기 때문에, 이론적으로는 동일한 O(g(n))을 가진 두 알고리즘이 실제 실행 환경에서는 상수 배의 차이로 인해 성능 차이를 보일 수 있다. 따라서 빅 오 분석은 대규모 입력에 대한 알고리즘의 확장성 트렌드를 이해하는 데 유용하지만, 소규모 입력이나 상세한 최적화에는 다른 분석이 필요할 수 있다.

오메가 표기법(Ω)은 알고리즘의 점근적 하한을 나타내는 표기법이다. 이는 알고리즘이 최소한 어떤 속도로 느려질 수 있는지를 수학적으로 정의한다. 즉, 입력 크기 n이 충분히 커질 때, 알고리즘의 수행 시간이 특정 함수 g(n)에 상수 배를 곱한 값보다 항상 크거나 같음을 의미한다. 이는 알고리즘의 최선의 경우나 평균적인 경우보다는 최악의 경우 성능에 대한 하한선을 제공한다.

빅 오 표기법이 알고리즘 성능의 상한(최악의 경우)을 설명한다면, 오메가 표기법은 그 반대인 하한을 설명한다. 예를 들어, 모든 비교 정렬 알고리즘은 최악의 경우 Ω(n log n)의 시간 복잡도를 가진다. 이는 아무리 효율적인 비교 정렬 알고리즘이라도 입력 크기 n에 대해 n log n보다 점근적으로 더 빠를 수 없다는 것을 보장한다. 이러한 하한 증명은 알고리즘의 이론적 한계를 이해하는 데 핵심적이다.

오메가 표기법의 수학적 정의는 다음과 같다. 함수 f(n)이 Ω(g(n))이라는 것은, 모든 충분히 큰 n에 대해 f(n) ≥ c * g(n)을 만족하는 양의 상수 c와 n0가 존재함을 의미한다. 예를 들어, 알고리즘의 수행 시간이 f(n) = 3n² + 2n + 1일 때, 이는 Ω(n²)이라고 말할 수 있다. 왜냐하면 n이 커짐에 따라 함수의 동작이 n²에 비례하는 항이 지배적이기 때문이다.

이 표기법은 알고리즘의 절대적인 효율성을 논할 때보다는, 특정 문제를 해결하는 알고리즘의 근본적인 복잡도 하한을 증명하는 데 더 유용하게 쓰인다. 세타 표기법이 점근적으로 정확한 한계를 나타낼 때, 오메가 표기법은 그 정확한 한계의 하한 부분을 구성하는 역할을 한다. 따라서 계산 복잡도 이론에서 문제의 난이도를 분류하거나, 특정 유형의 알고리즘이 가질 수 있는 성능의 이론적 최소치를 규명하는 데 중요한 도구이다.

세타 표기법은 알고리즘의 점근적 성능을 정확하게 묘사할 때 사용한다. 빅 오 표기법이 상한만을, 오메가 표기법이 하한만을 나타내는 반면, 세타 표기법은 점근적으로 상한과 하한이 동일한, 즉 정확한 성장률을 표현한다. 어떤 함수 f(n)이 Θ(g(n))이라면, 충분히 큰 n에 대해 f(n)은 g(n)에 상수 배를 곱한 값 사이에 꼭 끼어 있음을 의미한다. 따라서 이 표기법은 알고리즘의 성능이 최악의 경우와 최선의 경우 모두 동일한 비율로 증가함을 보여줄 때 유용하다.

예를 들어, 입력 크기 n에 대한 모든 요소를 한 번씩 확인하는 선형 탐색 알고리즘의 최악의 경우 시간 복잡도는 O(n)이다. 그러나 이 알고리즘의 최선의 경우는 첫 번째 요소에서 바로 찾는 경우로 Ω(1)이다. 따라서 선형 탐색의 수행 시간은 Θ(n)이라고 말할 수 없다. 반면, 모든 요소를 비교하며 정렬하는 버블 정렬의 기본 구현은 최선, 평균, 최악의 경우 모두 수행 시간이 n의 제곱에 비례하므로, 그 시간 복잡도를 Θ(n²)으로 표현할 수 있다.

세타 표기법의 수학적 정의는 다음과 같다. f(n) = Θ(g(n))은 양의 상수 c₁, c₂, 그리고 n₀이 존재하여, 모든 n ≥ n₀에 대해 0 ≤ c₁*g(n) ≤ f(n) ≤ c₂*g(n)을 만족할 때 성립한다. 이는 함수 f(n)의 증가율이 g(n)과 점근적으로 동일하다는 엄밀한 의미를 갖는다. 알고리즘 분석에서 Θ 표기는 해당 알고리즘의 성능이 입력 크기에 대해 정확히 어떤 클래스에 속하는지를 명시적으로 보여주는 강력한 도구가 된다.

리틀 오 표기법은 점근 표기법 중 하나로, 함수의 증가율을 비교할 때 사용한다. 빅 오 표기법이 '점근적 상한'을 의미하는 반면, 리틀 오 표기법은 '점근적으로 엄격히 더 작은' 상한을 나타낸다. 즉, 한 함수가 다른 함수보다 무시할 수 있을 정도로 느리게 증가함을 수학적으로 엄밀하게 정의하기 위한 도구이다.

수학적으로, 함수 f(n)이 o(g(n))에 속한다는 것은, 모든 양의 상수 c에 대해, 충분히 큰 n에 대해 f(n) < c * g(n)이 성립함을 의미한다. 이는 빅 오 표기법의 정의에서 등호가 제거된 형태로, 예를 들어 f(n) = 2n이 o(n^2)에 속하지만, o(n)에는 속하지 않는다. 빅 오 표기법에서는 O(n)이 가능하지만, 리틀 오 표기법은 더 엄격한 조건을 요구한다.

이 표기법은 주로 알고리즘의 성능을 보다 정교하게 비교할 때 활용된다. 예를 들어, 시간 복잡도가 O(n)인 알고리즘 A와 O(n log n)인 알고리즘 B가 있을 때, A가 B보다 점근적으로 더 빠르다고 말할 수 있다. 이때 A의 복잡도는 B의 복잡도인 n log n에 대해 리틀 오 관계, 즉 o(n log n)에 속한다고 표현할 수 있다. 이는 A가 B보다 엄격히 더 좋은 성능을 가짐을 강조한다.

따라서 리틀 오 표기법은 점근 표기법의 다른 형태들, 특히 빅 오 표기법과 함께 사용되며, 알고리즘 분석에서 두 알고리즘의 성능 차이를 정량화하고 이론적으로 분류하는 데 중요한 역할을 한다.

리틀 오메가 표기법은 점근 표기법 중 하나로, 함수의 점근적 하한을 '엄격하게' 기술하는 데 사용된다. 이는 빅 오메가 표기법보다 더 강력한 제약을 의미하며, 함수 f(n)이 함수 g(n)보다 점근적으로 '훨씬 빠르게' 증가함을 나타낸다. 즉, g(n)이 f(n)의 성장률을 따라잡지 못한다는 것을 수학적으로 엄밀하게 정의한다.

정의에 따르면, 모든 양의 상수 c에 대하여, 충분히 큰 n에 대해 0 ≤ c*g(n) < f(n)이 성립할 때, f(n) = ω(g(n))이라고 쓴다. 이는 빅 오메가 표기법의 정의에서 부등호가 '≤'가 아닌 '<'로 강화된 형태이다. 예를 들어, n² = ω(n)은 성립하지만, 2n² = ω(n²)은 성립하지 않는다. 후자의 경우, c=1일 때 1*n² < 2n²이 항상 성립하므로 빅 오메가 조건(Ω)은 만족하지만, c=3과 같이 큰 상수를 선택하면 3*n² < 2n²이 거짓이 되어 리틀 오메가 조건을 만족시키지 못한다.

이 표기법은 주로 알고리즘의 하한을 보다 정밀하게 논할 때 활용된다. 예를 들어, 비교 기반 정렬 알고리즘의 하한이 Ω(n log n)임은 잘 알려져 있다. 여기에 리틀 오메가 표기법을 사용하면, 이러한 알고리즘의 시간 복잡도가 ω(n)임을 표현할 수 있다. 이는 알고리즘이 선형 시간보다 '엄격하게 느리게'는 동작할 수 없음을, 즉 선형 시간에 동작하는 비교 정렬 알고리즘은 존재하지 않음을 강조하는 방식이다.

리틀 오 표기법(o)이 '엄격한 상한'을 나타내는 것과 쌍을 이루며, 계산 복잡도 이론에서 정교한 분석을 가능하게 한다. 그러나 실제 알고리즘 분석에서 가장 흔히 사용되는 빅 오 표기법이나 세타 표기법에 비해 빈도는 낮은 편이다.