알고리즘 기초

알고리즘이란?

어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정

알고리즘은 모호하지 않고 이해하기 쉬우며, 효율적으로 설계가 되어야 한다

 

알고리즘의 성능을 계산할 때 시간이나 메모리 등의 자원을 분석하지만, 주로 수행 시간이 얼마나되는지를 통해 알고리즘의 성능을 확인한다

 

몇가지 간단한 수행 시간 계산 방법을 알아보자

sample1(A[], n)
{
	sum ← 0;
	for i ← 1 to n
        sum ← sum + A[i];
	return sum;
}

위는 배열 A[1 ···n]의 모든 원소를 더하는 알고리즘이다

for 루프를 제외한 3, 6 라인은 상수 시간이 소요되므로 해당 알고리즘의 수행 시간은 for 루프의 반복 횟수 n에 비례한다

sample2(A[], n)
{
	sum ← 0;
	for i ← 1 to n
        for j ← 1 to n
        {
            k ← A[1···n]에서 임의로 ⌊n/2⌋개를 뽑을 때 이들 중 최대값;
            sum ← sum + k;
        }
    return sum;
}

위의 알고리즘은 for 루프를 \(n^2\)번 반복하면서 매번 배열에서 반을 임의로 뽑아 그중 최대값을 계속 더하는 알고리즘이다

7 라인에서 ⌊\(\frac{n}{2}\)⌋개를 뽑아 최댓값을 구하는 과정에서  \(\frac{n}{2}\)의 시간이 소요되고 이는 n에 비례하는 시간이기 때문에 해당 알고리즘은 총 \(n^2 \) X n = \(n^3\)에 비례하는 시간이 소요된다

 

factorial(n)
{
    if (n = 1) return 1;
    return n * factorial(n - 1);
}

마지막으로 자기호출 알고리즘이다

위의 알고리즘의 경우 factorial()이 총 몇 번 호출되는지가 시간을 좌우하는데, 총 n번의 factorial()이 호출되기 때문에 해당 알고리즘은 n에 비례하는 시간이 소요된다

 

점근적 표기

알고리즘에서 관심을 갖는 것은 '입력의 크기가 클때 해당 알고리즘의 수행 시간이 어떻게 되는지' 이다

그래서 알고리즘의 수행 시간은 항상 입력 크기가 충분히 클 때 분석하고, 입력의 크기가 커짐에 따라 함수값이 증가하는 비율(점근적 증가율)을 계산하여 점근적 표기법으로 나타낸다

 

1. \(\Theta\)-표기법

다음의 명제들은 모두 같은 의미를 지닌다

입력 크기 n에 대해 \(\Theta(n^2)\)이라면 대략 \(n^2\)에 비례하는 시간이 소요된다

\(\Theta\)(f(n))은 점근적 증가율이 f(n)과 일치하는 모든 함수의 집합이다

\(\Theta\)(f(n))은 최고차항의 차수가 f(n)과 일치하는 함수의 집합이다

\(\Theta\)(g(n)) = \(O\)(g(n)) \(\cap\) \(\Omega\)(g(n))

\(\Theta\)(g(n)) = {f(n) | 충분히 큰 모든 n에 대하여 \(c_{1}\)g(n) \(\leq\) f(n) \(\leq\) \(c_{2}\)g(n)인 양의 상수 \(c_{1}\), \(c_{2}\)가 존재한다}

 

 

2. \(O\)-표기법

입력 크기 n에 대해 \(O(n^2)\)이라면 기껏해야 \(n^2\)에 비례하는 시간이 소요된다

\(O\)(f(n))은 점근적 증가율이 f(n)을 넘지 않는 모든 함수의 집합이다

\(O\)(f(n))은 최고차항의 차수가 f(n)과 일치하거나 더 작은 함수의 집합이다

\(O\)(g(n)) = {f(n) | 충분히 큰 모든 n에 대하여 f(n) \(\leq\) cg(n)인 양의 상수 c가 존재한다}

 

 

3. \(\Omega\)-표기법

입력 크기 n에 대해 \(\Omega(n^2)\)이라면 적어도 \(n^2\)에 비례하는 시간이 소요된다

\(\Omega\)(f(n))은 점근적 증가율이 적어도 f(n)이 되는 모든 함수의 집합이다

\(\Omega\)(f(n))은 최고차항의 차수가 f(n)과 일치하거나 더 큰 함수의 집합이다

\(\Omega\)(g(n)) = {f(n) | 충분히 큰 모든 n에 대하여 f(n) \(\geq\) cg(n)인 양의 상수 c가 존재한다}

 

4. \(o\)-표기법, \(\omega\)-표기법

각각 빅오 표기법과 빅오메가 표기법의 부등호에서 등호가 빠진 표현이다

 

점화식

점화식이란 어떤 함수를 자신과 똑같은 함수를 이용해 나타내는 것이다

주로 자기호출을 사용하는 함수 (재귀 함수)의 복잡도를 구하는 데 유용하다

 

대표적 재귀 함수인 합병 정렬을 예시로 들면

mergeSort(A[], p, r)
{
    if (p < r) then {
        q ← ⌊(p+r) / 2⌋;
        mergeSort(A, p, q);
        mergeSort(A, q + 1, r);
        merge(A, p, q, r);
    }
}

