[Algorithm] Optimality Analysis

참고: GeeksforGeeks - Analysis of Algorithms | Big-O Analysis

수학 배경

\begin{align} &\sum^n_{i=1} i = \frac{n(n+1)}{2}\\ &\sum^n_{i=1} i^2 = \frac{2n^3 + 3n^2 + n}{6} \approx \frac{n^3}{3}\\ &\sum^n_{i=1} i^k \approx \frac{n^{k+1}}{k+1}\\ &\sum^k_{i=0} 2^i = 2^{k+1} - 1\\ &\sum^k_{i=1} i 2^i = (k-1)2^{k+1} + 2 \end{align}

학습할 내용

Amount of Work
Worst-Case Complexity
Average Complexity

함수 증가율 분류

complexity image

이미지 출처: GeeksforGeeks

$\Omega(g)$ : 함수 $g$ 보다 증가율이 높거나 같다.
$\Omega(g)$ is the set of functions $f$ , such that $f(n) \geq cg(n)$ for all $n \geq n_0$
$\Theta(g)$ : 함수 $g$ 와 같은 증가율을 가진다.
$\Theta(g) = O(g) \cap \Omega(g)$
$O(g)$ : 함수 $g$ 보다 증가율이 낮거나 같다.
$O(g)$ is the set of functions $f$ , such that $f(n) \leq c g(n)$ for all $n \geq n_0$

비교하는 방법

보통 최악의 경우를 위해 계산하기 때문에 무한대 상황을 가정한다.

\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}

결과값이 무한대로 갈 경우,
$f\in\omega(g)$ 또는 최소한 $f\in\Omega(g)$ 이다.

complexity image2

이미지 출처: GeeksforGeeks

$O(g),\ \Theta(g),\ \Omega$ 의 성질

Transitive: 만약 $f \in O(g)$ 와 $g \in O(h)$ 이면, $f \in O(h)$ 는 transitive하다.
또한 $\Omega, \Theta, o, \omega$ 는 transitive하다.
Reflexive: $f \in \Theta(f)$
Symmetric: 만약 $f \in \Theta(g)$ 이면, $g \in \Theta(f)$ 이다.

$f \in O(g) \leftrightarrow g \in \Omega(f)$ 이면
$O(f + g) = O(\max(f, g))$ 와 $\Omega(f + g) = \Omega(\max(f, g))$ 를 만족한다.

알고리즘과 문제 분석

조건1: Correctness가 증명되어야 한다

if the preconditions are satisfied
then the postconditions will be true
when the algorithm terminates.

조건2: Amount of Work Done

A measure of work
- input 사이즈
Basic Operation
- 문제 해결을 위한 근본적인 연산

Worst-Case Complexity

$D_n$ $D_{n}$ 이 크기가 $n$ $n$ 인 input 사이즈를 가지고 있다.
- $I$ 는 $D_n$ 의 원소를 의미한다.
$t(I)$ 는 input $I$ 에 대해, basic operation의 수를 의미한다.
함수 $W$ 는 $W(n) = \max\{t(I)\mid I \in D_n\}$ 라 정의한다.

Average Complexity

$Pr(I)$ 는 입력 $I$ 가 발생할 확률이다.
평균 알고리듬 수행시간은 다음과 같이 정의한다.
- $A(n) = \sum_{i\in D_n}Pr(I)t(I)$
$t(I)$ 로 알고리듬을 분석한다.

예시

int seqSearch(int E[], int n, int K) {
    int ans = -1; // Assume failure

    for (int index = 0; index < n; index++) {
        if (K == E[index]) {
            ans = index; // Success
            break; // Done
        }
    }

    return ans;
}

Worst Case

array에 값이 없을 경우.
array 마지막 원소가 $K$ 일 경우. 는 값이 없거나 맨 마지막에 값이 있을 경우이니, $W(n) = n$ 이다.

Average Behavior Analysis

A(n) = Pr(\text{succ})A_{\text{succ}}(n) + Pr(\text{fail})A_{\text{fail}}(n)

가정

$Pr(I_i\mid \text{succ}) = 1/n$
$Pr(\text{succ}) = p$
$Pr(\text{fail}) = 1-p$

성공하는 경우에는 $K$ 가 배열의 어느 위치에든 같은 확률로 존재한다고 가정한다. $I_i$ 는 $K$ 가 $i$ 번째 위치에서 발견되는 입력을 의미한다.

성공 시 평균 비교 횟수는 다음과 같다.

\begin{align} A_{\text{succ}}(n) &= \sum_{i=1}^{n} Pr(I_i \mid \text{succ})t(I_i) \\ &= \sum_{i=1}^{n} \frac{1}{n}i \\ &= \frac{1}{n}\sum_{i=1}^{n}i \\ &= \frac{n+1}{2} \end{align}

실패하는 경우에는 배열 전체를 끝까지 확인해야 한다.

A_{\text{fail}}(n) = n

따라서 전체 평균 수행시간은 다음과 같다.

\begin{align} A(n) &= pA_{\text{succ}}(n) + (1-p)A_{\text{fail}}(n) \\ &= p\frac{n+1}{2} + (1-p)n \end{align}

만약 성공 확률과 실패 확률이 각각 $\frac{1}{2}$ 이라면 다음과 같이 계산된다.

