시간복잡도(Time Complexity)

알고리즘 분석

RAM 모델

시간복잡도

[eqn: O, \ Omega, \ Theta] 표기

최대 부분 수열의 합

알고리즘 I

알고리즘 I을 다시 생각하며

순환호출을 이용한 알고리즘

또 다른 알고리즘

NP-complete 문제

알고리즘의 분석

어떤 문제에 대한 알고리즘을 설계하고 나면,

· 가능한 입력에 대해서 항상 옳게 동작하는지를 보이고,

· 얼마나 많은 자원을 사용하는지를 분석한다.

가장 중요한 자원은 알고리즘의 실행 시간이며 그 외에 알고리즘을 실행하는데 필요한 메모리의 양 등이 있다.

실행시간을 측정하기 위해서 프로그램을 작성하여야 하나?

컴퓨터에 따라 실행시간에 차이가 있을 텐데?

프로그래밍 언어에 따른 차이는 어떡하지?

RAM 모델

RAM 모델은 명령어가 순차적으로 수행되는 보통의 컴퓨터에 기반을 두고 있다.

· 덧셈, 곱셈 등 사칙연산, 비교, 치환과 같은 간단한 명령어를 가지고 있다. 실제 컴퓨터와 다른 점은 이러한 연산을 모두 단위 시간에 수행할 수 있다고 가정한다. 그러나 정렬이나 행렬 곱셈 등과 같은 연산은 단위 시간에 수행할 수 없다.

· 실제 컴퓨터와 마찬가지로 정수를 고정된 길이(예컨대 32비트)로 표현한다.

· 무한한 양의 메모리를 가진다. 단위 시간에 메모리에 접근할 수 있다고 가정한다.

알고리즘의 실행 시간은 RAM 모델 상에서 실행할 때 필요한 단위 시간의 개수로 나타낸다.

시간복잡도

입력의 개수가 [eqn: n]개일 때 알고리즘의 실행 시간을 [eqn: n]에 대한 함수로 표현한다. 그러나 입력의 크기가 [eqn: n]으로 같더라도 알고리즘의 실행 시간이 다를 수 있다.

최악의 경우 시간복잡도는 입력의 개수가 [eqn: n]인 모든 가능한 입력에 대한 최대 실행 시간을 말한다. 최악의 경우 시간복잡도를 간단히 시간복잡도라고 부른다.

평균 시간복잡도는 크기 [eqn: n]인 모든 입력에 대한 실행 시간의 평균을 말한다.

시간복잡도를 정확히 계산하는 것은 복잡하고 귀찮은 작업이다. 시간복잡도의 상한과 하한을 말하는 것이 쉽고도 간결하다.

[eqn: O, \ Omega, \ Theta] 표기

· 상수 [eqn: c]와 [eqn: n_0]가 존재하여 [eqn: n geq n_0]인 모든 [eqn: n]에 대하여 [eqn: T(n) leq c cdot f(n)]을 만족하면 [eqn: T(n) = O(f(n))]이라고 한다.

· 상수 [eqn: c]와 [eqn: n_0]가 존재하여 [eqn: n geq n_0]인 모든 [eqn: n]에 대하여 [eqn: T(n) geq c cdot g(n)]을 만족하면 [eqn: T(n) = Omega(g(n))]이라고 한다.

· [eqn: T(n) = O(h(n))]이고 [eqn: T(n) = Omega(h(n))]이면 [eqn: T(n)][eqn: =][eqn: Theta(h(n))]이라고 한다.

[eqn: O, \ Omega, \ Theta] 표기 연습

[eqn: n]이 작을 때에는 [eqn: 1000n]이 [eqn: n^2]보다 크지만, [eqn: n]이 커짐에 따라 [eqn: n^2]이 빠른 속도로 증가하므로 큰 [eqn: n]에 대해서는 [eqn: n^2]이 [eqn: 1000n]보다 더 큰 함수가 된다. 이 경우에 분기점이 되는 것은 [eqn: n]이 [eqn: 1000n]일 때이다.

