algo_lec2

 

알고리즘 분석 (Algorithm Analysis)

---

1. Optimality (최적성)

• 어떤 문제는 근본적으로 요구되는 최소한의 연산량이 존재함 → 이론적 한계 = Lower Bound
• 어떤 알고리즘이 그 문제의 lower bound와 upper bound를 일치시킬 수 있다면, 그 알고리즘은 최적(Optimal)

예시:

• 행렬 곱셈:
  • 전통적 알고리즘: O(n³)
  • Strassen's algorithm (1969): O(n^2.81)
  • Coppersmith-Winograd (1987): O(n^2.376)

---

2. 점근적 표기법 (Asymptotic Notation)

Big-O (O(f(n))) : 상한 Asymptotic upper bound

• 정의: 어떤 함수 g(n)에 대해, n이 충분히 클 때 g(n) ≤ c×f(n) 를 만족하는 c, n₀가 존재
• 의미: 최악의 경우에 이 이상으로 커지지 않음
• 예시:
  • n² + 10n ∈ O(n²) (c = 2, n₀ = 10)

Big-Omega (Ω(f(n))) : 하한 Asymptotic lower bound

• 정의: 어떤 함수 g(n)에 대해, n이 충분히 클 때 g(n) ≥ c×f(n) 를 만족하는 c, n₀가 존재
• 의미: 최소한 이 정도는 걸림
• 예시:
  • 2n² logn + 1 ∈ Ω(n²)

Big-Theta (Θ(f(n))) – 정확한 성장률 Exact bound

• 정의: c×f(n) ≤ g(n) ≤ d×f(n)을 만족하는 c, d, n₀ 존재 시
• 의미: 정확한 성장률로 f(n)과 같음
• Big-O 와 Big-Omega의 교점
• 예시:
  • 5n² + 15 ∈ Θ(n²)

---

3. 시간복잡도 비교 (Complexity classes)

표기	시간 복잡도	예시 알고리즘
Θ(1)	상수시간	배열 접근
Θ(log n)	로그시간	이진 탐색
Θ(n)	선형시간	선형 탐색
Θ(n log n)	로그-선형	병합정렬
Θ(n²)	2차	이중 루프
Θ(2ⁿ)	지수	재귀 피보나치

비교 기준:

• lim n→∞ ( g(n) / f(n) ) = c 라고 할 때 → 같은 성장률 의미
• c = 0 → g(n) < f(n) → g(n)이 f(n)보다 더 빠름.
• c = ∞ → f(n) < g(n) → f(n)이 g(n)보다 더 빠름.

L'Hospital's Rule

---

알고리즘 분석이 필요한 이유

(1) 알고리즘 성능 개선 목적

• 기존 알고리즘을 더 효율적으로 개선하기 위해
• 연산 횟수나 자원 사용을 줄여야 할 필요가 있는 경우

(2) 여러 알고리즘 중 최적 선택

• 같은 문제를 푸는 다양한 알고리즘이 존재할 때,
• 그 중에서 시간복잡도와 공간복잡도가 가장 적절한 것을 선택해야 함

 

4. 시간복잡도 정의

• Worst-case (W(n)): 가장 많은 연산이 필요한 경우 Mostly used
  ex) 선형 탐색에서 탐색 실패 시 → O(n)
• Average-case (A(n)): 평균적인 입력에 대해 필요한 연산 수 Rarely used
  ex) Linear search algorithm → A(n) ≈ n/2 = O(n)
• Amortized-case: 일련의 연산에 걸친 평균 → 비싼 연산이 가끔 있지만, 전체 평균은 낮음 분할상환
  ex) Stack의 push/pop

Situation: Shop for clothing all under $10

상황: 모든 옷이 10달러 이하인 가게에서 쇼핑하기
앨리스는 옷을 3벌 사고 싶어 한다.
그녀는 얼마를 준비해야 할까?
나중에, 옷의 평균 가격이 5달러라는 정보를 얻게 된다.
그렇다면 얼마를 준비해야 할까?
앨리스는 5달러보다 저렴한 옷을 살 때 절약한 돈을, 나중에 5달러보다 비싼 옷을 사는 데 사용할 수 있다.

