时间复杂度和空间复杂度（新手必看）

算法是对特定问题解决步骤的一种体现方式，不依赖任何语言，既可以用自然语言、C、C++、Java、Python 等体现，也可以用流程图、框图体现。对于同一个问题，可以采用不同的算法解决。

那么，怎样才算一个好算法呢？好算法的衡量标准如下：

• 正确性：指算法能够满足解决具体问题的需求，程序运行正常，无语法错误，能够通过典型的软件测试，达到预期的需求规格；
• 易读性：指算法遵循标识符命名规则，简洁、易懂，注释语句恰当、适量，既便于自己和他人阅读，也便于后期调试和修改；
• 健壮性：指算法对非法数据及操作有较好的反应和处理。例如，在信息管理系统中登记电话号码时，少输入 1 位，系统就应该提示出错；
• 高效性：指算法运行效率高，即算法运行所消耗的时间短。算法的时间复杂度就是算法运行需要的时间。现代计算机1秒能计算数亿次，因此不能用秒来具体计算算法消耗的时间。由于采用相同配置的计算机进行一次基本运算的时间是一定的，所以我们可以用算法基本运算的执行次数来衡量算法效率，即将算法基本运算的执行次数作为时间复杂度的衡量标准；
• 低存储性：指算法所需的内存空间少。尤其像手机、Pad 这样的嵌入式设备，若算法占用内存空间过大，则无法执行。

算法复杂度包括时间复杂度和空间复杂度。除前 3 条基本标准外，好算法的评判标准就是高效和低存储，高效即时间复杂度低，低存储即空间复杂度低。

时间复杂度

时间复杂度指算法运行需要的时间。一般将算法基本运算的执行次数作为时间复杂度的衡量标准。

int sum(int n){
    int sum=0; //1次
    for(int i=1;i<=n;i++) //n+1次
        sum+=i; //n次
    return sum; //1次
}

总执行次数为 2×n+3。若用一个函数 T(n)表达：

T(n)=2n+3

则当 n 足够大时，例如 n=105 时，T(n)=2×105+3。

算法运行时间主要取决于最高项，后面的可以忽略不计。因为若你告诉朋友买车花了 20万零199元，则朋友会认为你花了 20 万元，并不关心尾数。若一个人是亿万富翁，则不管其是有 2 亿元还是有 10 亿元，都是亿万富翁。

因此在表达时舍小项、舍系数，只看最高项就可以了。若用时间复杂度的渐进上界 O 表示，则该算法的时间复杂度为 O(n)。

其实完全没有必要计算每行代码的运行次数，只计算出现频率最多的语句的运行次数即可。循环内层的语句往往是运行次数最多的，对运行时间贡献最大。

例如，在下面的算法中，“total=total+i*j”是对时间复杂度贡献最大的语句，只计算该语句的运行次数即可。该算法的时间复杂度为 O(n^2)。

sum=0;        //运行1次
total=0;      //运行1次
for(i=1;i<=n;i++) { //运行n+1次，最后1次判断条件不成立，结束
    sum=sum+i;    //运行n次
    for(j=1;j<=n;j++) //运行n*(n+1)次
        total=total+i*j; //运行n*n次
}

并不是对每个算法都能直接计算运行次数。对于某些算法如排序、查找、插入等，可以按最好、最坏和平均情况分别求其渐进复杂度。但在考查一个算法时，通常考查最坏情况，而不是考查最好情况，因为最坏情况对于衡量算法的好坏具有实际意义。

空间复杂度

空间复杂度指算法在运行过程中占用了多少内存空间。

算法占用的内存空间包括：输入和输出数据占用的内存空间、算法本身占用的内存空间、额外需要的辅助空间。

输入和输出数据占用的内存空间是必需的。算法本身占用的内存空间可以通过精简算法来压缩，但压缩的量很小，可以忽略不计。

程序在运行时使用的辅助变量占用的内存空间就是辅助空间，是衡量空间复杂度的关键因素。一般将算法的辅助空间作为衡量空间复杂度的标准。

例如，将两个数交换。

swap(int x, int y) { // x 与 y 交换
    int temp;
    temp = x;       // ① temp 为辅助空间
    x = y;          // ②
    y = temp;       // ③
}

这两个数的交换过程如下图所示：


上图中的步骤标号与函数 swap() 中的语句标号一一对应，该算法使用了一个辅助空间 temp，空间复杂度为 O(1)。

注意 在递归算法中，每次递推都需要一个栈空间来保存调用记彔，因此在计算空间复杂度时需要计算递归栈的辅助空间。

例如，计算 n 的阶乘。

long long fac(int n) {
    if(n < 0)
        return -1;
    else if(n == 0 || n == 1)
        return 1;
    else
        return n * fac(n - 1);
}

递推和回归在系统内部使用栈实现，栈空间的大小为递归树的深度。计算 n 的阶乘，其递归树如下图所示。


计算 n 的阶乘时，递归树的深度为 n，因此计算 n 的阶乘的递归算法的空间复杂度为 O(n)。

总结

常见算法的时间复杂度如下：

• 常数阶：算法运行的次数是一个常数，例如 5、20、100，通常用 O(1) 表示。
• 对数阶：具有对数阶时间复杂度的算法的运行效率较高，常见的有 O(logn)、O(nlogn) 等。
• 多项式阶：对很多算法的时间复杂度都可以用多项式表达，常见的有 O(n)、O(n^2)、O(n^3)等。
• 指数阶：具有指数阶时间复杂度的算法的运行效率极差，是程序员避之不及的，常见的有 O(2^n)、O(n!)、O(n^n)等。

常见的时间复杂度函数曲线如下图所示：


从上图可以看出，指数阶增量随着 x 的增加而急剧增加，而对数阶增量增加缓慢。它们之间的关系为：

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)