자료구조: 점근적 분석

Cheatsheet Content

### 서론: 점근적 분석의 필요성 * **재귀 관계의 한계**: $T(n) = 2T(n/2) + n$ 와 같은 재귀 관계는 실행 시간의 구조를 나타내지만, 다음과 같은 질문에 답하지 못합니다: * '비용 단위'의 정확한 의미는 무엇인가? * 다양한 구현을 어떻게 비교할 것인가? * **알고리즘 분석의 목표**: * 시간, 공간, 에너지 등 자원 사용량을 일관성 있고 재현 가능하게 측정합니다. * 알고리즘의 성능을 하드웨어 및 구현과 독립적으로 비교합니다. * 알고리즘의 '성장률'에 초점을 맞춥니다. * **최악의 경우, 평균 경우, 최적의 경우 분석**: * **최악의 경우 (Worst-case)**: 주어진 크기의 입력에 대해 가장 긴 실행 시간. 가장 일반적이고 중요한 분석. * **평균 경우 (Average-case)**: 가능한 모든 입력에 대한 평균 실행 시간. 입력 분포에 대한 가정이 필요. * **최적의 경우 (Best-case)**: 주어진 크기의 입력에 대해 가장 짧은 실행 시간. 일반적으로 덜 유용함. ### 효율성 측정 방법 * **실험적 접근법 (Experimental Approach)**: * 실제 프로그램을 구현하고 다양한 입력 크기에 대해 실행 시간을 측정합니다. * **단점**: * 하드웨어, 운영체제, 백그라운드 작업, 입력의 종류에 따라 결과가 달라져 일반성이 떨어집니다. * 구현에 많은 시간과 노력이 소요됩니다. * 대규모 입력에 대한 예측이 어렵습니다. * **이론적 접근법 (Theoretical Approach)**: * 알고리즘이 수행하는 기본 연산의 수를 세어 비용을 측정합니다. * **장점**: 하드웨어와 독립적이며 수학적으로 분석 가능합니다. 일반적인 성능 예측에 유용합니다. * **RAM 모델 (Random Access Machine Model)**: * CPU와 무한한 메모리 셀을 가정합니다. * 모든 메모리 접근 및 기본 연산(산술, 할당, 비교, 비트 연산 등)은 상수 시간($O(1)$)이 걸린다고 가정합니다. * 메모리 계층 구조(캐시, 주 메모리 등)는 무시합니다. * 각 연산은 단위 비용을 가집니다. * **의사 코드 (Pseudocode)**: * 알고리즘을 공식적으로 기술하여 실행 시간을 추정하는 데 사용합니다. * 언어 및 특정 용어를 사용하여 단계별로 알고리즘을 요약합니다. ### 기본 연산 및 비용 함수 * **기본 연산 (Primitive Operations)**: 각 의사 코드 명령은 상수 시간 단계로 간주됩니다. * 예: 변수 할당, 산술 연산 (+, -, *, /), 비교 연산 (==, ), 배열 요소 접근 (A[i]), 함수 호출 및 반환, 포인터 역참조. * **비용 함수 (Cost Function)**: 알고리즘의 실행 시간 $T(n)$을 입력 크기 $n$의 함수로 표현합니다. * 예: 배열에서 최대 요소를 찾는 알고리즘은 총 $8n - 3$ 연산을 수행할 수 있습니다. ($T(n) = an + b$ 형태) * **주요 관심사**: * 정확한 상수 $a, b$보다는 입력 크기 $n$이 커질 때 $T(n)$이 어떻게 성장하는지에 초점을 맞춥니다. * 이를 **점근적 성장 (Asymptotic Growth)** 또는 **점근적 효율성 (Asymptotic Efficiency)**이라고 합니다. * **성장률의 중요성**: $n$이 충분히 커지면, 더 높은 성장률을 가진 항이 전체 실행 시간을 지배하게 됩니다. 예를 들어 $n^2$는 $1000n$보다 빠르게 성장합니다. ### Big-O 표기법 (상한) * **정의**: $f(n) \in O(g(n))$은 $n \ge n_0$인 모든 $n$에 대해 $f(n) \le c \cdot g(n)$을 만족하는 상수 $c > 0$와 자연수 $n_0$가 존재함을 의미합니다. * $O(g(n))$은 함수 $f(n)$의 **상한 (upper bound)**을 나타냅니다. 즉, $f(n)$은 $g(n)$만큼 빠르게 성장하거나 더 느리게 성장합니다. * **예시**: * $3n + 2 \in O(n)$ (단, $c=4, n_0=2$ 또는 $c=3.5, n_0=4$ 등) * $100n \in O(n^2)$ (단, $c=1, n_0=100$) * $5n^2 + 3n + 8 \in O(n^2)$ * **Big-O의 속성**: * **상수 인자 무시**: $k \cdot f(n)$은 $O(f(n))$입니다. (예: $5n \in O(n)$) * **더 높은 차수의 항**: $n^r$은 $0 1$인 모든 $b$에 대해 $O(b^n)$입니다. (지수 함수가 다항식보다 빠르게 성장합니다.) * **로그 함수**: $k>0$인 모든 $k$에 대해 $\log n \in O(n^k)$입니다. (로그 함수는 다항식보다 느리게 성장합니다.) * **로그 밑 무시**: 점근적으로 로그의 밑은 중요하지 않습니다. $\log_b n$은 $\log_d n$과 같은 $O(\log n)$입니다. ### Big-Omega (Ω) 표기법 (하한) * **정의**: $f(n) \in \Omega(g(n))$은 $n \ge n_0$인 모든 $n$에 대해 $f(n) \ge c \cdot g(n)$을 만족하는 상수 $c > 0$와 자연수 $n_0$가 존재함을 의미합니다. * $\Omega(g(n))$은 함수 $f(n)$의 **하한 (lower bound)**을 나타냅니다. 즉, $f(n)$은 $g(n)$만큼 빠르게 성장하거나 더 빠르게 성장합니다. * **예시**: * $3n + 2 \in \Omega(n)$ (단, $c=1, n_0=1$) * $n^2 \in \Omega(n)$ (단, $c=1, n_0=1$) * **용도**: 알고리즘이 아무리 최적화되어도 특정 문제에 대해 달성할 수 있는 최소 성능을 나타낼 때 사용합니다. 예를 들어, 정렬 알고리즘은 비교 기반 정렬의 경우 최악의 경우 $\Omega(n \log n)$입니다. * **관계**: $f(n) \in \Omega(g(n))$은 $g(n) \in O(f(n))$과 동치입니다. ### Big-Theta (Θ) 표기법 (정확한 경계) * **정의**: $f(n) \in \Theta(g(n))$은 $n \ge n_0$인 모든 $n$에 대해 $c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$을 만족하는 상수 $c_1, c_2 > 0$와 자연수 $n_0$가 존재함을 의미합니다. * $\Theta(g(n))$은 함수 $f(n)$의 **정확한 경계 (tight bound)**를 나타냅니다. 즉, $f(n)$과 $g(n)$은 동일한 성장률을 가집니다. * **관계**: $f(n) \in \Theta(g(n))$은 $f(n) \in O(g(n))$이면서 $f(n) \in \Omega(g(n))$인 경우와 같습니다. * **예시**: * $3n + 2 \in \Theta(n)$ * $5n^2 + 3n + 8 \in \Theta(n^2)$ * **용도**: 알고리즘의 실행 시간이 특정 함수와 동일한 성장률을 가질 때 사용합니다. 이는 가장 정확한 점근적 분석 결과를 제공합니다. ### Small-o (o) 및 Small-omega (ω) 표기법 * **Small-o (o)**: $f(n) \in o(g(n))$은 $f(n)$이 $g(n)$보다 **엄격하게 느리게 성장함**을 의미합니다. 즉, 어떤 $c > 0$에 대해서도 $n \ge n_0$인 모든 $n$에 대해 $0 \le f(n) 0$에 대해서도 $n \ge n_0$인 모든 $n$에 대해 $f(n) > c \cdot g(n)$입니다. * 또는 $\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$과 동치입니다. * **예시**: $n^2 \in \omega(n)$, $n^3 \in \omega(n^2)$ * **관계**: $f(n) \in o(g(n))$은 $g(n) \in \omega(f(n))$과 동치입니다. ### 일반적인 복잡도 클래스 * **성장률 순서 (느린 것부터 빠른 것까지)**: $O(1) ### 루프 분석: 점근적 시간 복잡도 계산 * **단일 루프**: 루프가 $N$번 반복되고 각 반복이 $O(1)$이면 총 $O(N)$입니다. ``` for i from 1 to N: // O(1) 연산 ``` * **중첩 루프**: 외부 루프가 $N$번, 내부 루프가 $M$번 반복되고 각 내부 반복이 $O(1)$이면 총 $O(N \cdot M)$입니다. $N=M$이면 $O(N^2)$입니다. ``` for i from 1 to N: for j from 1 to N: // O(1) 연산 ``` * **로그 루프**: 루프 변수가 각 반복마다 상수 비율로 증가하거나 감소하는 경우 (예: `i *= 2`, `i /= 2`). ``` i = 1 while i ### 분할 상환 분석 (Amortized Analysis) * **개념**: 일련의 연산에 대한 전체 비용을 분석하여, 개별 연산 중 일부가 매우 비쌀 수 있지만 전체 시퀀스에 걸친 평균 비용은 저렴함을 보여주는 기술입니다. * 데이터 구조에 $k$개의 연산을 수행할 때, 전체 실제 비용 $Actual\_Cost = \sum_{i=0}^{k-1} Cost\_of\_Operation_i$입니다. * **분할 상환 비용 (Amortized Cost)**: $Actual\_Cost / k$ * **목표**: 연산 시퀀스에 대한 최악의 경우를 보장합니다. 일부 비싼 연산은 자주 발생하지 않으므로, 전체적으로는 평균 비용이 낮게 유지됩니다. * **분할 상환 분석 vs. 평균 사례 분석**: * **평균 사례 분석**: 확률 분포에 의존하며, 입력 분포를 가정해야 합니다. 입력 분포를 알기 어렵거나 균등하지 않을 때 부정확할 수 있습니다. * **분할 상환 분석**: 확률적 가정이 필요 없으며, 연산 시퀀스에 대한 결정론적 보장을 제공합니다. 모든 입력 시퀀스에 대해 유효합니다. * **세 가지 기법**: * **집계 방법 (Aggregate Method)**: 전체 $k$개 연산에 대한 총 비용 $T(n)$의 상한을 계산한 다음, $T(n)/k$를 분할 상환 비용으로 사용합니다. * **예시: 동적 배열 (Dynamic Array)**: `push_back` 연산. 배열이 꽉 차면 크기를 두 배로 늘리고 모든 요소를 복사합니다. * $N$개의 요소를 추가하는 시퀀스를 고려합니다. * 확장 비용: $1+2+4+\dots+2^k \approx 2N$ (총 복사 연산 수). * 따라서 $N$개의 `push_back` 연산의 총 비용은 $O(N)$이며, 각 연산의 분할 상환 비용은 $O(1)$입니다. * **예시: 이진 카운터**: $N$번 증가. $i$번째 비트가 플립되는 횟수는 $N/2^i$번입니다. * 총 비트 플립 수 $\sum_{i=0}^{\log N} N/2^i = N \sum_{i=0}^{\log N} (1/2)^i