# [07-03] 점근적 표기법 (Asymptotic Notation)

점근적 표기법은 알고리즘의 성능을 수학적으로 엄밀하게 표현하는 방법으로, Big-O, Big-Ω, Big-Θ 등이 있습니다.

---

🎯 점근적 표기법이란 무엇인가

점근적 표기법의 기본 개념

지금까지 "O(n)", "O(n²)" 같은 표기를 사용했습니다. 이제 이것의 정확한 수학적 의미를 알아봅시다.

점근적(Asymptotic)의 의미:

점근(漸近): 점점 가까워진다

수학적 의미:
n이 무한대로 갈 때 (n → ∞)
함수의 증가율이 어떻게 되는가?

예:
f(n) = 3n² + 2n + 1

n이 클 때:
- n² 항이 지배적
- 2n, 1은 무시 가능
- 계수 3도 무시

→ "점근적으로 n²에 비례한다"

실생활 비유:

두 사람의 재산 증가:

A: 매년 100만원씩 증가 (선형)
B: 매년 전년도의 2배 증가 (지수)

초기 (1년차):
A: 100만원
B: 100만원
→ 비슷함

나중 (20년차):
A: 2,000만원
B: 52,428,800만원 (약 5천억!)
→ B가 압도적

점근적으로 지수 증가가 훨씬 빠름!

왜 점근적 표기법이 필요한가?

1. 하드웨어 독립적

실제 실행 시간:
- 컴퓨터마다 다름
- 언어마다 다름
- 컴파일러마다 다름

점근적 표기법:
- 하드웨어 무관
- 언어 무관
- 본질적 성능만 표현

2. 큰 입력에서의 행동

작은 입력 (n=10):
O(n): 10번
O(n²): 100번
→ 10배 차이

큰 입력 (n=10000):
O(n): 10,000번
O(n²): 100,000,000번
→ 10,000배 차이!

점근적 표기법은 큰 입력에서의 차이를 보여줌

3. 알고리즘 비교

알고리즘 A: 5n² + 100n + 500
알고리즘 B: 0.01n³ + n

어느 것이 빠른가?

작은 n: A가 느릴 수도
큰 n: B가 훨씬 느림 (n³ 때문)

점근적으로 A가 우수!

---

📐 Big-O 표기법 (상한)

Big-O (빅 오)의 정의

수학적 정의:

f(n) = O(g(n))

의미:
n이 충분히 클 때, f(n)은 g(n)의 상수 배를 넘지 않는다

엄밀한 정의:
f(n) = O(g(n)) ⟺
∃ c > 0, ∃ n₀ > 0 such that
∀ n ≥ n₀, f(n) ≤ c · g(n)

읽는 법:
"양의 상수 c와 n₀가 존재하여,
모든 n ≥ n₀에 대해
f(n) ≤ c · g(n)이 성립한다"

직관적 이해:

f(n) = O(g(n))

= "f(n)은 최악의 경우 g(n)에 비례한다"
= "f(n)은 g(n)보다 빠르거나 같다"
= "g(n)은 f(n)의 상한(upper bound)"

예:
f(n) = 3n² + 2n + 1 = O(n²)

의미:
n이 충분히 크면
3n² + 2n + 1 ≤ c · n² (적당한 c에 대해)

Big-O 증명 예시

예제 1: f(n) = 3n + 5는 O(n)임을 증명하라.

증명:
f(n) = 3n + 5

목표: f(n) ≤ c · n을 만족하는 c, n₀ 찾기

시도:
3n + 5 ≤ c · n
5 ≤ (c - 3)n
5/n ≤ c - 3

n ≥ 1일 때, 5/n ≤ 5
따라서 c = 8, n₀ = 1이면 성립

검증:
n ≥ 1일 때
3n + 5 ≤ 8n
5 ≤ 5n ✓

∴ f(n) = O(n) (증명 완료)

예제 2: f(n) = n² + n은 O(n²)임을 증명하라.

증명:
f(n) = n² + n

목표: f(n) ≤ c · n²을 만족하는 c, n₀ 찾기

시도:
n² + n ≤ c · n²
n ≤ (c - 1)n²
1/n ≤ c - 1

n ≥ 1일 때, 1/n ≤ 1
따라서 c = 2, n₀ = 1이면 성립

검증:
n ≥ 1일 때
n² + n ≤ 2n²
n ≤ n² ✓ (n ≥ 1이면 성립)

∴ f(n) = O(n²) (증명 완료)

