효율, 분석, 차수

🍒 알고리즘이란

문제에 대한 답을 찾기 위해 계산하는 절차
단계별로 주의 깊게 설계된 계산 과정
입력을 받아 출력으로 전환시켜주는 일련의 계산 절차

🍒 순차 검색

알고리즘

문제: n개의 키로 구성된 배열 S에 키 x가 있는가?
입력: 양의 정수 n, 배열 S, 키 x
출력: 키 x가 배열에 있으면 그것의 index, 없으면 -1

예시 코드

void seqsearch(int n, const keytype S[], keytype x, index & location) {
    location = 1;
    while(location <= n && S[location] != x)
        location++;
    if (location < n)
        location = -1;
}

비교 횟수

순차 검색 알고리즘으로 키를 찾기 위해서 검색해야 하는 항목은 키와 같은 항목의 위치에 따라 개수가 달라짐
최악의 경우 n (data 개수)
S에 있는 항목에 대한 정보가 없는 한 더 빨리 찾을 수 없음

🍒 합계 알고리즘

알고리즘

문제: n개의 수로 구성된 배열 S에 있는 모든 수의 합은?
입력: 양의 정수 n, 배열 S
출력: 배열 S에 있는 모든 수의 합

예시 코드

number sum(int n, const number S[]) {
    index i = 1;
    number result = 0;
    for (i = 1; i <= n; i++)
        result = result + S[i];
    return result;
}

🍒 교환 정렬

알고리즘

문제: n개의 수로 구성된 배열 S를 오름차순으로 정렬하라.
입력: 양의 정수 n, 배열 S
출력: 오름차순으로 정렬된 배열 S

예시 코드

void exchangeSort(int n, number[] S) {
    index i, j;
    for(i = 1, i <= n; i++) {
        for(j = i+1; j <= n; j++) {
            if(S[j] < S[i]) swap S[i] and S[j];
        }
    }
}

🍒 이진 검색

알고리즘

문제: n개의 키로 구성된 정렬된 배열 S에 키 x가 있는가?
입력: 양의 정수 n, 오름차순으로 정렬된 배열 S, 키 x
출력: 키 x가 배열에 있으면 그것의 index, 없으면 0

예시 코드