mergeSort 알고리즘은 주어진 문제를 이등분한 다음, 5, 6 라인에서 나누어진 두 문제를 각각 해결하고 7 라인에서 후처리한다

크기가 n인 배열의 정렬 문제에 크기 \(\frac{n}{2}\)인 배열의 정렬 문제 두개가 포함되어, 합병 정렬의 수행 시간이 T(n)이면 다음과 같이 표현될 수 있다

T(n) = 2T(\(\frac{n}{2}\)) + 후처리 시간

이와 같은 수식을 점화식이라고 하는데, 이러한 점화식의 점근적 분석 방법은 어떻게 구할 수 있을까?

방법은 세가지이다

 

1. 반복 대치

위의 팩토리얼 알고리즘을 다시 확인해보자

팩토리얼 알고리즘의 점화식은 T(n) = T(n-1) + c 이고, 이를 전개하면 다음과 같다

T(n) = T(n-1) + c
        = T(n-2) + c + c = T(n-2) + 2c
        ···
        = T(1) + (n-1)c \(\leq\) c + (n-1)c = cn

결과적으로 T(n) \(\leq\) cn 이므로 T(n) = \(O\)(n)이 된다

이렇게 점화식을 전개하여 반복해서 대치하여 점근적 복잡도를 구하는 방법을 반복 대치라고 한다

 

다시 합병 정렬을 보면, 다음과 같이 전개된다

T(n) \(\leq\) 2T(\(\frac{n}{2}\)) + n
        \(\leq\) 2(2T(\(\frac{n}{4}\))+\(\frac{n}{2}\)) + n = \(2^2\)T(\(\frac{n}{2^2}\)) + 2n
        ···
        \(\leq\) \(2^k\)(2T(\(\frac{n}{2^k}\)) + kn = nT(1) + kn = n + n\(\log n\) = \(O\)(n\(\log n\))

해당 식처럼 전개될 수 있는 이유는 n = \(2^k\)로 가정하기 때문이다

점근적 복잡도의 계산을 용이하게 하기 위해 보통 n = \(2^k\)이라고 가정하는데, 이렇게 가정해도 대부분의 다항식으로 표현되는 복잡도에서 오류 없이 적용된다

 

2. 추정 후 증명

추정 후 증명은 식의 모양을 보고 점근적 복잡도를 추정한 다음 그것이 옳음을 귀납적으로 증명하는 방법이다

 

T(n) = 2T(\(\frac{n}{2}\)) + 1 의 점근적 복잡도는 \(O\)(n)이다

증명 : T(n) = 2T(\(\frac{n}{2}\)) + 1
                  \(\leq\) 2(c\(\frac{n}{2}\)-2) + 1
                  = cn - 3
                  \(\leq\) cn -2

추정 후 증명은 의미 있는 추정이 필요하다

너무 여유롭게 추정해 증명하는 것은 별로 의미가 없고 너무 무리한 추정은 증명되지 않는다

 

3. 마스터 정리

마스터 정리는 특정 형태의 재귀식에서 바로 결과를 알 수 있는 방법이고, 적용되는 식의 형태는 다음과 같다

T(n) = aT(\(\frac{n}{b}\)) + f(n)

입력의 크기가 n인 문제를 해결하기 위해 입력의 크기가 \(\frac{n}{b}\)인 문제를 a개 풀고, 나머지 f(n)의 작업이 필요한 알고리즘

결과는 상수 a, b와 식 f(n)의 모양에 따라 달라지며, 정리하면 다음과 같다

① 어떤 양의 상수 \(\epsilon\)에 대하여 \(\frac{f(n)}{h(n)}\) = \(O\)(\(\frac{1}{n^\epsilon}\)))이면, T(n) = \(\Theta\)(h(n))이다
② 어떤 양의 상수 \(\epsilon\)에 대하여 \(\frac{f(n)}{h(n)}\) = \(\Omega\)(\(n^\epsilon\))이고, 어떤 상수 c(<1)와 충분히 큰 모든 n에 대해 af(\(\frac{n}{b}) \leq cf(n)\)이면 T(n) = \(\Theta\)(f(n))이다
③ \(\frac{f(n)}{h(n)}\) = \(\Theta\)(1)이면 T(n) = \(\Theta\)(h(n)\(\log n\))이다

이를 간단하게 아래와 같이 나타낼 수 있으며

① \(\displaystyle \lim_{n \to \infty}\frac{f(n)}{h(n)}\) = 0이면 T(n) = \(\Theta\)(h(n))이다
② \(\displaystyle \lim_{n \to \infty}\frac{f(n)}{h(n)}\) = \(\infty\)이고, 충분히 큰 모든 n에 대해 af(\(\frac{n}{b}) \leq cf(n)\)이면 T(n) = \(\Theta\)(f(n))이다
③ \(\frac{f(n)}{h(n)}\) = \(\Theta\)(1)이면 T(n) = \(\Theta\)(h(n)\(\log n\))이다

더 간단하게 아래처럼 나타낼 수 있다

① h(n)이 더 무거우면 h(n)이 수행 시간을 결정한다
② f(n)이 더 무거우면 f(n)이 수행 시간을 결정한다
③ h(n)과 f(n)이 같은 무게이면 h(n)에 \(\log n\)을 곱한 것이 수행 시간이 된다