예제 3: f(n) = 2ⁿ은 O(n²)이 아님을 증명하라.

귀류법으로 증명:

가정: f(n) = O(n²)
즉, ∃ c, n₀ such that 2ⁿ ≤ c · n²

하지만:
n = 100일 때
2¹⁰⁰ ≈ 1.27 × 10³⁰
c · 100² = c · 10,000

아무리 큰 c를 선택해도
2ⁿ은 결국 c · n²을 넘어섬

이유: 지수 함수는 다항 함수보다 빠르게 증가

∴ 2ⁿ ≠ O(n²) (증명 완료)

Big-O의 특성

1. 상수 계수 무시

f(n) = 5n → O(n)
f(n) = 100n → O(n)
f(n) = 0.001n → O(n)

모두 같음!

2. 낮은 차수 항 무시

f(n) = n² + n → O(n²)
f(n) = n² + 100n + 1000 → O(n²)

n²이 지배적이므로 나머지 무시

3. 덧셈 규칙

f(n) = O(f₁(n))
g(n) = O(g₁(n))

→ f(n) + g(n) = O(max(f₁(n), g₁(n)))

예:
O(n) + O(n²) = O(n²)
O(n log n) + O(n) = O(n log n)

4. 곱셈 규칙

f(n) = O(f₁(n))
g(n) = O(g₁(n))

→ f(n) · g(n) = O(f₁(n) · g₁(n))

예:
O(n) · O(n) = O(n²)
O(log n) · O(n) = O(n log n)

---

📉 Big-Ω 표기법 (하한)

Big-Ω (빅 오메가)의 정의

수학적 정의:

f(n) = Ω(g(n))

의미:
n이 충분히 클 때, f(n)은 g(n)의 상수 배 이상이다

엄밀한 정의:
f(n) = Ω(g(n)) ⟺
∃ c > 0, ∃ n₀ > 0 such that
∀ n ≥ n₀, f(n) ≥ c · g(n)

읽는 법:
"양의 상수 c와 n₀가 존재하여,
모든 n ≥ n₀에 대해
f(n) ≥ c · g(n)이 성립한다"

직관적 이해:

f(n) = Ω(g(n))

= "f(n)은 최선의 경우에도 g(n)에 비례한다"
= "f(n)은 g(n)보다 느리거나 같다"
= "g(n)은 f(n)의 하한(lower bound)"

예:
f(n) = 3n² + 2n + 1 = Ω(n²)

의미:
n이 충분히 크면
3n² + 2n + 1 ≥ c · n² (적당한 c에 대해)

Big-Ω 증명 예시

예제: f(n) = 3n² + 2n은 Ω(n²)임을 증명하라.

증명:
f(n) = 3n² + 2n

목표: f(n) ≥ c · n²을 만족하는 c, n₀ 찾기

시도:
3n² + 2n ≥ c · n²
2n ≥ (c - 3)n²

n이 크면 2n보다 (c-3)n²이 더 큼 (c < 3이면)
따라서 c = 3, n₀ = 1이면 성립

검증:
n ≥ 1일 때
3n² + 2n ≥ 3n²
2n ≥ 0 ✓

∴ f(n) = Ω(n²) (증명 완료)

Big-Ω의 활용

최선의 경우 분석:

def linear_search(arr, target):
    """
    최선: Ω(1) - 첫 번째에 있음
    최악: O(n) - 마지막 또는 없음
    """
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# 최선의 경우: arr[0] == target
# → 1번 비교 → Ω(1)

알고리즘의 하한:

비교 기반 정렬:
"어떤 비교 기반 정렬도 최소 Ω(n log n)"

증명 (결정 트리):
- n개 원소의 순열: n! 가지
- 비교 결과로 구분: 2^h ≥ n!
- 트리 높이: h ≥ log₂(n!)
- Stirling 근사: log₂(n!) ≈ n log₂ n
- ∴ 최소 Ω(n log n) 비교 필요

→ 병합 정렬, 퀵 정렬이 최적!

---

🎯 Big-Θ 표기법 (정확한 차수)

Big-Θ (빅 세타)의 정의

수학적 정의:

f(n) = Θ(g(n))

의미:
f(n) = O(g(n)) AND f(n) = Ω(g(n))  즉, 상한과 하한이 같음

엄밀한 정의:
f(n) = Θ(g(n)) ⟺
∃ c₁, c₂ > 0, ∃ n₀ > 0 such that
∀ n ≥ n₀, c₁ · g(n) ≤ f(n) ≤ c₂ · g(n)