\begin{align} A(n) &= \frac{1}{2}\frac{n+1}{2} + \frac{1}{2}n \\ &= \frac{3n+1}{4} \end{align}

결국 순차 탐색의 평균 수행시간도 $n$ 에 비례한다.

A(n) \in \Theta(n)

Best, Worst, Average Case 비교

알고리즘을 분석할 때는 같은 알고리즘이라도 어떤 입력을 받는지에 따라 수행시간이 달라진다. 따라서 보통 다음 세 가지 관점으로 나누어 생각한다.

분석 기준	의미	Sequential Search 예시
Best Case	가장 빨리 끝나는 입력	첫 번째 원소가 $K$ 인 경우
Worst Case	가장 늦게 끝나는 입력	$K$ 가 없거나 마지막에 있는 경우
Average Case	입력 분포를 고려한 평균	$K$ 의 위치와 실패 확률을 고려한 경우

Best Case는 알고리즘의 가장 좋은 상황을 보여주지만, 일반적인 성능을 대표하기 어렵다. Worst Case는 어떤 입력이 들어와도 보장할 수 있는 상한을 제공하기 때문에 알고리즘 분석에서 자주 사용된다. Average Case는 실제 사용 환경을 더 잘 반영할 수 있지만, 입력이 어떤 확률 분포를 따르는지 가정해야 한다.

예제: Nested Loop

다음 코드를 분석해보자.

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) {
        count++;
    }
}

내부 반복문은 $i$ 값에 따라 실행 횟수가 달라진다. 전체 실행 횟수는 다음과 같다.

\sum_{i=1}^{n} i = \frac{n(n+1)}{2}

상수와 낮은 차수 항은 $n$ 이 커질수록 영향이 작아진다.

\frac{n(n+1)}{2} = \frac{n^2+n}{2} \in \Theta(n^2)

따라서 이 코드는 $O(n^2)$ 이면서 동시에 $\Omega(n^2)$ 이므로 $\Theta(n^2)$ 이다.

예제: Binary Search

Binary Search는 정렬된 배열에서 중간 값을 기준으로 탐색 범위를 절반씩 줄인다.

int binarySearch(vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (arr[mid] == target) {
            return mid;
        }

        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

입력 크기가 $n$ 일 때, 반복할 때마다 탐색 범위는 아래처럼 줄어든다.

n,\ \frac{n}{2},\ \frac{n}{4},\ \frac{n}{8},\ \cdots

$k$ 번 반복한 뒤 탐색 범위가 1 이하가 된다고 하면 다음을 만족한다.

\frac{n}{2^k} \leq 1

따라서

n \leq 2^k

양변에 로그를 취하면

k \geq \log_2 n

즉 Binary Search의 worst-case complexity는 다음과 같다.

W(n) \in \Theta(\log n)

증가율 비교

알고리즘의 정확한 실행 시간은 하드웨어, 컴파일러, 구현 방식에 따라 달라질 수 있다. 하지만 입력 크기가 충분히 커지면 증가율이 더 중요한 기준이 된다.

대표적인 증가율은 다음 순서로 커진다.

O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n) < O(n!)

Complexity	대표 예시
$O(1)$	배열 index 접근
$O(\log n)$	Binary Search
$O(n)$	Sequential Search
$O(n\log n)$	Merge Sort, Heap Sort
$O(n^2)$	단순 이중 반복문, Bubble Sort
$O(2^n)$	부분집합 전체 탐색
$O(n!)$	순열 전체 탐색

중요한 것은 작은 입력에서는 $O(n^2)$ 알고리즘이 더 빠를 수도 있다는 점이다. Big-O는 실제 시간을 직접 말하는 것이 아니라, 입력 크기가 커질 때의 증가 경향을 설명한다.

알고리즘 분석 절차

알고리즘을 분석할 때는 아래 순서로 접근하면 된다.

입력 크기 $n$ 을 정의한다.
Basic Operation을 정한다.
Basic Operation이 몇 번 실행되는지 계산한다.
Best, Worst, Average 중 어떤 기준으로 분석하는지 정한다.
가장 지배적인 항만 남겨 asymptotic notation으로 표현한다.

예를 들어 이중 반복문이라도 항상 $O(n^2)$ 인 것은 아니다. 반복문의 범위가 어떻게 변하는지, 중간에 종료되는 조건이 있는지, 입력의 구조가 어떤지까지 함께 봐야 한다.

정리

Optimality Analysis는 단순히 코드를 보고 반복문 개수를 세는 것이 아니다. 알고리즘이 올바르게 동작한다는 correctness를 확인한 뒤, 입력 크기에 따라 필요한 work가 어떻게 증가하는지 분석하는 과정이다.

$O(g)$ 는 upper bound를 의미한다.
$\Omega(g)$ 는 lower bound를 의미한다.
$\Theta(g)$ 는 tight bound를 의미한다.
Worst Case는 모든 입력에 대해 보장 가능한 성능을 보여준다.
Average Case는 입력의 확률 분포를 가정해야 계산할 수 있다.

알고리즘 문제를 풀 때도 이 분석이 중요하다. 제한 조건에서 $n$ 의 크기를 먼저 보고, 허용 가능한 시간복잡도를 예상한 뒤 풀이 방법을 선택해야 한다.