01. Algorithm_Analysis and Recurrences

학습 목표

• 알고리즘의 정의, 바람직한 알고리즘의 조건, 표기법 네 가지
• 알고리즘을 분석하는 이유와 수행 시간을 좌우하는 요소
• 점근적 표기법 O, Ω, Θ, o, ω의 정의와 증명 방법
• 점화식의 의미와 재귀 알고리즘의 관계
• 반복 대치로 팩토리얼과 병합 정렬의 수행 시간 구하기
• 마스터 정리로 점화식의 복잡도를 바로 구하기

---

1. 알고리즘이란

• 문제 해결 절차를 체계적으로 기술한 것. 어떤 작업을 하기 위해 입력을 받아 출력을 만들어 내는 과정을 애매하지 않게 적은 것
• 문제의 요구 조건은 입력과 출력으로 명시하고, 알고리즘은 입력으로부터 출력을 만드는 과정을 기술함
  • 예: “학생 100명의 점수 중 최댓값 찾기”에서 입력은 점수 100개, 출력은 최댓값
• 알고리즘의 핵심은 코드 자체보다 생각하는 방법

바람직한 알고리즘의 조건

• 명확성: 이해하기 쉽고 간명해야 함
• 효율성: 같은 문제를 더 적은 자원(주로 시간)으로 풀어야 함

표기법 네 가지

자연어, 순서도, 프로그래밍 언어, 가상코드(pseudocode). 가상코드는 특정 언어의 문법에 묶이지 않으면서 절차를 명확하게 표현할 수 있음.

자료구조와 알고리즘은 따로 노는 것이 아니라, 자료구조는 데이터를 저장하고 조직하는 방식, 알고리즘은 그 데이터를 처리하는 절차로서 함께 문제를 품.

---

2. 알고리즘 분석

왜 분석하는가

• 정확성 확인: 원하는 결과가 나오는가, 시작하면 반드시 끝나는가
• 자원 효율성 파악: 주로 시간을 따짐

수행 시간을 좌우하는 것

• 수행 시간에 영향을 주는 요소: 입력의 크기와 알고리즘의 실행 절차
• 수행 시간의 기준: 특정 행이 수행되는 횟수, 함수 호출 횟수

알고리즘	구조	수행 시간
배열의 가운데 원소 찾기	반복 없음	\(O(1)\)
배열의 모든 원소의 합	for 1개	\(O(n)\)
모든 원소쌍의 곱의 합	for 2개	\(O(n^2)\)
\(n^2\)번 반복하며 매번 배열 절반 중 최댓값을 더함	for 3개	\(O(n^3)\)
팩토리얼 (재귀)	재귀 n번	\(O(n)\)

재귀적 구조: 어떤 문제 안에 크기만 다르고 똑같은 작은 문제가 들어 있는 구조 (예: \(n! = n \times (n-1)!\)).

---

3. 점근적 표기법

점근적 분석: 입력 크기 \(n\)이 충분히 클 때의 증가율만 보는 분석. 상수배와 낮은 차수 항은 무시함 (예: \(3n\), \(100n\), \(0.5n\)은 모두 같은 차수).

(중요!!) 표기법의 정의와 증명은 매번 출제됨

표기	의미	정의
\(O(g(n))\)	점근적 상한 (\(\le\))	양수 \(c\), \(n_0\)가 있어 모든 \(n \ge n_0\)에서 \(f(n) \le c\,g(n)\)
\(\Omega(g(n))\)	점근적 하한 (\(\ge\))	양수 \(c\), \(n_0\)가 있어 모든 \(n \ge n_0\)에서 \(f(n) \ge c\,g(n)\)
\(\Theta(g(n))\)	점근적으로 같음	양수 \(c_1\), \(c_2\), \(n_0\)가 있어 모든 \(n \ge n_0\)에서 \(c_1 g(n) \le f(n) \le c_2 g(n)\)
\(o(g(n))\)	여유 있는 상한 (\(<\))	모든 양수 \(c\)에 대해 어떤 \(n_0\) 이후 \(f(n) < c\,g(n)\)
\(\omega(g(n))\)	여유 있는 하한 (\(>\))	모든 양수 \(c\)에 대해 어떤 \(n_0\) 이후 \(f(n) > c\,g(n)\)

• \(O\), \(\Omega\), \(\Theta\)는 함수들의 집합. \(f(n) = O(g(n))\)은 사실 \(f(n) \in O(g(n))\)이라는 뜻
• \(\Theta(g(n))\)은 \(O(g(n))\)과 \(\Omega(g(n))\)을 둘 다 만족하는 함수들
• \(o(n^2)\)는 \(n^2\)보다 증가율이 확실히 작은 함수(\(n\), \(n \log n\) 등), \(\omega(n^2)\)는 확실히 큰 함수(\(n^3\) 등)

증명 예시

\(f(n) = 3n^2 + 2n + 5\)라고 하자.

