时间、空间复杂度分析

时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

在程序开发中，运行时间的长短和占用空间的大小，是衡量程序好坏的重要因素。

可以，如果连代码都没有运行，怎么预知代码所花的时间和占用空间呢？由于运行环境和输入规模的影响，代码的绝对执行时间是无法预估的。但我们却可以预估代码的基本操作执行次数。

什么是复杂度分析？

1.数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。
2.因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。
3.分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。
4.复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。

时间复杂度

场景1：给小灰一条长10寸的面包，小灰每3天吃掉1寸，那么吃掉整个面包需要几天？

答案自然是 3 X 10 = 30天。
如果面包的长度是 n 寸呢？
此时吃掉整个面包，需要 3 X n = 3n 天。
如果用一个函数来表达这个相对时间，可以记作 T（n） = 3n，执行次数是线性的。

场景2：给小灰一条长16寸的面包，小灰每5天吃掉面包剩余长度的一半，第一次吃掉8寸，第二次吃掉4寸，第三次吃掉2寸......那么小灰把面包吃得只剩下1寸，需要多少天呢？

即为2的n次方为16。以2位底，16的对数，可以简写为log16。
因此，把面包吃得只剩下1寸，需要 5 X log16 = 5 X 4 = 20 天。
如果面包的长度是 n 寸呢？
需要 5 X logn = 5logn天，记作 T（n） = 5logn，执行次数是对数计算的。

场景3：给小灰一条长10寸的面包和一个鸡腿，小灰每2天吃掉一个鸡腿。那么小灰吃掉整个鸡腿需要多少天呢？

答案自然是2天。因为只说是吃掉鸡腿，和10寸的面包没有关系 。
如果面包的长度是 N 寸呢？
无论面包有多长，吃掉鸡腿的时间仍然是2天，记作 T（n） = 2,执行次数的常数。

场景4：给小灰一条长10寸的面包，小灰吃掉第一个一寸需要1天时间，吃掉第二个一寸需要2天时间，吃掉第三个一寸需要3天时间.....每多吃一寸，所花的时间也多一天。那么小灰吃掉整个面包需要多少天呢？

答案是从1累加到10的总和，也就是55天。
如果面包的长度是 N 寸呢？
此时吃掉整个面包，需要 1+2+3+......+ n-1 + n = (1+n)*n/2 = 0.5n^2 + 0.5n。
记作 T（n）= 0.5n^2 + 0.5n，执行次数是多项式性计算的。

时间复杂度归纳：

一个算法中的基本语句执行次数称为语句频度或时间频度。记为T(n)。

n变量称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。算法中基本操作重复执行的次数是问题规模n的某个函数。

如何推导出时间复杂度呢？有如下几个原则：

1.如果运行时间是常数量级，用常数1表示；
2.只保留时间函数中的最高阶项；
3.如果最高阶项存在，则省去最高阶项前面的系数。

让我们回头看看刚才的四个场景。

场景1：

T（n） = 3n
最高阶项为3n，省去系数3，转化的时间复杂度为：
T（n） = O（n）。

场景2：

T（n） = 5logn
最高阶项为5logn，省去系数5，转化的时间复杂度为：
T（n） = O（logn）。

场景3：

T（n） = 2
只有常数量级，转化的时间复杂度为：
T（n） = O（1）

场景4：

T（n） = 0.5n^2 + 0.5n
最高阶项为0.5n^2，省去系数0.5，转化的时间复杂度为：
T（n） = O（n^2）

这四种时间复杂度究竟谁用时更长，谁节省时间呢？当n取得足够大时可以得出结论：

O（1）< O（logn）< O（n）< O（n^2）

另外：

1.T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。

2.算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。
时间复杂度分别是T1(n)=100n2，T2(n)=5n3。（1）当输入量n＜20时，有T1(n)＞T2(n)，
随着问题规模n的增大，两个算法的时间开销之比5n3/100n2=n/20亦随着增大

常见算法的时间复杂度

常数阶O(1)：无论数据规模有多大，都可以在一次计算后找到目标。
对数阶O(log n)或O(log 2n)：每找一次都排除一半的可能。
线性阶O(n)：循环时数据量增大几倍耗时也增大几倍。
线性对数阶O(n log N)：将时间复杂度为O(log n)的代码循环N遍。
平方阶O(n^2)：对数据进行排序需要扫描nn次。
立方阶O(n^3)：同上nn*n。
K次方阶O(n^k)：同上
指数阶O(2^n)：同上

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

示例：

int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) pos = i;
  }
  return pos;
}

在一个无序的数组（array）中，查找变量 x 出现的位置。如论如何都会找n次，这段代码的复杂度是 O(n)，其中，n 代表数组的长度。

修改之后：

int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}

如果数组中第一个元素正好是要查找的变量 x，那就不需要继续遍历剩下的 n-1 个数据了，那时间复杂度就是 O(1)。
但如果数组中不存在变量 x，那我们就需要把整个数组都遍历一遍，时间复杂度就成了 O(n)。
所以，不同的情况下，这段代码的时间复杂度是不一样的。

• 最好情况时间复杂度
  最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度。就像我们刚刚讲到的，在最理想的情况下，要查找的变量 x 正好是数组的第一个元素，这个时候对应的时间复杂度就是最好情况时间复杂度，如上例子就是O(1)。

• 最坏情况时间复杂度
  最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度。就像刚举的那个例子，如果数组中没有要查找的变量 x，我们需要把整个数组都遍历一遍才行，所以这种最糟糕情况下对应的时间复杂度就是最坏情况时间复杂度，如上例子就是O(n)。

• 平均情况时间复杂度
  要查找的变量 x 在数组中的位置，有 n+1 种情况：在数组的 0～n-1 位置中和不在数组中。我们把每种情况下，查找需要遍历的元素个数累加起来，然后再除以 n+1，就可以得到需要遍历的元素个数的平均值，即：

  

  可以省略掉系数、低阶、常量，所以，咱们把刚刚这个公式简化之后，得到的平均时间复杂度就是 O(n)。

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，它同样使用了大O表示法。我们常见的空间复杂度就是 O(1)、O(n)、O(n2 )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。

1.常量空间

当算法存储空间大小固定，和输入规模没有直接的关系时，即此算法空间复杂度为一个常量，可表示为 O(1)。
示例：

void fun1(int n) {
      int num = 3;
      ...
}

2.线性空间

当算法分配的空间是一个线性的集合，并且集合大小和输入规模n成正比时，空间复杂度记作O(n)。

示例：

void fun2(int n) {
      int[] array = new int[n];
      ...
}

3.二维空间

当算法分配的空间是一个二维数组集合，并且数组的长度和宽度都和输入的规模n成正比，空间复杂度就记作O(n2)。
示例：

void fun3(int n) {
      int[][] matrix = new int[n][n];
      ...
 }