읽는 법:
"양의 상수 c₁, c₂와 n₀가 존재하여,
모든 n ≥ n₀에 대해
c₁ · g(n) ≤ f(n) ≤ c₂ · g(n)이 성립한다"

직관적 이해:

f(n) = Θ(g(n))

= "f(n)은 정확히 g(n)에 비례한다"
= "f(n)과 g(n)은 같은 증가율"
= "최선/최악 모두 g(n)"

시각화:
      c₂ · g(n) ← 상한
         ↑
      f(n) ← 실제 함수
         ↓
      c₁ · g(n) ← 하한

f(n)이 두 경계 사이에 끼임

Big-Θ 증명 예시

예제: f(n) = 3n² + 2n은 Θ(n²)임을 증명하라.

증명:
f(n) = 3n² + 2n

방법 1: O와 Ω를 각각 증명

1) f(n) = O(n²) 증명:
   3n² + 2n ≤ 5n² (n ≥ 1일 때)
   → c₂ = 5, n₀ = 1

2) f(n) = Ω(n²) 증명:
   3n² + 2n ≥ 3n² (항상 성립)
   → c₁ = 3, n₀ = 1

∴ 3n² ≤ 3n² + 2n ≤ 5n² (n ≥ 1)
∴ f(n) = Θ(n²) (증명 완료)


방법 2: 직접 증명

목표: c₁ · n² ≤ 3n² + 2n ≤ c₂ · n²

하한:
3n² + 2n ≥ 3n² (항상 성립)
→ c₁ = 3

상한:
3n² + 2n ≤ 3n² + 2n²  (n ≥ 1일 때)
         = 5n²
→ c₂ = 5

∴ c₁ = 3, c₂ = 5, n₀ = 1로
   3n² ≤ 3n² + 2n ≤ 5n² (n ≥ 1)

∴ f(n) = Θ(n²) (증명 완료)

Big-Θ의 활용

정확한 복잡도 표현:

def sum_array(arr):
    """
    Θ(n) - 최선/평균/최악 모두 n번
    """
    total = 0
    for x in arr:  # 정확히 n번
        total += x
    return total

def bubble_sort(arr):
    """
    최선: Ω(n) - 이미 정렬됨
    최악: O(n²) - 역순
    평균: Θ(n²)

    Big-Θ로 표현 불가 (최선≠최악)
    """
    # ...

def merge_sort(arr):
    """
    Θ(n log n) - 항상 같은 복잡도
    """
    # ...

---

📊 표기법 비교

관계 정리

관계:
f(n) = Θ(g(n)) ⟺ f(n) = O(g(n)) AND f(n) = Ω(g(n))

벤 다이어그램:
        O(g(n))
    ┌─────────────┐
    │            │
    │   Θ(g(n))  │ ← 교집합
    │            │
    └─────────────┘
        Ω(g(n))

예시:

f(n) = 3n² + 2n

Big-O:
f(n) = O(n²) ✓
f(n) = O(n³) ✓ (더 느슨한 상한)
f(n) = O(n⁴) ✓
f(n) = O(n) ✗ (틀림)

Big-Ω:
f(n) = Ω(n²) ✓
f(n) = Ω(n) ✓ (더 느슨한 하한)
f(n) = Ω(log n) ✓
f(n) = Ω(n³) ✗ (틀림)

Big-Θ:
f(n) = Θ(n²) ✓ (정확!)
f(n) = Θ(n) ✗
f(n) = Θ(n³) ✗

언제 어떤 표기법?

Big-O (가장 많이 사용):
- 최악의 경우 성능
- 알고리즘 비교
- 성능 보장

예: "이 알고리즘은 O(n log n)입니다"

Big-Ω:
- 최선의 경우
- 문제의 하한
- 알고리즘 최적성 증명

예: "비교 정렬은 최소 Ω(n log n)입니다"

Big-Θ:
- 정확한 복잡도
- 모든 경우가 같을 때
- 이론적 분석

예: "병합 정렬은 Θ(n log n)입니다"

---

📐 기타 표기법

Little-o (작은 오)

f(n) = o(g(n))

의미:
f(n)은 g(n)보다 "엄격히" 느리게 증가

정의:
lim(n→∞) f(n)/g(n) = 0

예:
n = o(n²) ✓
n² = o(n²) ✗ (같으므로)
n log n = o(n²) ✓