• O 증명: \(n \ge 1\)이면 \(2n \le 2n^2\), \(5 \le 5n^2\)이므로 \(f(n) \le 3n^2 + 2n^2 + 5n^2 = 10n^2\). 따라서 \(c = 10\), \(n_0 = 1\)로 \(f(n) = O(n^2)\)
• Ω 증명: 모든 \(n \ge 1\)에서 \(f(n) \ge 3n^2\)이므로 \(c = 3\), \(n_0 = 1\)로 \(f(n) = \Omega(n^2)\)
• Θ 증명: 위 두 결과를 합치면 \(3n^2 \le f(n) \le 10n^2\) (\(n \ge 1\))이므로 \(f(n) = \Theta(n^2)\)
• o 판단: \(\lim_{n \to \infty} \frac{f(n)}{n^3} = 0\)이므로 \(f(n) = o(n^3)\)이지만, \(\frac{f(n)}{n^2} \to 3 \ne 0\)이라 \(f(n) \ne o(n^2)\)

증명의 요령: 상한은 낮은 차수 항을 최고차 항으로 키워서 묶고, 하한은 양수 항을 버려서 묶음. \(c\)와 \(n_0\)를 구체적으로 제시해야 증명이 됨

---

4. 재귀 알고리즘과 점화식

점화식: 어떤 함수를 자신보다 작은 입력에 대한 같은 함수로 표현한 식. 재귀 알고리즘은 큰 문제를 작은 같은 문제로 나눠 다시 호출하므로, 수행 시간이 자연스럽게 점화식이 됨.

알고리즘	점화식	의미
팩토리얼	\(T(n) = T(n-1) + c\)	크기 \(n-1\) 문제 하나 + 곱셈 한 번
병합 정렬	\(T(n) = 2T(n/2) + n\)	크기 \(n/2\) 문제 두 개 + 병합 오버헤드
이진 검색	\(T(n) = T(n/2) + c\)	절반 크기 문제 하나 + 비교 한 번

점화식의 점근적 분석 방법 세 가지: 반복 대치, 추정 후 증명, 마스터 정리.

반복 대치: 팩토리얼

식을 계속 대입해서 펼치면

식으로 쓰면 \(T(n) = T(n-1) + c = T(n-2) + 2c = \cdots = T(1) + (n-1)c\)

\(T(1) = c\)이므로 \(T(n) = nc = O(n)\)

반복 대치: 병합 정렬

\(n = 2^k\)라고 두고 펼치면

식으로 쓰면 \(T(n) = 2T(n/2) + n = 4T(n/4) + 2n = \cdots = 2^k T(n/2^k) + kn\)

\(k = \log_2 n\)이면 \(T(n/2^k) = T(1) = 1\)이므로 \(T(n) = n + n \log_2 n = \Theta(n \log n)\)

마스터 정리

\(T(n) = aT(n/b) + f(n)\) (\(a \ge 1\), \(b > 1\)) 꼴이면 \(h(n) = n^{\log_b a}\)와 \(f(n)\)의 증가율을 비교해서 바로 답을 얻음.

1. \(h(n)\)이 다항식 차수만큼 더 크면 \(T(n) = \Theta(h(n))\)
2. 둘이 같은 차수면 \(T(n) = \Theta(h(n) \log n)\)
3. \(f(n)\)이 다항식 차수만큼 더 크고, 어떤 \(c < 1\)에 대해 \(af(n/b) \le cf(n)\)(정규 조건)이면 \(T(n) = \Theta(f(n))\)

직관적으로는 “재귀 트리에서 리프 쪽 일(\(h(n)\))과 루트 쪽 일(\(f(n)\)) 중 큰 쪽이 전체를 결정하고, 같으면 층 수(\(\log n\))만큼 곱해진다”는 뜻.

---

5. Python으로 확인하기

반복 구조별 연산 횟수, 점화식을 직접 계산한 값과 닫힌 식, 마스터 정리 결과를 한 번에 출력함.

import math
from functools import lru_cache

# 1) 반복문 구조에 따른 기본 연산 횟수
def count_ops(n):
    middle = 1                                        # 가운데 원소 하나 읽기
    total = sum(1 for _ in range(n))                  # 모든 원소 더하기
    pairs = sum(1 for i in range(n) for j in range(n))  # 모든 원소쌍
    return middle, total, pairs

print("n      O(1)   O(n)     O(n^2)")
for n in [10, 100, 1000]:
    print(f"{n:<6}", "  ".join(f"{c:<7}" for c in count_ops(n)))

# 2) 점화식을 직접 계산해서 닫힌 식과 비교
def T_fact(n):            # 팩토리얼: T(n) = T(n-1) + c, T(1) = c  (c = 1), 반복문으로 펼쳐서 계산
    t = 1
    for _ in range(2, n + 1):
        t = t + 1
    return t

