数据结构与算法 03：时间复杂度 & 空间复杂度

衡量不同算法的优劣一般从以下两个方面去考量

• 时间维度：是指执行当前算法所消耗的时间，通常用时间复杂度描述
• 空间维度：是指执行当前算法需要占用的内存空间，通常用空间复杂度描述

所以，评价一个算法的效率主要是看它的时间复杂度和空间复杂度。

时间复杂度

一般情况下，算法中的基本操作语句的重复执行次数是问题规模 n 的某个函数，用 T(n)表示，若有某个辅助函数 f(n)，使得当 n 趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称 f(n)是 T(n)的同数量级函数。记作T(n)= Ｏ( f(n) )，称Ｏ( f(n) )为算法的渐进时间复杂度，简称时间复杂度，主要有以下一些影响因素

• 算法输入时间
• 编译可执行代码的时间
• 执行指令的时间
• 执行重复指令的时间

这种用大写Ｏ()来表示的方式，称为大Ｏ时间复杂度表示法，这种方式并不具体表示代码真正执行的时间，而是表示代码执行时间随数据规模增长的变化趋势，也称为渐进时间复杂度，有以下一些规则

• 1、用常数1 取代运行时间中所有的常数
• 2、在修改运行次数函数中，只保留最高阶层
• 3、如果在最高阶存在且不等于1，则去除这个项目相乘的常数

一般分析时间复杂度，有以下三种方式

• 只关注循环执行次数最多的一段代码

• 加法法则：总复杂度等于量级最大的那段代码的复杂度，如果 T1(n)=Ｏ(f(n))，T2(n)=Ｏ(g(n))；那么 T(n)=T1(n)+T2(n)=max(Ｏ(f(n)), Ｏ(g(n))) =Ｏ(max(f(n), g(n))).

• 乘法准则【也可以理解为嵌套循环】：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积，如果 T1(n)=Ｏ(f(n))，T2(n)=Ｏ(g(n))；那么 T(n)=T1(n)*T2(n)=Ｏ(f(n))*Ｏ(g(n))=Ｏ(f(n)*g(n)).

常见的时间复杂度

常见的时间复杂度从小到大排序为：

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

下面简单举例说明下

• 常数阶 Ｏ(1)：只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。所以一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万的代码，其时间复杂度也是Ｏ(1)
  

对数阶 Ｏ(log2n)

线性阶 Ｏ(n)

• 平方阶 Ｏ(n^2)
  如下所示，i=0，执行n次，i=1，执行n-1次，i=2，执行n-2次，所以是一个等差数列，即Sn = n(n-1)/2 = n^2/2 + n/2，用大 Ｏ(n^2)
  

平方阶

立方阶 Ｏ(n^3)

所以找时间复杂度最高的代码，即为关键代码

最好、最坏、平均、均摊时间复杂度

• 最好：在最理想的情况下，执行这段代码的时间复杂度，即循环在第一次就可以找到它的位置
  
• 最坏：在最糟糕的情况下，执行这段代码的时间复杂度，即循环在最后一次就可以找到它的位置，而一般大O表示法描述的是底线，即最坏的情况
  
• 平均：为了方便理解，假设在数组中与不在数组中的概率都为 1/2。另外，要查找的数据出现在 0～n-1 这 n 个位置的概率也是一样的，为 1/n。所以，根据概率乘法法则，要查找的数据出现在 0～n-1 中任意位置的概率就是 1/(2n)。其平均时间的计算方式如下：
  

• 这个值就是概率论中的加权平均值，即期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。

均摊时间复杂度

均摊时间复杂度，以及它对应的分析方法，摊还分析（或者叫平摊分析），以下面这个插入算法为例，来了解什么是均摊时间复杂度

 // array表示一个长度为n的数组
 // 代码中的array.length就等于n
 int[] array = new int[n];
 int count = 0;
 void insert(int val) {
    if (count == array.length) {
       int sum = 0;
       for (int i = 0; i < array.length; ++i) {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }
    array[count] = val;
    ++count;
 }

假设数组的长度是 n，根据数据插入的位置的不同，我们可以分为 n 种情况，每种情况的时间复杂度是 O(1)。除此之外，还有一种“额外”的情况，就是在数组没有空闲空间时插入一个数据，这个时候的时间复杂度是 O(n)。而且，这 n+1 种情况发生的概率一样，都是 1/(n+1)。所以，根据加权平均的计算方法，我们求得的平均时间复杂度就是

因此，每一次 O(n) 的插入操作，都会跟着 n-1 次 O(1) 的插入操作，所以把耗时多的那次操作均摊到接下来的n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)。这就是均摊分析的大致思路。均摊时间复杂度其本质就是一种特殊的平均时间复杂度。

空间复杂度

算法空间复杂度是指计算算法所需的存储空间， 其计算公式为S(n) = n(f(n))，n为问题的规模，f(n)为语句关于n所占存储空间的函数。所以在考察算法的空间复杂度，主要考虑算法执行所需要的辅助空间

下面以一个问题为例，来说明空间复杂度的计算

问题: 数组逆序,将一维v1.43数组a中的n个数逆序存放在原数组中.

针对这个问题，有以下两种算法：

• 通过临时变量来做中间的交换：所需辅助空间为临时变量temp的空间，为O(1)
• 先倒序存入一个数组b，在从b中依序存入a：所需的辅助空间 为 O(n)
  

解决问题的两种方式