数据结构01 算法的时间复杂度和空间复杂度

作者：nnngu
GitHub：https://github.com/nnngu
博客园：http://www.cnblogs.com/nnngu
简书：https://www.jianshu.com/users/1df20d76ea5c
知乎：https://www.zhihu.com/people/nnngu/posts

---

1、算法的概念：

算法 (Algorithm)，是对特定问题求解步骤的一种描述。

解决一个问题往往有不止一种方法，算法也是如此。那么解决特定问题的多个算法之间如何衡量它们的优劣呢？有如下的指标：

2、衡量算法的指标：

（1）时间复杂度： 执行这个算法需要消耗多少时间。

（2）空间复杂度： 这个算法需要占用多少内存空间。

同一个问题可以用不同的算法解决，而一个算法的优劣将影响到算法乃至程序的效率。算法分析的目的在于为特定的问题选择合适算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑 。

算法在时间的高效性和空间的高效性之间通常是矛盾的 。所以一般只会取一个平衡点。通常我们假设程序运行在足够大的内存空间中，所以研究更多的是算法的时间复杂度。

3、算法的时间复杂度

（1）语句频度T(n)： 一个算法执行所花费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。而且一个算法花费的时间与算法中的基本操作语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度，记为T(n)。

（2）时间复杂度： 在刚才提到的语句频度中，n称为问题的规模，当n不断变化时，语句频度T(n)也会不断变化。但有时我们想知道它的变化呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作 T(n)=Ｏ( f(n) )，称Ｏ( f(n) ) 为算法的渐进时间复杂度，简称时间复杂度。 　　T(n) 不同，但时间复杂度可能相同。 如：T(n)=n²+5n+6 与 T(n)=3n²+3n+2 它们的T(n) 不同，但时间复杂度相同，都为O(n²)。

（3）常见的时间复杂度有： 常数阶O(1)，对数阶O(log₂n)，线性阶O(n)，线性对数阶O(nlog₂n)，平方阶O(n²)，立方阶O(n³)， k次方阶O(n^k)，指数阶O(2ⁿ)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

（4）平均时间复杂度和最坏时间复杂度：

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。

最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。

（5）如何求时间复杂度：

【1】如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

    public static void main(String[] args) {
        int x = 91;
        int y = 100;
        while (y > 0) {
            if (x > 100) {
                x = x - 10;
                y--;
            } else {
                x++;
            }
        }
    }

该算法的时间复杂度为：O(1)

这个程序看起来有点吓人，总共循环运行了1100次，但是我们看到n没有?

没。这段程序的运行是和n无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数

【2】当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

1         int x = 1;
2         for (int i = 1; i <= n; i++) {
3             for (int j = 1; j <= i; j++) {
4                 for (int k = 1; k <= j; k++) {
5                     x++;
6                 }
7             }
8         }

该算法的时间复杂度为：O(n³) 该程序段中频度最大的语句是第5行的语句，内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此该程序段的时间复杂度为 O(n³)

【3】算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。 　　在数值 A[n-1，n-2 ...0] 中查找给定值k的算法大致如下：

1         int i = n - 1;
2         while (i >= 0 && (A[i] != k)) {
3             i--;
4         }
5         return i;

该算法的时间复杂度为：O(n)

此算法中第3行语句的频度不仅与问题规模n有关，还与输入实例A中的各元素取值和k的取值有关：如果A中没有与k相等的元素，那么第3行语句的频度为 f(n)=n ，该程序段的时间复杂度为 O(n)

（6）用时间复杂度来评价算法的性能

用两个算法A₁和A₂求解同一问题，时间复杂度分别是O(100n²)，O(5n³)

（1） 5n³/100n²=n/20 ，当输入量n＜20时，100n²> 5n³ ，这时A₂花费的时间较少。

（2）随着问题规模n的增大，两个算法的时间开销之比 5n³/100n²=n/20 也随着增大。即当问题规模较大时，算法A₁比算法A₂要高效的多。它们的渐近时间复杂度O(n²)和O(n³) 评价了这两个算法在时间方面的性能。在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度 O(f(n)) 简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。

4、算法的空间复杂度

空间复杂度(Space Complexity) 是对一个算法在运行过程中临时占用存储空间大小的量度，记做 S(n)=O(f(n)) ，其中n为问题的规模。利用算法的空间复杂度，可以对算法的运行所需要的内存空间有个预先估计。

一个算法执行时除了需要存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些计算所需的辅助空间。算法执行时所需的存储空间包括以下两部分。

（1）固定部分。这部分空间的大小与输入/输出的数据的个数、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。

（2）可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。
举例分析算法的空间复杂度：

    public void reserse(int[] a, int[] b) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            b[i] = a[n - 1 - i];
        }
    }

上方的代码中，当程序调用 reserse() 方法时，要分配的内存空间包括：引用a、引用b、局部变量n、局部变量i

因此 f(n)=4 ，4为常量。所以该算法的空间复杂度 S(n)=O(1)

5、总结

算法的时间复杂度和两个因素有关：算法中的最大嵌套循环层数；最内层循环结构中循环的次数。

一般来说，具有多项式时间复杂度的算法是可以接受的；具有指数（不是对数）时间复杂度的算法，只有当n足够小时才可以使用。一般效率较好的算法要控制在O(log₂n) 或者 O(n)