@lru_cache(None)
def T_merge(n):           # 병합 정렬: T(n) = 2T(n/2) + n, T(1) = 1
    return 1 if n <= 1 else 2 * T_merge(n // 2) + n

@lru_cache(None)
def T_quarter(n):         # T(n) = T(n/4) + 1, T(1) = 1
    return 1 if n <= 1 else T_quarter(n // 4) + 1

print("\nn         T_fact  T_merge     n*log2(n)+n  T_quarter  log4(n)+1")
for k in [4, 8, 12, 16, 20]:
    n = 2 ** k
    print(f"{n:<9} {T_fact(n):<7} {T_merge(n):<11} {int(n * math.log2(n) + n):<12} "
          f"{T_quarter(n):<10} {math.log(n, 4) + 1:.0f}")

# 3) 마스터 정리: T(n) = aT(n/b) + f(n), f(n) = n^d 꼴일 때
def master(a, b, d):
    e = math.log(a, b)                        # h(n) = n^(log_b a)
    if abs(d - e) < 1e-9:
        return f"Θ(n^{d:g} log n)  (f(n)과 h(n) = n^{e:g}의 차수가 같음)"
    if d < e:
        return f"Θ(n^{e:.3g})  (h(n) = n^{e:.3g}가 더 큼)"
    return f"Θ(n^{d:g})  (f(n)이 더 큼)"

for a, b, d, name in [(2, 2, 1, "병합 정렬 2T(n/2)+n"), (1, 2, 0, "이진 검색 T(n/2)+1"),
                      (1, 4, 0, "T(n/4)+1"), (4, 2, 1, "4T(n/2)+n"), (2, 2, 2, "2T(n/2)+n^2"),
                      (7, 2, 2, "Strassen 7T(n/2)+n^2")]:
    print(f"{name:<22} -> {master(a, b, d)}")

실행 결과

n      O(1)   O(n)     O(n^2)
10     1        10       100    
100    1        100      10000  
1000   1        1000     1000000

n         T_fact  T_merge     n*log2(n)+n  T_quarter  log4(n)+1
16        16      80          80           3          3
256       256     2304        2304         5          5
4096      4096    53248       53248        7          7
65536     65536   1114112     1114112      9          9
1048576   1048576 22020096    22020096     11         11
병합 정렬 2T(n/2)+n        -> Θ(n^1 log n)  (f(n)과 h(n) = n^1의 차수가 같음)
이진 검색 T(n/2)+1         -> Θ(n^0 log n)  (f(n)과 h(n) = n^0의 차수가 같음)
T(n/4)+1               -> Θ(n^0 log n)  (f(n)과 h(n) = n^0의 차수가 같음)
4T(n/2)+n              -> Θ(n^2)  (h(n) = n^2가 더 큼)
2T(n/2)+n^2            -> Θ(n^2)  (f(n)이 더 큼)
Strassen 7T(n/2)+n^2   -> Θ(n^2.81)  (h(n) = n^2.81가 더 큼)

• 병합 정렬 점화식을 그대로 계산한 값이 \(n \log_2 n + n\)과 정확히 같음 (반복 대치 결과 확인)
• \(T(n/4) + 1\)은 \(\log_4 n + 1\)로, \(n\)이 4배가 될 때마다 1씩만 늘어남
• 마스터 정리에서 \(n^0 \log n\)은 \(\log n\). 이진 검색과 \(T(n/4)+1\)은 모두 \(\Theta(\log n)\) (로그의 밑은 상수배 차이라 무시)

---

정리 노트에서 정정한 부분 정리

위치	원래	정정	이유
점근적 표기법	O는 점근적 상한(Tight), o는 상한(Loose)	O는 상한(\(\le\), 딱 맞지 않아도 됨), o는 엄격한 상한(\(<\)). 딱 맞는(tight) 것은 Θ	\(n = O(n^2)\)도 참이므로 O는 tight하지 않을 수 있음
빅세타의 직관	빅오와 빅세타가 같아야 정의 가능	빅오와 빅오메가를 둘 다 만족해야 Θ	Θ의 정의는 상한과 하한을 동시에 만족하는 것
마스터 정리 3번 경우	(조건 없이) f(n)이 크면 Θ(f(n))	정규 조건 \(af(n/b) \le cf(n)\)이 필요	정규 조건을 만족하지 않는 반례가 있음

---

최종 핵심 정리

1. 알고리즘은 입력에서 출력을 만드는 절차를 애매하지 않게 기술한 것이고, 명확성과 효율성을 갖춰야 함
2. 표기법은 자연어, 순서도, 프로그래밍 언어, 가상코드가 있고, 가상코드는 언어에 독립적
3. 수행 시간은 입력 크기와 실행 절차가 좌우하며, 반복문 중첩 수가 차수를 결정하는 경우가 많음
4. O는 상한, Ω는 하한, Θ는 둘 다, o와 ω는 엄격한 상한과 하한이며, 증명은 \(c\)와 \(n_0\)를 제시하는 것
5. 재귀 알고리즘의 수행 시간은 점화식으로 표현됨 (팩토리얼 \(T(n-1)+c\), 병합 정렬 \(2T(n/2)+n\))
6. 반복 대치로 팩토리얼은 \(O(n)\), 병합 정렬은 \(n \log_2 n + n = \Theta(n \log n)\)
7. 마스터 정리는 \(n^{\log_b a}\)와 \(f(n)\)을 비교해 큰 쪽이 결정하고, 같으면 \(\log n\)을 곱함
8. 점화식을 코드로 직접 계산하면 손으로 구한 닫힌 식이 맞는지 바로 확인할 수 있음

---

End.