数据结果与算法分析(1)——算法分析

在确定一个算法正确的同时，也要保证算法的有效性。算法分析的最重要的标准时运行时间T(N)，运行时间与输入元素个数N有关。

数学基础

T(N) = O(f(N)) 表示T(N)以不快于f(N)的速度增长，也就是说，f(N)是T(N)的上界。f(N) = Ω(T(N)) 表示T(N)是f(N)的下届。

例：N3增长快于N2，因此N2 = O(N3) 或 N3 =Ω(N2)

法则：

若T1(N) = O(f(N))且T2(N) = O(g(N)),则有(a) T1(N)+ T2(N) = max{ O(f(N)) , O(g(N)) };(b) T1(N)* T2(N) =O( f(N * g(N) ).
如T(N)是k次多项式，则T(N) = theta（ Nk ）
logkN = O(N)

大O中不包含常数项和低阶项。

算法运行时间

算法估计的运行时间一般是最坏运行时间。运行时间计算的一般法则：

for循环：至多是for循环的语句(包括测试)的运行时间乘以迭代次数。
嵌套for循环：嵌套内的一条语句的运行时间是该语句运行时间乘以所有外层for循环大小的乘积。
顺序语句：所有语句中运行时间的最大值。
if S1 else S2：至多为判断加上max（S1，S2）。

算法举例 (1)最大序列和问题

最大序列和问题的求解给出了四种解法，其中前两种解法是最常规的遍历所有的子序列和，这样的方法运行时间比较大，分别为O(N3)和O(N2)，对于这两种方法这里不详细叙述，重点叙述采用所谓“分治策略”的算法以及一个十分巧妙的算法。

解一：

将整个序列划分成三个部分，左半部分、右半部分以及跨越中部包含左右的中间部分。那么子序列和的最大值就只能出现在这三个位置。这样就可以以递归的方式求得左右部分的最大子序列和，然后将二者结合求出中间部分(包含左半部分的最后一个元素和右半部分的第一个元素)的最大子序列和。这个算法的时间复杂度为O(N logN)算法代码如下。

static int
MaxSubSum(const int A[], int left, int right)
{
    int MaxLeftSum, MaxRightSum;
    int MaxLeftBorderSum, MaxRightBorderSum;
    int LeftBorderSum, RightBorderSum;
    int center, i;

    if(left == right)
    {
        if(A[left] > 0)
            return A[left];
        else
            return 0;

    }

    center = (left + right) / 2;
    MaxLeftSum = MaxSubSum(A, left, center);
    MaxRightSum = MaxSubSum(A, center + 1, right);

    MaxLeftBorderSum = 0; LeftBorderSum = 0;
    for(i = center; i >= left; i --)
    {
        LeftBorderSum += A[i];
        if(LeftBorderSum > MaxLeftBorderSum)
            MaxLeftBorderSum = LeftBorderSum;
    }
    
    MaxRightBorderSum = 0; RightBorderSum = 0;
    for(i = center + 1; i <= right; i ++)
    {
        RightBorderSum += A[i];
        if(RightBorderSum > MaxRightBorderSum)
            MaxRightBorderSum = RightBorderSum;
    }

    return Max( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum);

}
int 
MaxSubsequenceSum(const int A[], int N)
{
    return MaxSubSum(A, 0, N-1);
}

解二:

这种解法可以被叫做扫描法，因为它只需要对数据进行一次扫描，一旦A[i]被读入处理，A[i]就不需要被记忆了，算法能对它已经读入的数据给出正确答案，这样的算法也叫做联机算法(online algorithm)。现在来解释这一个算法的运行过程，对于一个数列中的元素，依次读入数组的元素并求和，每次求和之后与之前获得的最大和比较，若比之大则更新最大和，若比之小则不更新，若小于0，则令为0(题设：若数据全为负，则输出为0)。如果前k个数的和为负，那么这个和与之后的元素的和不会大于这个元素本身，因此将有负数的和令为0是可行的。

下面先给出这种算法的代码表示。

int 
MaxSubsequenceSum(const in 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;
}

算法举例 (2)对分查找

对分查找：给定一个整数X和整数A0,A1…….An-1，后者已排序，求X在A中的下标，若不在数据中返回-1。

对分查找的基本思想是，用X与中间元素对比，如相等则可返回，若X比中间元素大，则继续在后半部分（假设升序）递归查找，反之在前半部分递归查找。算法如下：

int 
BinarySearch(const ElementType A[], ElementType X, int N)
{
    int left, right, mid;

    left = 0; right = N - 1;
    mid = (left + right) / 2;

    while(left <= right)  //查找是否结束
    {
        if(X == A[mid])
            return mid;

        else if(X > A[mid])
            left = mid + 1;
        else 
            right = mid - 1;
    }

    return -1;
}

算法举例 (3)欧几里得算法

欧几里得算法是用来计算最大公因数的。从下面的算法描述中可以看出，这个算法非常精妙，而且复杂度为O(logN)。欧几里得算法依赖一个定理

gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0)

实际上，在算法中如果N>M时，循环的第一次迭代将使他们互换。

unsigned int Gcd(unsigned int M, unsigned int N)
{
    unsigned int Rem;

    while(N > 0)
    {
        Rem = M % N;
        M = N;
        N = Rem;
    }
    return M;
}

算法举例 (4)高效率求幂运算

常规的X^N求幂运算方法是对X进行N-1此自乘，其复杂度为O(N)，可以想象，在N很大的时候其消耗还是很惊人的。因为XN=X^N/2*X^N/2,于是有下面递归实现的高效率求幂运算。由于把一个求幂运算分成两个最多只需要两次乘法(N为奇数时)，所以乘法总次数最多为2logN.

long int    //long int防止过大的数溢出
Pow(long int X, unsigned int N)
{
    if(N == 0)
        return 1;
    if(N == 1)
        return X;
    if(N % 2 == 0)
        return Pow(X*X, N/2);
    else
        return Pow(X*X, N/2) * X;

}