Maximum Contiguous Subsequence Sum(MCSS) 알고리즘 분석

Maximum Contiguous Subsequence Sum(MCSS) 알고리즘 분석

Maximum Contiguous Subsequence Sum(MCSS)

- n개의 정수 $a_1, a_2, \ldots, a_n$ 이 주어졌을 때, 연속적인 부분 수열의 합 $\sum_{k=i}^{j} a_k$ 이 최대가 되는 구간 (i, j)와 그 구간의 합을 계산하는 문제.

5

-7

2

3

-4

5

2

-7

8

-7

$\sum_{k=3}^{9} a_k = 9$

MCSS 알고리즘 (Time complexity : O($n^3$))

unsigned long int mcssN3(int a[], int n, int *start, int *end){
    int i, j, k;
    unsigned long int maxSum = 0;
 
    // start, end : 합이 최대가 되는 구간의 시작과 끝 인덱스를 저장
    *start = *end = -1;
 
    for (i=0; i<n; i++)
        for (j=i; j<n; j++){
            unsigned long int thisSum = 0;
 
            for (k=i; k<=j; k++)
                thisSum += a[k]; // basic operation
 
            if (thisSum > maxSum)
            {
                maxSum = thisSum;
                *start = i;
                *end = j;
            }
        }
    return maxSum;
}

$$T(n) = \displaystyle\sum_{i=1}^{n} \displaystyle\sum_{j=i}^{n} \displaystyle\sum_{k=i}^{j} 1$$

$$= \frac{n(n+1)(n+2)}{6}$$

$$= O(n^3)$$

MCSS 알고리즘 (Time complexity : O($n^2$))

unsigned long int mcssN2(int a[], int n, int *start, int *end){
    int i, j, k;
    unsigned long int maxSum = 0;
 
    *start = *end = -1;
 
    for (i=0; i<n; i++)
    {
        unsigned long int thisSum = 0;
 
        for (j=i; j<n; j++)
        {
            thisSum += a[j]; // basic operation
 
            if(thisSum > maxSum)
            {
                maxSum = thisSum;
                *start = i;
                *end = j;
            }
        }
    }
    return maxSum;
}

$$T(n) = \displaystyle\sum_{i=1}^{n} \displaystyle\sum_{j=i}^{n} 1$$

$$ = n + (n-1) + \ldots + 1$$

$$ = \frac{n(n+1)}{2}$$

$$ = O(n^2)$$

MCSS 알고리즘 (Time complexity : O($nlogn$))

int mcssNlogn(int a[], int start, int end){
    if (start == end){
        return a[start] > 0 ? a[start] : 0;
    }
 
    int center = (start + end) / 2;
    int maxLeftSum = mcssNlogn(a, start, center);
    int maxRightSum = mcssNlogn(a, center+1, end);
 
    int maxLeftCenterSum = 0;
    int maxRightCenterSum = 0;
    int leftCenterSum = 0;
    int rightCenterSum = 0;
 
    for (int i=center; i>=start; --i)
    {
        leftCenterSum += a[i]; // basic operation
        if (leftCenterSum > maxLeftCenterSum)
            maxLeftCenterSum = leftCenterSum;
    }
 
    for (int i=center+1; i<=end; ++i)
    {
        rightCenterSum += a[i]; // basic operation
        if(rightCenterSum > maxRightCenterSum)
            maxRightCenterSum = rightCenterSum;
    }
 
    int max = maxLeftSum;
    if(maxRightSum>max)
        max = maxRightSum;
    if(maxLeftCenterSum + maxRightCenterSum > max)
        max = maxLeftCenterSum + maxRightCenterSum;
    
    return max;
}

$$ T(n) = \begin{cases} 0 & \quad n = 1\\T(n/2) + T(n/2) + (n-1) & \quad n > 1\\ \end{cases} $$

아래와 같이 단순화해서 생각할 수 있다.

$$ T(n) = \begin{cases} 0 & \quad n = 1\\2T(n/2) + n & \quad n > 1\\ \end{cases} $$

위 식은, $n = 2^k$ 일 때, 아래와 같이 구할 수 있다.

$$ T(n) = 2T(n/2) + n $$

$$ = 2{2T(n/4)+n/2}+n $$

(위의 T(n)식에 n/2를 넣고 T(n/2)에 대입)

$$ = 4T(n/4) + 2n $$

$$ = 4(2T(n/8) + n/4) + 2n $$

$$ = 8T(n/8) + 3n $$

($n = 2^k$ 대입)

$$ 2^3T(2^(k-3))+3*2^k $$

$$ \ldots $$

$$ = 2^kT(2^(k-k) + k2^k) $$

$$ = 2^kT(2^0) + k2^k $$

(T(1) = 0 이므로)

$$ = k2^k $$

($n = 2^k$, 즉 $k = log2N$)

$$ = nlog2N $$

MCSS 알고리즘 (Time complexity : O($n$))

int mcssN(int a[], int n, int *start, int *end){
    int i, j;
    int maxSum = 0, thisSum = 0;
 
    *start = *end = -1;
 
    for (i=0, j=0; j<n; j++)
    {
        thisSum += a[j]; //basic operation
 
        if (thisSum > maxSum)
        {
            maxSum = thisSum;
            *start = i;
            *end = j;
        }
        else if(thisSum < 0)
        {
            i = j+1;
            thisSum = 0;
        }
    }
    return maxSum;
}

$$ T(n) = n $$

$$ = O(n) $$

알고리즘 별 그래프 (gnuplot)

- 데이터 만개~백만개까지 MCSS를 실행하며 얻은 데이터로 그린 그래프이다. $O(n^2)$과 $O(n^3)$은 데이터가 적다. 그 이유는 많은 연산 횟수 때문에 많은 시간이 소비되어 중간에 중단 시켰기 때문이다.

$$ O(n) $$

$$ O(nlogn) $$

$$ O(n^2) $$

$$ O(n^3) $$

정리

그래프 데이터를 출력하면서 $O(n)$ 알고리즘은 1초도 안돼서 100개의 데이터가 모두 출력 된 반면 $O(n^3)$ 알고리즘은 첫 번째 10000개의 데이터를 연산하는데 6분 가량 소요되었다. 알고리즘 시간복잡도의 중요성을 다시 한번 느낄 수 있는 데이터라고 할 수 있겠다.