[eqn: T(n) = O(f(n))]이라는 것은 정의에 의하면 [eqn: n]이 어떤 지점 [eqn: n_0]보다 커지면 [eqn: T(n)]은 항상 [eqn: f(n)]의 상수 배보다 같거나 작다는 것이다. [eqn: T(n) = 1000n], [eqn: f(n) = n^2]인 경우에 [eqn: n_0 = 1000], [eqn: c = 1]이라 두면 [eqn: n geq 1000]인 모든 [eqn: n]에 대해서 [eqn: 1000n leq 1 cdot n^2]이므로 [eqn: 1000n = O( n^2 )]이 된다.

[eqn: O] 표기에 상수나 낮은 차수의 항을 포함하는 것은 좋지 않다. [eqn: T(n) = O(2n^2 )]이나 [eqn: T(n) = O(n^2 + n)]이라고 하지말고, [eqn: T(n)][eqn: =][eqn: O(n^2 )]이라고 말하면 된다.

[eqn: O, \ Omega, \ Theta] 표기 연습 (계속)

· [eqn: 3n^2 - 100n + 6 = O(n^2 )]

[eqn: 3n^2 - 100n + 6 = O(n^3 )]

[eqn: 3n^2 - 100n + 6 neq O(n)]

· [eqn: 3n^2 - 100n + 6 = Omega (n^2 )]

[eqn: 3n^2 - 100n + 6 neq Omega (n^3 )]

[eqn: 3n^2 - 100n + 6 = Omega (n)]

· [eqn: 3n^2 - 100n + 6 = Theta (n^2 )]

[eqn: 3n^2 - 100n + 6 neq Theta (n^3 )]

[eqn: 3n^2 - 100n + 6 neq Theta (n)]

[eqn: O(n^2 ), \ Omega (n^2 ), \ Theta (n^2 )] 등을 함수의 집합으로 생각하는 것이 좋다.

시간복잡도의 분류

· 다항 시간

- [eqn: O(1)]

- [eqn: O(log n)]

- [eqn: O(sqrt n \\ )]

- [eqn: O(n)]

- [eqn: O(n log n)]

- [eqn: O(n^2 )]

- [eqn: O(n^3 )]

[eqn: vdots]

· 지수 시간

- [eqn: O(2^n )]

- [eqn: O(n2^n )]

- [eqn: O(n!)]

최대 부분 수열의 합

길이 [eqn: n]인 정수의 수열 [eqn: a_0 , \ a_1 , \ a_2 , \ cdots , \ a_n-1]이 입력으로 주어진다. 부분 수열 [eqn: [i,j]]라는 것은 [eqn: a_i , \ a_{i+1} , \ cdots , \ a_j]를 말한다. 부분 수열의 합 즉 [eqn: sum_{i leq k leq j} a_k]의 최대값을 구하는 문제이다.

주어진 수열의 정수가 모두 음수이면 최대 부분 수열의 합은 [eqn: 0]이라고 생각한다. 예를 들어 다음과 같은 수열이 주어졌을 때,

[eqn: +31, -41, +59, +26, -53, +58, +97, -93, -23, +84]

최대 부분 수열은 [eqn: [3,7]]이며 수열의 합은 [eqn: 187]이 된다.

문제는 최대 부분 수열의 합을 구하는 것이지만, 앞으로 소개될 알고리즘을 조금만 수정하면 최대 부분 수열도 쉽게 구할 수 있다.

알고리즘 I

모든 가능한 부분 수열에 대해서 그 부분 수열의 크기를 계산하여 최대값을 찾는다. 부분 수열은 [eqn: [i, j]]로 나타내며 이때 [eqn: 0 leq i leq j leq n-1]이 되도록 한다. 고려하고 있는 부분 수열의 크기는 ThisSum에, 현재까지 고려한 부분 수열 중에서 최대값은 MaxSum에 저장하여 보관한다. 여기서 max()는 두 수의 최대값을 돌려주는 함수나 마크로라고 가정한다.

long MaxSubseqSum(int A[], unsigned n)

{

long MaxSum, ThisSum;

unsigned i, j, k;

MaxSum = 0;

for (i=0; i<n; i++) {

for (j=i; j<n; j++) {

ThisSum = 0;

for (k=i; k<=j; k++)

ThisSum = ThisSum + A[k];

MaxSum = max(MaxSum,ThisSum);

}

}

return MaxSum;

}

