算法效率分析

你也许和我开始学习算法的观点一样，认为学习算法没有什么用处？不过，如果你是只做C++或者Java等基本程序的设计，的确不用学习算法，
用它们本身提供的数据结构，如数组，向量，链表，再用它们的函数就ok了。但是一旦涉及大量数据的处理，就必须仔细设计数据结构和算法了。这时还用语言本身提供的，效率就很低了，因为它们是面向通用的。对于不同的数据量，为了效率最好，也要选择不同的算法，就比如排序的算法。
学习算法第一步，要会分析不同算法的效率，也就是该算法需要多少时间和空间（主要是时间）。这种分析能力还有助于知道如何设计好的算法。那么如何分析算法的运行时间呢？

1. 计算机模型：
    分析一个算法的运行时间要在一个理想计算机模型下，假设模型机每做一条基本指令都是一个时间单位1，比如加，减，乘，除。还有模型机
    的空间是无限的，即内存很大，而且从磁盘读入和写到磁盘的时间不计入（虽然这个时间很大，但是不同算法的差距不在这里）。

2. 什么时间？
    到底要分析算法的什么运行时间？运行时间有最坏情况下的运行时间和平均情况的运行时间，我们一般分析最坏情况下的运行时间，因为这是
    算法的上界而且比平均情况更好分析。运行时间一般是输入数据量N的函数，比如6N+2。

3. 如何简化计算？
    如果对最坏情况下的运行时间精确计算，是不可能的。我们的目的是比较出多个算法谁的效率更高。比如两个算法的运行时间为A(N)=6N+2,
    B(N)=N²，可以看曲线图像，B(N)的增长率比A(N)高，从某个点之后，B(N)>A(N)，所以一般舍弃常数项；若A(N)=60N+2，可以看出还是这
    个趋势，只是那个转折点后移了，所以系数也一般舍弃。当然，如果A(N)=6N+2，B(N)=7N+2，舍弃后都是N，肯定比较不了，那还是
    要计入系数，不过两个思路不同的算法一般不会是这个样子的。还有如果A(N)=N³+N²+N+1,显然N³的增长率是主要的，所以后面的低阶项
    也要舍弃。

4. 运行时间如何表达？
    从上面可以看出，我们有时会估计过高，但是这不影响体现算法整体的性能。如上面A(N)=6N+2,可以表示为A(N)=O(N),说明A(N)的运行
    时间上限可以用N的一个式子表示；A(N)=N³+N²+N+1,可以表示为A(N)=O(N³)，说明A(N)的时间上限可以用N³的式子表示。可以这样
    简洁表示都是基于上面如何简化的思想。因为对于比较出两个算法性能高低的结果没有影响。

5. 一个例子：
    这个算法是计算一个序列最大子序列和的问题，比如序列-2,11,-4,13,-5,-2最大子序列和为20，即11+(-4)+13=20。

int Max(const int A[],int N)
{
    int ThisSum,MaxSum,i,j,k;    //声明不占用时间
    MaxSum=0;                    //赋值时间单位1，舍弃
    for(i=0;i
        for(j=i;j
        {
            ThisSum=0;           //时间单位1，外面两层循环
            for(k=i;k
                ThisSum+=A[k];   //时间单位1，外面三层循环
            if(ThisSum>MaxSum)
                MaxSum=ThisSum;  //时间单位1，外面两层循环
        }
    return MaxSum;
}

     我们估算最坏情况的运行时间，第一层循环N次，第二层循环N-i次，最坏时是N，第三层循环j-i+1次，最坏也是N，所以T(N)=O(N³),
    两层循环内的赋值和判断为O(N²),低阶舍弃；最终这个算法的运行时间A(N)=O(N³)。显然，效率很低。

    可以看出算法运行时间主要用在循环上，要想提高算法效率就要减少循环，实际上第三层循环是不需要的。看下面：

int Max(const int A[],int N)
{
    int ThisSum,MaxSum,i,j;      //声明不占用时间
    MaxSum=0;                  //赋值时间单位1，舍弃
    for(i=0;i<N;i++)      //循环了N次
    {
        ThisSum=0;     //时间单位1，外面一层循环
        for(j=i;j<N;j++) //循环了N-i次
        {
            ThisSum+=A[j]; //时间单位1，外面两层循环
            if(ThisSum>MaxSum)
                MaxSum=ThisSum; //时间单位1，外面两层循环
        }
    }
    return MaxSum;
}

    按照相同的道理分析，这个算法的运行时间A(N)=O(N²)。