Divide and Conquer | 分治算法

递归定义：将问题分解为若干个子问题，并递归求解子问题，最后将子问题的解组合成原问题的解。

e.g.

$$T(N)=2T(N/2)+cN,T(1)=O(1)=2^{k}cN+ckN,k=lo{g}_{2}NT(N)=O(NlogN)$$

在线算法

on-line algorithm

int MaxSubSum(int A[], int N)
{
    int ThisSum,MaxSum,j;
    ThisSum = MaxSum = 0;
    for (j = 0; j < N; j++)
    {
        ThisSum += A[j];
        if (ThisSum > MaxSum)
        MaxSum = ThisSum;
        else if (ThisSum < 0)
            ThisSum = 0;

    }
    return MaxSum;
}

T(N) = O(N)

4 Logarithms in the Running Time

[Example] binary search

二分查找

需要在已经排好序的数组中寻找 (static and sorted)

int BinarySearch(const ElementType A[], ElementType X, int N){
    int Low,Mid,High;
    Low=0,High=N-1;
    while (Low <= High)
    {
        Mid = (Low+High)/2;
        if (A[Mid] < X)
        Low = Mid+1;
        else if (A[Mid] > X)
            High = Mid-1;
        else
        return Mid;
    }
    return -1;//Not Found
}

T(N) = O(log N)

5 Check Ur Analysis

1. 代入法

When $T(N)=O(f(N)), check