数据结构与算法（二）时间复杂度和空间复杂度

算法效率

算法的效率主要由以下两个复杂度来评估：

• 时间复杂度（time complexity）：评估执行程序所需的时间。
• 空间复杂度（space complexity）：评估执行程序所需的存储空间。

设计算法时，一般是要先考虑系统环境，然后权衡时间复杂度和空间复杂度，选取一个平衡点。不过，算法时间复杂度如果恰当会给程序带来速度上质的的飞跃，不特别说明的情况下，复杂度就是指时间复杂度。但在内存紧缺的情况下，可以牺牲少许性能使内存占用更少，例如手机设备内存非常紧缺,Android上Google推荐使用ArrayMap替代Java中的HashMap,虽然性能相差无几，甚至还稍差与HashMap,但内存占用更少，该例就是减少了空间复杂度。

---

算法时间复杂度

概念

在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并确定T（n）的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T（n）=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f（n）是问题规模n的某个函数。

下面对标准定义做下解释

• 问题规模n就是问题的输入量
• 一个算法花费的时间与算法中语句的执行次数成正比例，假设算法A执行次数为Ca(n) = 2n² +1,则该算法总花费时间T(n) = 常数*Ca(n);假设算法B执行次数为Cb(n) = 2n²+n,则该算法总花费时间T(n) = 常数*Cb(n)，下图给出随着问题规模n的增大，算法的花费时间图
  问题规模
  从图中可以看出只要4个表达式最高项阶数相同，4种算法的执行时间受其它项影响很小，随着n的增大，几乎可以忽略不记，甚至可以忽略与最高项的相乘的乘数。我们不需要关心每个算法具体的执行时间是多少，只需要可以体现各个算法时间长短即可，故引入了大O阶来表示算法时间复杂度，我们称之为大O记法。

推导大O阶

1. 用常数1来取代运行时间中所有加法常数。
2. 修改后的运行次数函数中，只保留最高阶项
3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数

例如一个算法执行次数f(n) = 5n²+2n+3,T(n) = O(f(n))=> T(n) = O(n²)。

常数阶

  int sum = 0,n = 100; // 执行1次  
  sum = (1+n)*n/2; // 执行1次  
  System.out.println (sum); // 执行1次 

执行次数的函数为f(n)=3，根据推导大O阶的规则1，我们需要将常数3改为1，则这个算法的时间复杂度为O(1)。如果sum = （1+n）*n/2这条语句再执行10遍，f(n)=13,算法的时间复杂度仍旧是O(1)，代码执行次数与问题规模没有关系的时间复杂度都为O(1)，我们可以称之为常数阶。

线性阶

for(int i=0;i<3n;i++){
  // 时间复杂度为O(1)的语句序列
}

循环中执行了3n次，根据推导大O阶的规则，可得算法时间复杂度为O（n）

对数阶

int count=1;
while(count < n){
  count = count * 2;
  // 时间复杂度为O(1)的语句序列
}

count每次乘以2后，其值会越来越接近n，当count不小于n时就会退出循环。假设循环的次数(也就是该题的算法执行次数)为x，则有2^x=n关系式，故x=log₂ⁿ，因此得出这个算法的时间复杂度为O(logn)。这里省略了底数，因为底数可以为2，3，等等，但具体的底数并不重要，因为随着n的增大，对结果的影响非常小。

平方阶

 for(int i=0;i<n;i++){   
      for(int j=0;j<n;i++){
          // 时间复杂度为O(1)的语句序列
      }
  }

内层循环的时间复杂度在讲到线性阶时就已经得知是O(n)，现在经过外层循环n次，那么这段算法的时间复杂度则为O(n²)。
接下来我们来算一下下面算法的时间复杂度：

for(int i=0;i<n;i++){   
      for(int j=i;j<n;i++){
          // 时间复杂度为O(1)的语句序列
      }
  }