알고리즘 I의 분석

알고리즘 I은 크게 보면 [eqn: 3]개의 for 문으로 구성되어 있다.

· 가장 바깥쪽의 for 문은 [eqn: n]번 반복을 실행한다.

· 중간에 있는 for문은 [eqn: n-i]회 반복을 실행하는데 [eqn: 0 leq i leq n-1]이므로 [eqn: n]회 이하 반복한다.

· 가장 안쪽은 for 문은 [eqn: j-i+1]회 반복이 실행되나 [eqn: 0 leq i leq j leq n-1]이 성립하므로 최대 [eqn: n]회 반복한다.

for 문 내에 있는 문장을 포함하여 알고리즘의 시간복잡도를 분석하여 보자.

· 가장 안쪽 for 문은 덧셈, 치환을 반복하므로 [eqn: O(n)]이다.

· 가운데 for 문은 [eqn: O(n)] 시간의 for 문과 함께 [eqn: O(1)] 시간을 쓰는 비교 및 치환을 [eqn: n]회 반복하므로 [eqn: O(n^2 )]이다.

· 바깥 for 문은 [eqn: O(n^2 )] 시간의 for 문을 [eqn: n]회 반복하므로 [eqn: O(n^3 )]이 된다.

따라서 [eqn: O(1)] 시간의 첫 문장과 마지막 문장을 포함하더라도

알고리즘 I의 시간복잡도는 [eqn: O(n^3 )]이 된다.

알고리즘 I의 분석(계속)

앞의 분석에서 for 문의 반복 횟수를 엄밀히 계산하지 않고 상한값을 이용하여 시간복잡도 [eqn: O(n^3 )]을 얻었다. 실제 시간복잡도는 이 보다 작을 수 있다고 생각할 수 있다.

그러나 for 문의 가장 안쪽에서 반복 실행되는 다음 문장의 실행 횟수를 계산하여 보자.

ThisSum = ThisSum + A[k];

그러면 아래와 같이 [eqn: n^3]항을 가지고 있으므로, 상한값으로 계산한 것이 상수 배만큼만 시간복잡도에 영향을 미친 것임을 알 수 있다.

[eqn: sum_{0 leq i leq n-1} sum_{i leq j leq n-1} sum_{i leq k leq j} 1]

[eqn: = sum_{0 leq i leq n-1} sum_{i leq j leq n-1} (j - i + 1)]

[eqn: = sum_{0 leq i leq n-1} {(n - i) (n-i+1)} over {2}]

[eqn: = 1 over 2 LEFT { sum_{0 leq i leq n-1} {(n - i)^2} + sum_{0 leq i leq n-1} {(n - i)} RIGHT }]

[eqn: = 1 over 2 LEFT { {n(n+1)(2n+1)} over 6 + {n(n+1)} over 2 RIGHT }]

[eqn: = 1 over 2 LEFT { {n(n+1)} over 2 cdot left ( {2n+1} over 3 + 1 right ) RIGHT }]

[eqn: = 1 over 2 LEFT { {n(n+1)} over 2 cdot left ( {2n+4} over 3 right ) RIGHT }]

[eqn: = {n^3 +3n^2 +2n} over {6}]

알고리즘 I을 다시 생각하며

알고리즘 I을 잘 관찰하여 보면 중복된 계산을 하는 부분이 있다는 것을 알 수 있다. 일반적으로 알고리즘을 설계하였을 때 계산이 중복되는 부분이 있는지를 살펴보고 이 부분을 제거하여 알고리즘을 보다 효율적인 것으로 만드는 것은 중요한 일이다.

부분 수열 [eqn: [i,j]]의 합을 계산할 때 순서대로 [eqn: a_i ,] [eqn: a_{i+1},] [eqn: cdots ,] [eqn: a_j]를 더한다. 부분 수열 [eqn: [i,j-1]]의 합을 구할 때도 같은 방식으로 [eqn: a_i , \ a_{i+1} , \ cdots , \ a_{j-1}]을 더하게 되므로 이 부분이 부분 수열 [eqn: [i,j]]의 합을 계산할 때와 중복된다.