void binSearch(int n, const keytype S[], keytype x, index & location) {
    index low, high, mid;
    low = 1; high = n;
    location = 0;
    while(low <= high && location == 0) {
        mid = floor((low + high) / 2);
        if (x == S[mid])
            location = mid;
        else if (x < S[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }
}

비교 연산은 1번

비교 횟수

while문을 수행할 때마다 검색 대상의 크기가 반 씩 감소하기 때문에 최악의 경우라도 ⌊lg N⌋ + 1개만 검사하면 됨
+1 : mid를 구할 때 floor 함수를 이용했기 때문에 mid 뒷부분은 data가 한 개 더 많을 수 있기 때문
비교 횟수 ∝ 트리의 높이

🍒 효율적인 알고리즘 개발의 중요성

순차검색 vs. 이진검색

순차검색: S의 크기가 n이면 최대 n번 비교
이진검색: S의 크기가 n이면 최대 lgn + 1번 비교

피보나치 수열

재귀적 정의

$f_0 = 0$
$f_1 = 1$
$f_n = f_{n-1} + f_{n-2}$

알고리즘

문제: 피보나치 수열의 n번째 항 결정
입력: 음이 아닌 정수 n
출력: 피보나치 수열의 n번째 항

코드

int fib(int n) {
    if(n <= 1) return n;
    else return fib(n-1) + fib(n-2);
}

수행 속도

피보나치 재귀 알고리즘은 수행속도가 매우 느림
- 같은 피보나치 수를 중복 계산하기 때문
- ex) fib(5) 계산에 fib(2) 3번 중복 계산 필요

함수 호출 횟수

n이 2 증가할 때마다 계산하는 항의 수는 2배 이상 증가

T(n): 입력이 n일 때 재귀 트리의 항 수
T(n) > 2 x T(n-2)
T(n) > 2 x 2 x T(n-4)
…
T(n) > 2 x 2 x … x 2 x T(0)
-> T(n) > $2^{n/2}$

cf. n = 1일 땐 성립하지 않음

점화식 (재귀식)

수학적 귀납법에서와 같이 첫 번째 요소가 정의되고, n+1번째 요소는 바로 앞의 n번째와 그 이하의 요소와의 관계로서 정의될 경우

수학적 귀납법 증명 방법

명제 $p_1, p_2, p_3, …, p_n$이 사실이라고 할 때 $p_{n+1}$의 경우에도 성립
n이 1인 경우에 성립하는 것을 보이고, 모든 양의 정수 n에 대해 성립한다고 가정하면 n+1의 경우에도 성립하는 것을 보여주면 됨
basis: 출발점이 되는 n의 값
inductive assumption: $p_1, p_2, p_3, …, p_n$이 성립한다고 가정
inductive step: $p_{n+1}$의 경우에도 성립

개선된 피보나치 알고리즘

동적 프로그래밍 방법
중복 계산 없이, 구해놓은 값을 저장해놓고 참조
계산하는 항의 총 개수
- T(n) = n + 1
- 즉, f[0]부터 f[n]까지 한 번씩만 계산

int fib2(int n) {
    index i;
    int f[0..n];
    f[0] = 0;
    f[1] = 1;
    if(n > 1) {
        for(i = 2; i <= n; i++)
            f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

두 피보나치 알고리즘의 비교

🍒 행렬 곱셈

알고리즘

문제: 두 n x n 행렬의 곱을 구하여라.
입력: 정수 n (n>0), 수의 2차원 배열 A, B
출력: 결과 행렬 C

예시 코드

void matrixmult(int n, const number A[][], const number B[][], number C[][]) {
    index i, j, k;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= n; j++) {
            C[i][j] = 0;
            for(k = 1; k <= n; k++) 
                C[i][j] = C[i][j] + A[i][k] * B[k][j];
        }
    }
}

🍒 알고리즘 분석

기본 연산이 몇 번 수행되는지

시간복잡도 분석

입력 크기에 따라 단위연산이 몇 번 수행되는지 결정하는 절차
일반적으로 알고리즘 수행 시간은 입력의 크기에 따라 증가

표현 척도

단위 연산
- 비교, 지정(할당, 덧셈, 곱셈)
입력 크기
- 배열의 크기, 리스트의 길이, 행렬에서 행과 열의 크기, 트리에서 마디와 이음선의 수

분석 방법의 종류

일정시간(모든 경우) 분석
- 입력 크기에만 종속
- 입력값과는 무관하게 결과 값은 항상 일정
최악의 경우 분석
- 입력 크기와 입력값 모두에 종속
- 단위연산이 수행되는 횟수가 최대인 경우 선택
평균인 경우 분석
- 입력 크기와 입력값 모두에 종속
- 모든 입력에 대해 단위연산이 수행되는 기대치(평균)
- 각 입력에 대해서 확률 할당 가능
- 일반적으로 최악의 경우보다 계산 복잡
최선의 경우 분석
- 입력 크기와 입력값 모두에 종속
- 단위연산이 수행되는 횟수가 최소인 경우 선택

합계 알고리즘

합을 구할 때 모든 data 더해야 함 -> every case

단위연산: 덧셈
입력 크기: 배열의 크기 n
모든 경우 분석
- 배열의 내용에 상관없이 for-loop가 모든 data에 대해 n번 반복됨
- 각 루프마다 덧셈이 1회 수행됨
- 따라서, n에 대해서 덧셈이 수행되는 총 횟수 T(n) = n

number sum(int n, number[] S) {
    index i = 1;
    number result = 0;
    for(i = 1; i <= n; i++)
        result = result + S[i];
    return result;
}

교환정렬 알고리즘

자리바꿈으로 비교 -> 모든 data 다 활용하여 비교 연산

단위연산: 조건문(S[j]와 S[i]의 비교)
입력 크기: 정렬할 항목의 수 n
일정 시간 분석
- j-loop가 수행될 때마다 조건문 1번씩 수행
- 조건문의 총 수행횟수
  i = 1     : j-loop (n-1) 번 수행
  i = 2     : j-loop (n-2) 번 수행
  i = 3     : j-loop (n-3) 번 수행
  …
  i = n-1 : j-loop 1 번 수행
  따라서
  $T(n) = (n-1) + (n-2) + … + 1 = \frac{(n-1)n}{2}$

void exchangeSort(int n, number[] S) {
    index i, j;
    for(i = 1; i <= n; i++) {
        for(j = i+1; j <= n; j++)
            if(S[j] < S[i]) swap S[i] and S[j];   // 비교연산
    }
}

🍒 행렬곱셈 알고리즘 시간복잡도

단위연산: 가장 안 쪽 루프 안의 곱셈
입력 크기: 행과 열의 개수, n
일정 시간 분석
- for -i, for -j, for-k 루프가 항상 n번 실행됨
- $T(n) = n * n * n = n^3$

void matrixmult(int n, const number A[][], const number B[][], number C[][]) {
    index i, j, k;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= n; j++) {
            C[i][j] = 0;
            for(k = 1; k <= n; k++)
                C[i][j] = C[i][j] + A[i][k] * B[k][j];
        }
    }
}

