2. 시작하기(2)

2.2 알고리즘의 분석

알고리즘의 분석은 그 알고리즘을 실행하는 데 필요한 자원을 예측하는 것을 의미한다. 메모리, 통신 대역, 하드웨어 등

대부분은 계산 시간을 의미한다.

이 책에서의 가정

알고리즘은 단일 프로세서와 랜덤 접근 기계(RAM, random-access machine) 모델로 가정 : 명령어는 동시X, 하나씩 실행
산술 연산, 데이터 이동연산, 제어 연산 등 : 상수 시간
RAM 모델의 데이터형 : 정수(integer)와 부동소수(floating point)
각 워드 크기에 제한을 가정 : 입력 크기가 n인 입력을 다룰 때 정수는 상수 c>= 1에 대해 clg2비트로 표현된다고 가정(워드는 상수로 처리하므로 너무 크면 안된다.)

삽입 정렬의 분석

입력 크기

주어진 문제에 따라 다름.
입력이 많은 문제에선 입력 항목의 개수(ex. 정렬, 이산 푸리에 변환 계산)
두 정수를 곱하는 문제에선 총 비트수
입력이 그래프일땐 노드와 간선의 개수로 2개일 수 있음

수행시간

기본 연산 개수 또는 실행된 “단계”의 횟수를 말한다.

INSERTION-SORT(A) cost times

for j = 2 to A.length					//c1		n
    key = A[j]							//c2		n-1
// A[j]를 정렬된 배열 A[1..j-1]에 삽입한다. //0		 n-1
    i = j-1								//c4		n-1
    while i > 0 and A[i] > key  		//c5		(t2+t3+..+tn)
        A[i+1] = A[i]					//c6		(t2-1)+...+(tn-1)
        i = i-1							//c7		(t2-1)+...+(tn-1)
    A[i+1] = key						//c8		n-1

알고리즘의 수행시간 : 각 명령문 수행시간의 합

n개의 원소에 대한 INSERTION-SORT의 수행시간 T(n)을 구하기 위해 비용과 횟수의 곱을 합하면 다음과 같다.

\[T(n) = c_1n + c_2(n-1) + c_4(n-1) + c_5\displaystyle\sum_{j=2}^{n}t_j + c_6\displaystyle\sum_{j=2}^{n}(t_j-1) + c_7\displaystyle\sum_{j=2}^n(t_j-1)+c_8(n-1)\]

크기가 정해져도 어떤 입력인가에 따라 수행시간은 변한다.

예시1

Insertion-Sort(A)

for j = 2 to A.length
    key = A[j]
    // A[j]를 정렬된 배열A[1..j-1]에 삽입한다.
    i = j-1
    while i > 0 and A[i] > key
        A[i+1] = A[i]
        i = i-1
    A[i+1] = key

최선의 경우는 이미 정렬된 경우이다. 따라서 j=2, 3, …, n의 각 경우에 대해 i가 j-1로 초기화될 때 5행에서 A[i] <= key(이미 오름차순 정렬되있으므로 이전 인덱스이자 A[i]인 A[j-1]는 key인 A[j]보다 작거나 같다.)

따라서 j = 2, 3, …, n에 대해

\[t_j=1\]

이므로 수행시간은 다음이 된다.

\[T(n) = c_1n + c_2(n-1) + c_4(n-1) + c_5(n-1) +c_8(n-1) = (c_1+c_2+c_4+c_5+c_8)n-(c_2+c_4+c_5+c_8)\]

이 수행시간을 명령분의 비용인 c에 의존하는 상수 a,b에 대한 an+b로 표현할 수 있다.

n에 관한 선형 함수가 된다.

예시2

Insertion-Sort(A)

for j = 2 to A.length
    key = A[j]
    // A[j]를 정렬된 배열A[1..j-1]에 삽입한다.
    i = j-1
    while i > 0 and A[i] > key
        A[i+1] = A[i]
        i = i-1
    A[i+1] = key

최악의 경우는 역순으로 정렬된 경우이다. 따라서 j = 2, 3, …, n에 대해

\[t_j = j\]

이 된다. 다음 두 등식이 성립함을 이용하면

\[\displaystyle\sum_{j=2}^{n}j = \frac{n(n+1)}{2} - 1\] \[\displaystyle\sum_{j=2}^{n}(j-1)=\frac{n(n-1)}{2}\]

최악의 경우 INSERTION-SORT의 수행시간은 다음이 된다.

\[T(n) = c_1n + c_2(n-1) + c_4(n-1) + c_5(\frac{n(n+1)}{n}-1) + c_6(\frac{n(n-1)}{2}) + c_7(\frac{n(n-1)}{2})+c_8(n-1)\]

정리하면

\[T(n) = (\frac{c_5}2+\frac{c_6}2+\frac{c_7}2)n^2 + (c_1 + c_2 + c_4 + \frac{c_5}2-\frac{c_6}2-\frac{c_7}2+c_8)n-(c_2+c_4+c_5+c_8)\]

결국 ““최악의 경우” 수행시간은 n에 관한 이차식이다.

최악의 경우와 평균적인 경우의 분석

최악의 경우 수행시간 (크기가 n인 입력 중 가장 오래 걸리는 수행시간)에 관심을 가져야 하는 이유

알고리즘에서 최악의 경우 수행시간이 모든 입력의 수행시간에 대한 상한이 됨. 이 보다 더 오래 걸리지 않음을 확신할 수 있음.
어떤 알고리즘은 최악의 경우가 상당히 빈번히 발생할 수 있음.
“평균적인 경우”가 최악의 경우만큼 거의 조힞 못한 상황일때가 종종 있음.

평균 수행시간이 중요한 경우도 있다. 확률적 분석 기법은 수행시간의 평균값을 구할 수 있다.

랜덤화된 알고리즘은 무엇이 “평균적인” 입력인지 불확실한 경우, 입력의 크기가 정해지면 가능한 모든 입력이 비슷한 정도로 나타난다고 가정하여 구한다.

증가 차수

증가 비율 or 증가 차수 : 단순하게 추상화 차수가 가장 높은항만, 계수도 무시한채 비교한다.

입력이 작은 경우에는 문제가 될 수 있다.

삽입정렬