부분 수열 [eqn: [i,j]]의 합은 부분 수열 [eqn: [i,j-1]]의 합을 알고 있다면 다음과 같이 쉽게 계산할 수 있다.

[eqn: sum_{i leq k leq j} a_k = sum_{i leq k leq j-1} a_k + a_j]

이제 부분 수열의 합을 계산할 때 위의 관찰을 이용하면 가장 안쪽의 for 문을 없앨 수 있을까? 그러면 시간복잡도는 얼마나 될까?

알고리즘 II

long MaxSubseqSum(int A[], unsigned n)

{

long MaxSum, ThisSum;

unsigned i, j;

MaxSum = 0;

for (i=0; i<n; i++) {

ThisSum = 0;

for (j=i; j<n; j++) {

ThisSum = ThisSum + A[j]

MaxSum = max(MaxSum,ThisSum);

}

}

return MaxSum;

}

알고리즘 II의 시간복잡도는 [eqn: O(n^2 )]이다. 이것을 어떻게 설명할 수 있을까?

순환호출을 이용한 알고리즘

순환호출을 이용하여 이 문제에 대한 알고리즘을 설계할 수 있을까? 우선 수열 [eqn: a_0 , \ a_1 , \ a_2 , \ cdots , \ a_n-1]을 두 부분으로 나누어 보자.

[eqn: a_0 , \ a_1 , \ cdots , \ a_k \ | \ a_{k+1}, \ a_{k+2}, \ cdots , \ a_n-1]

원래 수열에 대한 최대 부분 수열은

· 수열의 앞부분에 속하거나,

· 수열의 뒷부분에 속하거나, 혹은

· [eqn: a_k]와 [eqn: a_{k+1}]을 포함하여 앞뒤에 걸쳐있을 것이다.

위의 3가지 경우 각각에 대해서 최대 부분 수열을 구하여 최대값을 취하면 원래 수열에 대한 최대 부분 수열의 합이 된다. 앞부분에 속한 최대 부분 수열은 결국 수열 [eqn: a_0 , \ a_1 , \ cdots , \ a_k]에 대한 최대 부분 수열이므로 순환호출을 이용하여 구한다. 수열의 뒷부분에 속한 최대 부분 수열도 마찬가지로 순환호출을 이용한다.

그러면 앞뒤에 걸쳐있는 최대 부분 수열은 어떻게 구할 수 있을까?

앞뒤에 걸쳐있는 최대 부분 수열

앞뒤에 걸쳐있을 경우에 최대 부분 수열은 [eqn: a_k]와 [eqn: a_{k+1}]을 포함한다.

[eqn: a_0 , \ a_1 , \ cdots , \ a_{k-1}, \ a_k \ | \ a_k+1 , \ a_k+2 , \ cdots , \ a_n-2 , \ a_n-1]

수열의 앞부분에서 [eqn: a_k]를 포함하는 최대 부분 수열을 구하고, 수열의 뒷부분에서 [eqn: a_k+1]을 포함하는 최대 부분 수열을 구한 다음 구해진 두 부분 수열을 붙이면  수열의 앞뒤에 걸쳐있는 최대 부분 수열이 된다.

수열의 앞부분에서 [eqn: a_k]를 포함하는 최대 부분 수열은 어떻게 구할 수 있는지 생각해 보자. 모든 가능한 부분 수열을 생각해 보면 아래와 같이 [eqn: k]개가 있다.

[eqn: [0,k], \ [1,k], \ cdots , \ [i,k], \ [i+1,k], \ cdots , \ [k,k]]

부분 수열 [eqn: [i, k]]의 합은 부분 수열 [eqn: [i+1,k]]의 합이 주어져 있으면 쉽게 구할 수 있다.

[eqn: sum_{i leq j leq k} a_j = sum_{i+1 leq j leq k} a_j \ + \ a_i]

같은 방식으로 수열의 뒷부분에서 [eqn: a_k+1]을 포함하는 최대 부분 수열의 합을 구할 수 있다.

순환 알고리즘 완성하기