🍒 순차검색 알고리즘 시간복잡도

최악의 경우

단위연산: 배열의 아이템과 키 x와 비교 연산 S[location] != x
입력 크기: 배열 안에 있는 아이템 수 n
최악의 경우 분석
- x가 배열의 마지막 data이거나, x가 배열에 없는 경우 단위연산이 n번 수행됨
- W(n) = n
  - W() : Worst case
순차검색 알고리즘의 경우 입력 배열의 값에 따라서 검색하는 횟수가 달라지므로 모든 경우 분석은 불가능

최선의 경우

단위연산: 배열의 아이템과 키 x와 비교 연산 S[location] != x
입력 크기: 배열 안에 있는 아이템 수 n
최선의 경우 분석
- x가 S[1]일 때, 입력의 크기에 상관없이 단위연산이 1번만 수행됨
- B(n) = 1
  - B() : Best case

평균의 경우

단위연산: 배열의 아이템과 키 x와 비교 연산 S[location] != x
입력 크기: 배열 안에 있는 아이템 수 n
평균의 경우 분석
- 배열의 data가 모두 다르다고 가정
- Case 1) x가 배열 S 안에 있는 경우만 고려
  - 1 ≤ k ≤ n에 대해서 x가 배열의 k번째 있을 확률 = $\frac{1}{n}$
  - x가 배열의 k번째에 있다면, x를 찾기 위해 수행하는 단위연산 횟수 = k
  - $A(n) = \sum_{k=1}^{n} k * \frac{1}{n} = \frac{1}{n} * \sum_{k=1}^{n} k = \frac{1}{n} * \frac{n(n+1)}{2} = \frac{n+1}{2}$
    - A(n) : Average case
- Case 2) x가 배열 S 안에 없는 경우도 고려
  - x가 배열 S 안에 있을 확률 p
    - x가 배열의 k번째에 있을 확률 = $\frac{p}{n}$
      - 각 자리에 있을 확률이 $\frac{1}{n}$ → $p * \frac{1}{n}$
    - x가 배열에 없을 확률 = $1 - p$
  - $A(n) = \sum_{k=1}^{n} (k * \frac{p}{n}) + n(1-p)
    \qquad\;\, = \frac{p}{n} * \frac{n(n+1)}{2} + n(1-p)
    \qquad\;\, = n(1-\frac{p}{2}) + \frac{p}{2}$
  - p = 1 → $A(n) = \frac{n+1}{2}$ // case 1과 동일
  - p = 1/2 → $A(n) = \frac{3n}{4} + \frac{1}{4}$