차이:
Big-O: f(n) ≤ c · g(n) (이하)
little-o: f(n) < g(n) (미만, 극한에서)

Little-ω (작은 오메가)

f(n) = ω(g(n))

의미:
f(n)은 g(n)보다 "엄격히" 빠르게 증가

정의:
lim(n→∞) f(n)/g(n) = ∞

예:
n² = ω(n) ✓
n² = ω(n²) ✗ (같으므로)
2ⁿ = ω(n²) ✓

차이:
Big-Ω: f(n) ≥ c · g(n) (이상)
little-ω: f(n) > g(n) (초과, 극한에서)

---

🔍 복잡도 함수 순서

주요 복잡도 순서

느림 ←──────────────────────────────→ 빠름

O(n!) > O(2ⁿ) > O(n³) > O(n²) > O(n log n) > O(n) > O(log n) > O(1)

더 정확히:
O(1)
  < O(log log n)
  < O(log n)
  < O((log n)²)
  < O(√n)
  < O(n)
  < O(n log n)
  < O(n²)
  < O(n³)
  < O(2ⁿ)
  < O(n!)
  < O(nⁿ)

극한을 이용한 비교

f(n)과 g(n)의 비교:

lim(n→∞) f(n)/g(n) = L이면

L = 0:    f(n) = o(g(n))      f가 훨씬 느림
0 < L < ∞: f(n) = Θ(g(n))     같은 차수
L = ∞:    f(n) = ω(g(n))      f가 훨씬 빠름

예:
lim(n→∞) n/n² = lim 1/n = 0
→ n = o(n²)

lim(n→∞) 3n²/n² = 3
→ 3n² = Θ(n²)

lim(n→∞) 2ⁿ/n² = ∞
→ 2ⁿ = ω(n²)

---

💡 실무 팁

표기법 남용 피하기

# 잘못된 표현
def algorithm(n):
    # "이 알고리즘은 O(n)이다" ✗
    # O(n)은 집합이지 값이 아님
    pass

# 올바른 표현
# "이 알고리즘의 시간복잡도는 O(n)이다" ✓
# "이 알고리즘은 O(n) 시간에 실행된다" ✓

정확한 분석

def example(n):
    # 잘못된 분석
    # "O(n) + O(n) = O(2n) = O(n)" ✗
    # 중간 단계 불필요

    # 올바른 분석
    # "O(n) + O(n) = O(n)" ✓

    for i in range(n):
        pass  # O(n)

    for i in range(n):
        pass  # O(n)

    # 총: O(n)

최선/평균/최악 명확히

def binary_search(arr, target):
    """
    최선: Θ(1) - 중간에 있음
    평균: Θ(log n)
    최악: Θ(log n) - 없음

    보통 최악으로 표현: O(log n)
    """
    # ...

---

🎯 핵심 정리

점근적 표기법의 본질

• 입력이 클 때의 증가율
• 하드웨어 독립적
• 알고리즘의 본질적 효율성

세 가지 주요 표기법

표기법    의미                 용도
--------------------------------------------------
Big-O    상한 (≤)            최악의 경우
Big-Ω    하한 (≥)            최선의 경우
Big-Θ    정확한 차수 (=)    모든 경우 같을 때

수학적 정의

Big-O:
f(n) = O(g(n)) ⟺
∃ c, n₀ : ∀n ≥ n₀, f(n) ≤ c·g(n)

Big-Ω:
f(n) = Ω(g(n)) ⟺
∃ c, n₀ : ∀n ≥ n₀, f(n) ≥ c·g(n)

Big-Θ:
f(n) = Θ(g(n)) ⟺
f(n) = O(g(n)) AND f(n) = Ω(g(n))

복잡도 순서

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

실무 지침

일반적으로 Big-O 사용:
- 최악의 경우 보장
- 가장 보수적

Big-Θ 사용:
- 정확한 분석 필요 시
- 이론적 연구

---

🔗 다음 글에서는

[07-04] 최선/평균/최악 경우 분석

• 입력에 따른 성능 차이: 같은 알고리즘도 입력에 따라 다른 성능
• 최선의 경우 분석: 가장 좋은 입력 패턴과 성능
• 평균 경우 분석: 확률적 분석과 기댓값 계산
• 최악의 경우 분석: 성능 보장과 실무에서의 중요성

---

이전 글: [07-02] 공간 복잡도
다음 글: [07-04] 최선/평균/최악 경우 분석
시리즈: P1. Computer Science