[Ch.02 - 알고리즘 설계와 분석의 기초] 몇 가지 기초 사항들

1. 알고리즘 분석의 필요성

---

어떤 알고리즘을 설계하고 나면 이 알고리즘이 자원을 얼마나 소모하는지 분석해야 할 때가 많다. 여기서 자원이란 다양한 것이 되겠지만, 대부분 소요 시간이 가장 중요한 관심 대상이 된다.

시간 분석은 최악의 경우와 평균적인 경우에 대한 분석이 대표적이다. 시간 분석을 하면 알고리즘이 어느 정도 입력에서 어느 정도의 시간이 필요한지 미리 짐작할 수 있다.

알고리즘의 소요 시간은 설계하는 방법에 따라 소모 시간이 다양해진다. 예로 입력의 크기가 \(n\) 일 때, 최악의 경우 \(n^2\)에 비례하거나 \(n\log n\)에 비례하는 시간을 소모할 수 있다.

 

 

2. 알고리즘의 수행 시간

---

알고리즘의 수행 시간은 입력의 크기에 대해 시간이 어떤 비율로 소요되는지로 표현한다. 입력의 크기가 \(n\)인 경우의 알고리즘을 예로 들어보자.

sample1(A[], n)
{
	k = int(n/2);
    return A[k];
}

함수 sample1이 하는 일은 배열 A의 중간번째 요소를 반환하는 것이다. 입력의 크기에 상관없이 항상 일정한 시간 즉, 상수 시간이 소요된다.

 

sample2(A[], n)
{
    sum = 0;
    for i = 0 to n
    	sum = sum + A[i]
    return sum;
}

함수 sample2는 배열 A의 모든 원소를 더하여 반환한다. for 반복문은 배열의 크기 만큼 반복하고 for 반복문 안의 코드는 상수 시간이 소요되므로 for 반복문의 수행 시간은 \(n\)에 비례한다. 이 외의 코드는 상수 시간이 소요되기 때문에 해당 함수의 수행 시간 또한 \(n\)에 비례한다.

 

sample3(A[], n)
{
    sum = 0;
    for i = 1 to n
    	for j = 1 to n
            sum = sum + A[i] * A[j];
    return sum;
}

함수 sample3의 중첩된 for 반복문을 살펴보면 총 \(n\) * \(n\)번 반복되고 반복문 속 코드는 상수 시간이 소요된다. for 반복문 외의 코드 또한 모두 상수 시간이 소요되기 때문에 함수 sample3의 소요 시간은 \(n^2\)에 비례한다.

 

sample4(A[], n)
{
    sum = 0;
    for i = 1 to n
    	for j = 1 to n
            k = A[1...n]에서 임의로 int(n/2)개 뽑을 때 이들 중 최댓값;
            sum = sum + k;
    return sum;
}

함수 sample4는 위의 함수 sample3와 유사하게  \(n\) * \(n\)번 반복되는 for 반복문에 중첩되어 있다. 하지만 for 반복문 안에 코드의 소요 시간은 상수 시간이 아니다. 임의로  \(n\)의 절반 만큼의 배열의 요소를 고르고 이들 중 최댓값을 찾아야 하기 때문에 이의 소요 시간은  \(n/2\)에 비례하고 이것은  \(n\)에 비례한다. 즉, 함수 sample4의 소요 시간은  \(n^3\)에 비례한다.

 

sample5(A[], n)
{
    sum = 0;
    for i = 1 to n-1
        for j = i+1 to n
            sum = sum + A[i] * A[j];
    return sum;
}

함수 sample5는 반복문이 중첩되어 있지만 반복 횟수가 매번 변하는 예이다. 우선 for 반복문 안의 코드는 상수 시간이 소요된다. 총 반복되는 횟수를 자세히 살펴보면 다음과 같다.

i	내부 반복문의 반복 횟수
1	\(n-1\)
2	\(n-2\)
3	\(n-3\)
n-2	\(2\)
n-1	\(1\)

이전과 같이 총 반복 횟수는 \(n(n-1)/2\)회로 소요 시간은 \(n^2\)에 비례한다.

 

 

3. 재귀(자기호출)와 귀납적 사고

---

자기호출이 일어나는 경우에는 지금까지 들었던 예와는 분석 방법이 다르다.

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

위 함수는 자기호출 알고리즘이다. 이 알고리즘의 소요 시간은 factorial()이 얼마나 호출되는지에 영향을 받는다.

factorial(n)이 factorial(n-1)을 호출하고, factorial(n-1)이 factorial(n-2)를 호출하고, ... , factorial(2)가 factorial(1)을 호출하며  factorial(n) 알고리즘이 끝난다. 즉, 이 알고리즘의 총 소요 시간은 \(n\)에 비례한다. 이 예는 자기호출 알고리즘의 소요 시간 분석 중 매우 간단한 예이다.

 

자기호출은 컴퓨터 과학 이론의 근간을 이루는 중요한 개념이다. 자기호출은 어떤 문제를 해결하는 과정에서 자신과 똑같지만 크기가 다른 문제를 발견하고 이들의 관계를 파악함으로써 문제 해결에 간명하게 접근하는 방법이다. 자기호출은 수학적 귀납법과 관련이 깊다. 귀납적 사고라는 것은 성격이 같지만 크기가 다른 문제 간의 "관계"를 파악하는 것이다. 수학적 귀납법이란 자신보다 작은 문제에 대해 결론이 옳음을 가정하고 자신과 이 작은 문제의 관계를 통해서 자신에게도 결론이 옳음을 보이는 것이다. 재귀 알고리즘이 자신보다 작은 문제를 자기호출 한다는 것은 수학적 귀납법에서 자신보다 작은 문제에 대해 결론이 옳음을 가정하는 것과 일치한다. 즉, 자신보다 작은 문제에서는 이 알고리즘이 제대로 작동한다고 가정하는 것이다. 자기호출을 이용하는 알고리즘에서 자기호출을 제외한 나머지 부분은 대부분 크기가 다른 문제 간의 관계를 반영하는 것이다.

mergeSort(A[], p, r)
{
    if(p < r) then
        q = int((p+r)/2); 1️⃣
        mergeSort(A, p, q); 2️⃣
        mergeSort(A, q+1, r); 3️⃣
        merge(A, p, q, r); 4️⃣
}

위 함수는 대표적인 재귀 알고리즘인 병합 정렬이다. 1️⃣과 4️⃣의 코드는 자신과 자신보다 작은 문제의 관계를 반영한 것이고 2️⃣과 3️⃣는 자기호출로 작은 문제를 해결하는 것이다.