🍒 정확도 분석

알고리즘이 의도한 대로 수행되는지를 증명하는 절차
정확한 알고리즘
- 어떠한 입력에 대해서도 답을 출력하면서 멈추는 알고리즘
정확하지 않은 알고리즘
- 어떤 입력에 대해서 멈추지 않거나 (답을 주지 않거나)
- 틀린 답을 출력하면서 멈추는 알고리즘

🍒 차수 (order)

알고리즘의 복잡도를 표시하기 위해 사용
n → ∞ 임을 가정하고 따짐
ex) 1000n 과 n²
- n < 1000 → 1000n > n²
- n > 1000 → 1000n < n²
- 계수가 아닌 차수를 보고 효율성 따짐!

대표적인 복잡도 카테고리

로그시간 Θ(lgn)
지수시간 Θ($2^n$)
계승시간 Θ(n!)

Big O

점근적 상한
주어진 복잡도 함수 f(n)에 대해, O(f(n))은 n ≥ N을 만족하는 모든 n에 대해 다음 부등식을 만족하는 양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합

$g(n) ≤ c * f(n)$

c: 어느 하나라도 만족하면 ok
g(n)이 c * f(n) 보다 위에서 시작하지만, 어느 시점이 되면 c * f(n) 보다 밑으로 내려가 계속 밑에 머뭄

g(n)이 O(n²)이고, g(n)이 어느 알고리즘의 시간복잡도
- 그 알고리즘의 실행시간은 이차함수와 같거나 좋음을 의미
- g(n)은 궁극에는 최소한 순수이차함수만큼은 좋다고 말할 수 있음
Big O는 함수의 궁극적인 상태만 고려하기 때문에 함수의 점근적인 상태를 나타낸다고 함
ex) 5n² ∈ O(n²) 임을 보여라
- 5n² ≤ 5n², n ≥ 0 ⇒ c = 5, N = 0
ex) n² + 10n ∈ O(n²) 임을 보여라
- n² + 10n ≤ cn²
- 방법1 n² + 10n ≤ 2n², n ≥ 10 ⇒ c = 2, N = 10
- 방법2 n² + 10n ≤ n² + 10n² = 11n², n ≥ 1 ⇒ c = 11, N = 1
ex) n ∈ O(n²) 임을 보여라
- n ≤ n², n ≥ 1 ⇒ c = 1, N = 1
- O(n²)에 포함되기 위해 복잡도 함수가 반드시 이차함수일 필요는 없음

Omega Ω

점근적 하한
주어진 복잡도함수 f(n)에 대해, Ω(f(n))은 n ≥ N을 만족하는 모든 N에 대해 다음 부등식을 만족하는 양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합

\[g(n) ≥ c * f(n)\]

g(n)은 아무리 좋아도 f(n)보다 좋을 수 없음
g(n)이 Ω(n²)이고, g(n)이 어떤 알고리즘의 시간복잡도
- 그 알고리즘의 실행시간은 이차함수와 같거나 그보다 좋을 수 없음을 의미

Theta Θ

주어진 복잡도 함수 f(n)에 대해 Θ(f(n))은 다음과 같이 정의됨
n ≥ N을 만족하는 모든 n에 대해 다음 부등식을 만족하는 양의 실수

\[Θ(f(n)) = O(f(n)) \, ∩ \, Ω(f(n))\]

Big O, omega에 속함
c, d, 음이아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합

\[c * f(n) ≤ g(n) ≤ d * f(n) ⇒ Θ(f(n))\]

g(n) ∈ Θ(f(n)) ⇒ g(n)의 차수 : f(n)

점근적인 함수들의 관계

