[Algorithm] Optimality Analysis

Reference

Mathematics Background

\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}

To study

Amount of Work
Worst-Case Complexity
Average Complexity

Classifying Functions

complexity image

$\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\infin}\frac{f(n)}{g(n)}

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

complexity image2

$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))$ 를 만족한다.

Analyzing Algorithms and Problems

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

if the preconditions are satisfied
then the postconditions will be treu
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, index;
    ans = -1; // Assume failure
    for (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$