[eqn: k]를 얼마로 정할 것인가? 수열을 앞부분과 뒷부분으로 나눌 때 앞부분과 뒷부분에 속한 원소의 수가 비슷하도록 나누기로 한다. 사실 [eqn: 0 < alpha < 1]을 만족하는 [eqn: alpha]에 대해서 [eqn: alpha n]과 [eqn: (1- alpha)n]으로 나누어도 시간복잡도가 달라지지는 않지만 일반적으로 반씩 나누는 것이 좋다.

MaxSubseqSum(A,0,n-1)을 호출함으로써, A[n]의 최대 부분 수열의 크기를 구할 수 있다. 수열에 속한 원소가 [eqn: 1]개이면 그것이 양수인지 음수인지를 판단하여 양수이면 그 값을, 음수이면 [eqn: 0]을 반환한다. 그리고 원소가 [eqn: 2]개 이상이면 순환 호출을 부른다.

알고리즘 III

long MaxSubseqSum(int A[], unsigned Left, unsigned Right)

{

int Center, i;

long MaxSum, MaxLeft, MaxRight, MaxCenter;

long MaxCenterL, MaxCenterR, ThisSum;

if (Left == Right) {

if (A[Left] > 0) return A[Left];

else return 0;

}

Center = (Left + Right) / 2;

MaxLeft = MaxSubseqSum(A,Left,Center);

MaxRight = MaxSubseqSum(A,Center+1,Right);

MaxCenterL = 0;

ThisSum = 0;

for (i=Center; i>=Left; i--) {

ThisSum = ThisSum + A[i];

MaxCenterL = max(MaxCenterL,ThisSum);

}

MaxCenterR = 0;

ThisSum = 0;

for (i=Center+1; i<=Right; i++) {

ThisSum = ThisSum + A[i];

MaxCenterR = max(MaxCenterR,ThisSum);

}

MaxCenter = MaxCenterL + MaxCenterR;

MaxSum = max(max(MaxLeft,MaxRight),MaxCenter);

return MaxSum;

}

알고리즘 III의 분석

길이가 [eqn: n]인 수열에서 최대 부분 수열의 합을 구하는데 드는 시간을 [eqn: T(n)]이라고 하자. [eqn: n]이 [eqn: 1]일 때는 알고리즘의 맨 앞에 있는 if 문을 수행하고 끝나므로 상수 시간이 소요된다. [eqn: n]이 [eqn: 2] 이상인 경우에는 수열을 반으로 나누어 각각 길이가 [eqn: n/2]인 수열에 대해서 순환 호출을 한다. 그리고 [eqn: 2]개의 for 문을 수행하는데 각각 [eqn: O(n)] 시간이면 충분하므로, 순환 호출에 드는 시간을 제외한 나머지 시간은 모두 [eqn: O(n)]이다.

[eqn: T(1) \ = \ O(1)]

[eqn: T(n) \ = \ 2 T(n/2) + O(n), \ n ge 2]

계산을 간단히 하기 위해서 [eqn: O(1)] 대신에 [eqn: 1]을, [eqn: O(n)] 대신에 [eqn: n]을 쓰기로 한다. [eqn: T(n)]을 [eqn: O]-표기법으로 표현할 것이므로 단순화하더라도 결과에 영향을 미치지 않는다.

[eqn: T(1) \ = \ 1]

[eqn: T(n) \ = \ 2 T(n/2) + n, \ n ge 2]

알고리즘 III의 분석 (계속)

[eqn: 2^{k-1} < n le 2^k]이라 두고 앞의 점화식을 풀어 보기로 한다.

[eqn: T(n) \ leq \ T(2^k )]

[eqn: = \ 2 T(2^{k-1}) + 2^{k}]

[eqn: = \ 2 cdot \{ 2 T(2^{k-2}) + 2^{k-1} \} + 2^{k}]

[eqn: = \ 2^2 T(2^{k-2}) + 2^k + 2^k]

[eqn: vdots]

[eqn: = \ 2^k T(2^0 ) + {2^k + 2^k + cdots + 2^k}]

[eqn: = \ 2^k + k 2^k]         [eqn: Leftarrow \ \ k - 1 < log n, \ 2^{k-1} < n]이므로

[eqn: < \ 2n + 2n (log n + 1)]

[eqn: = \ O(n log n)]