O(f) : f보다 빠르게 성장하지 않는 (효율적인) 함수
Θ(f) : f와 비슷한 (f 정도로 가파른) 함수
Ω(f) : 적어도 f만큼 빠르게 성장하는 (비효율적인) 함수

Small o

주어진 복잡도 함수 f(n)에 대해, o(f(n))은 n ≥ N을 만족하는 모든 n과 모든 양의 실수 c에 대해 다음 부등식을 만족하는 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합

\[g(n) ≤ c * f(n)\]

Big O vs. Small o
- Big O : 하나의 상수 c > 0에 대해서만 성립하면 됨
- Small o : 모든 실수 c > 0에 대해 성립해야 함
g(n)이 o(f(g))이고, g(n)이 어떤 알고리즘의 시간복잡도
- 그 알고리즘의 실행시간은 f(n)보다 궁극적으로 훨씬 좋음을 의미
ex) n² + 2n 은 O(n²)에는 속하지만, Small o(n²)에는 속하지 않음
ex) n ∈ o(n²)

차수의 특성

iff : if and only if (필요충분조건)

$g(n) ∈ O(f(n))$ iff f(n) ∈ $Ω(g(n))$
- g(n)이 f(n)보다 밑에 있음

$g(n) ∈ Θ(f(n))$ iff f(n) ∈ $Θ(g(n))$
- g(n), f(n) 차수 같음

b > 1 ∩ a > 1 ⇒ $(log_a^n)$ ∈ $Θ(log_b^n)$
- 모든 로그 복잡도 함수는 같은 복잡도 카테고리에 속함! (같은 차수)

b > a > 0 ⇒ $a^n$ ∈ o($b^n$)

∀a > 0 ⇒ $a^n$ ∈ o(n!)
- $a^n$이 훨씬 좋음
- small o → 지수보다 나쁜 것이 계승

다음과 같은 순서의 복잡도 카테고리가 있음
$Θ(lg^n) < Θ(n) < Θ(nlg^n) < Θ(n^2) < Θ(n^j) < Θ(n^k) < Θ(a^n) < Θ(b^n) < Θ(n!)$
- k > j > 2 이고, b > a > 1
- g(n)이 f(n)이 속한 카테고리보다 왼쪽에 속하면 다음이 성립함
  $g(n) ∈ o(f(n))$

c ≥ 0, d > 0, g(n) ∈ O(f(n)), h(n) ∈ Θ(f(n))
⇒ c * g(n) + d * h(n) ∈ Θ(f(n))
- g(n) : f(n)과 차수 같거나 낮음
- h(n) : f(n)과 차수 같음
- g(n)보다 h(n)의 차수 더 높을 것
- 모든 로그 함수는 다항식 함수보다, 모든 다항식 함수는 지수 함수보다, 모든 지수 함수는 계승 함수보다 궁극적으로 좋음

극한을 사용한 차수 결정 방법

차수가 같으면 상수값
f(n)(분모)이 굉장히 크면 0으로 수렴 → f(n) 차수가 더 높음
g(n)(분자)이 굉장히 크면 발산 → g(n) 차수가 더 높음

ex) $\frac{n^2}{2} ∈ o(n^3)$
$\lim_{n→∞} \frac{n^2 / 2}{n^3} = \lim_{n→∞} \frac{1}{2n} = 0$

ex) b > a > 0 ⇒ $a^n ∈ o(b^n)$
$\lim_{n→∞} \frac{a^n}{b^n} = \lim_{n→∞} (\frac{a}{b})^n = 0$

ex) b > 1 ∩ a > 1 ⇒ $log_a^n ∈ Θ(log_b^n)$ (로피탈의 정리)
$\lim_{n→∞} \frac{log_a^n}{log_b^n} = \lim_{n→∞} \frac{1/(n ln^a)}{1/(n ln^b)} = \lim_{n→∞} \frac{ln^b}{ln^a} > 0$ ⇒ 상수값