需要注意的是内循环中int j=i，而不是int j=0。当i=0时，内循环执行了n次；i=1时内循环执行了n-1次，当i=n-1时执行了1次，我们可以推算出总的执行次数为：
n+(n-1)+(n-2)+(n-3)+……+1 ,可以看出是等差数列，看作首项为1，公差d为1，根据等差数列公式

a_n = a₁ + (n-1)d
S_n= n(a₁ + a_n)/2

可知总执行次数S_n = n (1+1+(n-1)x1)/2 = n²/2 + n/2,再根据推导大O阶规则可得时间复杂度为O（n²）

其他常见复杂度

除了常数阶、线性阶、平方阶、对数阶，还有如下时间复杂度：

1. f(n)=2n+3nlogn+10时，时间复杂度为O(nlogn)，可以称为nlogn阶。
2. f(n)=6n³+3n²+6n+5时，时间复杂度为O(n³)，可以称为立方阶。
3. f(n)=2ⁿ时，时间复杂度为O(2ⁿ)，可以称为指数阶。
4. f(n)=n!时，时间复杂度为O(n!)，可以称为阶乘阶。
   对于3,4时间复杂度，即使n比较小为100，运行时间也是噩梦般存在，故不讨论，根本不用考虑使用这种算法。

时间复杂度比较

n	logn	nlogn	n²	2ⁿ	n!
5	2	10	25	32	120
10	3	30	100	1024	3628800
50	5	250	2500	约10^15	约3.0*10^64
100	6	600	10000	约10^30	约9.3*10^157
1000	9	9000	1000 000	约10^300	约4.0*10^

从上表可以看出，O(n)、O(logn)、O(nlogn )随着n的增加，复杂度提升不大，因此这些复杂度属于效率高的算法，反观O(2ⁿ)和O(n!)当n增加到50时，复杂度就突破十位数了，这种效率极差的复杂度最好不要出现在程序中，因此在动手编程时要评估所写算法的最坏情况的复杂度。

下面给出一个更加直观的图：

时间复杂度对比

从图中可以看出O(n!)和O(2ⁿ)随着n值的增大，它们的T(n)值上升幅度非常大，而O(logn)、O(n)、O(nlogn)随着n值的增大，T(n)值上升幅度则很小。
常用的时间复杂度按照耗费的时间从小到大依次是：

O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)

算法复杂度可以从最理想情况、平均情况和最坏情况三个角度来评估，由于平均情况大多和最坏情况持平，而且评估最坏情况也可以避免后顾之忧，因此一般情况下，我们设计算法时都要直接估算最坏情况的复杂度

---

空间复杂度

程序的空间复杂度是指程序运行从开始到结束所需的存储量与问题规模的对应关系，记做：S（n）= O(f(n)),其中n是问题规模，f(n)是语句关于n的所占的存储空间的函数。
如果执行程序时，算法需要的额外空间相对于问题规模是常数，则称此算法为原地工作，空间复杂度为O(1)，如果随着n的增大，空间线性增长，则看空间复杂度为O(n)

常数阶 O(1)

int[] a = new int[1024];
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

上述代码并不随着某个变量增大而空间变大，即使第一个数组开辟了4M的存储空间，依然空间复杂度为O(1)

线性阶 O(n)

int[] m = new int[n]
int j = 1;
for(int i=1; i<=n; ++i){
    j =i;
   j++;
}

第一行分配的空间会随着n的增大而线性增大，之后的for循环中没有开辟空间，故该程序空间复杂度为O(n)
再举一个O(n)的示例:

for (int i = 0; i < n; i++) {
   int a = i;
}

由于这次随着n的增大，a的变量线性增多，故空间复杂度为O(n).

对于常见的递归操作，一般空间复杂度也是O(n),因为随着问题规模的增大，方法会被执行n次，导致空间线性增长。

---

参考

https://juejin.im/post/58d15f1044d90400691834d4
<<大话数据结构>>