---

5. Amortized Analysis (평균 시간 분석) - 방법 2가지

방법 1: Accounting method (회계 방식)

• 비싼 연산에 대비해 저렴한 연산에서 비용을 미리 적립
• 예시:
  • push: 실제 비용 $1 → $2로 설정, $1은 저장
  • pop: 실제 비용 $1 → 저장된 $1로 지불
  • 결과적으로 모든 연산의 Amortized cost = O(1)

방법 2: Potential method (잠재 에너지 방식)

• 스택의 상태에 따라 잠재 에너지(Φ)를 정의
• Amortized cost = real cost + (Φ(D₁) - Φ(D₀))
• 스택 길이를 잠재함수로 정의할 경우 모든 연산의 평균 시간복잡도는 O(1)

Potential method

1. 핵심 개념

• 잠재 함수 Φ(D)는 데이터 구조 D가 가진 “잠재된 비용(에너지)”을 수치화한 것
• 어떤 연산(op)이 데이터를 D₀ → D₁로 바꾸면,
  • 실제 비용(real cost) + 잠재 에너지 변화(Φ(D₁) - Φ(D₀))가 Amortized Cost가 됨

---

2. 직관 비유

• 스프링이나 활이 에너지를 저장하고 있다가 한 번에 힘을 쓰는 것처럼,
• stack 같은 자료구조도 push 연산으로 에너지를 축적해 놓고,
  나중에 pop 연산에 그 에너지를 써서 비용을 상쇄할 수 있음

---

3. 수학적 정의

• 연산 opi가 구조를 Di−1→Di로 바꾸면, Amortized cost(opi)=real cost(opi)+Φ(Di)−Φ(Di−1)​

• 이때 Φ(D)는 non-negative 함수여야 함 (음수 불가)

---

4. 예시: Stack 연산

잠재 함수 설정:

• 스택에 저장된 항목 수 = 스택의 상태 D의 Φ(D)
• 즉, 스택 길이만큼 잠재 에너지를 가진다고 설정

---

(1) push 연산

• real cost = 1 (항목 하나 추가)
• Φ 변화 = +1 (스택 길이 1 증가)
• amortized cost = 1 + 1 = 2 → O(1)

(2) pop 연산

• real cost = 1 (항목 하나 제거)
• Φ 변화 = -1 (스택 길이 1 감소)
• amortized cost = 1 - 1 = 0 → O(1)

(3) multipop(k) 연산

• real cost = min(k, s) (최대 s번 pop)
• Φ 변화 = -min(k, s)
• amortized cost = min(k, s) - min(k, s) = 0 → O(1)

---

6. 시간복잡도 예시

# 선형 탐색
def search(arr, x):
    for index, value in enumerate(arr):
        if value == x:
            return index
    return -1

• W(n): x가 없거나 맨 끝에 있음 → O(n)
• A(n): (1 + 2 + ... + n) / (n+1) ≈ n/2 = O(n)

---

7. 공간복잡도 (Space Complexity)

• 사용되는 메모리:
  • 명령어, 상수, 변수
  • 입력 데이터 + 추가적인 작업 공간
• 예시:
  • 그래프: 배열 vs 연결리스트 표현 방식
• 분석 방식:
  • Worst-case, Average-case로 분석 가능

---

8. 알고리즘 분석이 필요한 이유

• 실행 속도는 입력 크기에 따라 급격히 달라짐
• 재귀 피보나치:
  • n=100일 경우, 재귀는 약 10²⁰초(약 10⁶⁷년), 반복은 100초
• 실생활 데이터 규모:
  • 구글 색인 웹페이지: 300억~500억
  • 인간 유전체: 약 32억 염기쌍
  • 은하의 별 개수: 약 1000억 개