따라서 알고리즘 III의 시간복잡도는 [eqn: O(n log n)]이다. 이와 같은 방식으로 알고리즘을 설계하는 것을 분할정복기법(divide-and-conquer)이라고 부른다.

또 다른 알고리즘

최대 부분 수열의 합 문제에 대해서 또 다른 알고리즘을 살펴보고자 한다. 이 알고리즘이 옳은지를 알아보는 것은 그리 쉽지 않다.

부분 수열의 오른쪽 끝이 [eqn: a_k]인 최대 부분 수열의 합을 [eqn: s_k]라고 하자. 즉 [eqn: s_k]는 다음과 같은 부분 수열에서 최대 부분 수열의 합이다.

[eqn: [0,k], \[1,k], \ cdots , \ [k,k]], 혹은 길이 [eqn: 0]인 수열

만약에 모든 [eqn: k \ (0 leq k leq n-1)]에 대해서 [eqn: s_k]를 알고 있다면 최대 부분 수열의 합은 이들 중에서 최대값이 될 것이다. 왜냐하면 최대 부분 수열의 오른쪽 끝은 반드시 [eqn: 0]부터 [eqn: n-1] 사이의 값 중에 하나일 것이기 때문이다.

그러면 [eqn: s_k]를 어떻게 구할 수 있을까? 만약에 [eqn: s_k-1]을 알고 있다면 쉽게 구할 수 있을까? 혹은 [eqn: s_0 , \ s_1 , \ cdots , \ s_k-1]을 모두 알고 있다면 [eqn: s_k]를 구할 수 있을까?

또 다른 알고리즘 (계속)

실제로 [eqn: s_k]는 [eqn: s_k-1]을 알고 있으면 다음과 같이 쉽게 구할 수 있다.

[eqn: s_k = max \{ s_k-1 + a_k, \ 0 \}]

위의 식이 왜 성립하는지를 살펴보자. 오른쪽 끝이 [eqn: a_k]인 최대 부분 수열은 길이가 [eqn: 0]이거나 [eqn: 1] 이상이다.

· 길이가 [eqn: 0]이면  [eqn: s_k]는 [eqn: 0]이다.

· 길이가 [eqn: 1] 이상이면 그 부분 수열의 맨 끝에 있는 원소 [eqn: a_k]를 제거하면 오른쪽 끝이 [eqn: a_k-1]인 최대 부분 수열이다. 만약 그렇지 않다면 합이 더 큰 부분 수열의 오른쪽에[eqn: a_k]를 붙이면 합이 [eqn: s_k]보다 더 큰 부분 수열을 얻을 수 있다.

따라서 위와 같이 [eqn: s_k]를 구할 수 있다.

알고리즘 IV

long MaxSubseqSum(int A[], unsigned n)

{

long MaxSum, ThisSum;

unsigned k;

MaxSum = 0;

ThisSum = 0;

for (k=0; k<n; k++) {

ThisSum = max(ThisSum + A[k], 0);

MaxSum = max(MaxSum,ThisSum);

}

return MaxSum;

}

알고리즘 IV의 시간복잡도가 [eqn: O(n)]이라는 것은 쉽게 알 수 있다. 알고리즘 IV와 같은 방식의 알고리즘 설계 기법을 동적계획법(dynamic programming)이라고 한다. 동적계획법에 대해서는 나중에 자세히 배울 기회가 있다.

NP-complete 문제

다항식 [eqn: P(n)]에 대해서 시간복잡도가 [eqn: O(P(n))]인 알고리즘을 효율적이라고 말한다.

시간복잡도가 [eqn: O(2^n )], [eqn: O(n2^n )], [eqn: O(n!)] 등과 같이 다항 시간보다 큰 알고리즘은 입력의 크기가 클 때 전혀 실용적이지 못하다.

다항 시간 알고리즘이 알려지지 않은 문제들도 많이 있다.

NP-complete에 속하는 문제는 다항 시간 알고리즘이 알려져 있지 않을뿐더러 다항 시간 알고리즘이 존재하지 않을 것이라고 믿고 있다.

NP-complete 문제들

· subset sum

· hamiltonian cycle

· traveling salesman

· bin packing

· knapsack

· graph coloring

· maximum clique