简述

复杂度：数据结构和算法中的复杂度有两种，渐进时间复杂度（asymptotic time complexity），描述的是代码执行时间随着数据规模的增长而增长的趋势，简称时间复杂度；渐进空间复杂度（asymptotoc space complexity），描述的是代码使用空间随着数据规模的增长而增长的趋势，简称空间复杂度。通常情况下，复杂度使用大O表示法来表示：O(n)，O(logn)等等。

大O表示法

T(n)=O(f(n))

n表示的就是数据规模，T(n)表示代码执行时间，f(n)表示每行代码执行次数总和。

例如：

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

假定执行一行代码所需时间为unit_time，则f(n)=2*unit_time+2n*unit_time=2(n+1)*unit_time，因此T(n)=O(2n+2)，当n非常大时，系数和常数对于T(n)的影响就微乎其微了，所以通常系数和常数不计入表示法，因此上述代码的时间复杂度为：T(n)=O(n)，空间复杂度也是同理，见代码：

void print(int n) {
  int i = 0;//1 unit_space

  int[] a = new int[n];// n unit_space

  for (i; i <n; ++i) {
    a[i] = i * i;
  }

  for (i = n-1; i >= 0; --i) {
    print out a[i]
  }
}

复杂度分析

时间复杂度分析

分析方法

1：只关注循环次数最多或者循环嵌套最多的代码

循环就是O(n)，再嵌套就是O(n²)，三层循环就是O(n³)；

2：加法法则

如果一个算法里两段代码的时间规模n一样，则T(n)=T1(n)+T2(n)=max(O(f(n))+O(g(n)))=O(max(f(n),g(n)))；

如果一个算法里两段代码的时间规模不一样，分别为n和m，则T(m+n)=T1(m)+T2(n)=O(f(m))+O(f(n))=O(m+n)；

3：乘法法则

嵌套代码的复杂度等于每一层嵌套的复杂度乘积T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))。

常见复杂度

1：O(1)

多项式量级，常数阶，只要没有进行递归或者循环，普通的语句或者判断语句的复杂度都是O(1)，它并不是表示代码的具体执行时间，而是随着数据的增长，代码的执行时间并没有明显的增长，即不管代码多长，执行次数都是1次。

2：O(n)

多项式量级，线性阶，单层循环常见;

3：O(logn) O(nlogn)

多项式量级，该对数阶的推导可以参考下面代码：

i=1;
while (i <= n)  {
  i = i * 2;
}

每次都是乘以2，直到i的值大于n，每一次i的值分别是：

2¹ 2² 2³ ... 2^x，最后一项的值为n，则x=log₂n，O(f(n))=O(log₂n)，千万记住，f(n)的意思就是代码执行次数。

同理，将上述代码改为i = i * 3 时的大O表示法为O(log₃n)，根据对数换底公式：logan * lognb = logab，所以凡是对数阶的表示法都可以变为logm² * log₂n的形式，其中m为常数，由于上面所说常数项不计，因此所有对数阶都是O(logn)。

O(nlogn)则是在上述基础上再加上一个外层循环。

4：O(n²)

多次方阶，常见于嵌套循环或者递归调用。

5：O(m+n) O(m n)*

该复杂度常见于有多种数据规模的算法，算法的时间复杂度取决于多个代码段。

6：指数阶和阶乘阶

O(2^n)或者O(n!)属于非多项式量级，该复杂度的算法性能很差，所以不再考虑。

各种算法的性能图表如下：

$数据结构和算法-复杂度分析\497a3f120b7debee07dc0d03984faf04$

空间复杂度分析

空间复杂度常用的有O(1)、O(n)、O(n²)等等，由于比较简单，没有太多需要赘述。

扩展

时间复杂度还有最好时间复杂度(best case time complexity)，最坏时间复杂度(worst case time complexity)，平均时间复杂度(average case time complexity)和均摊时间复杂度(amortized time complexity)。

// n 表示数组 array 的长度
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;
}

由于不同的操作会导致复杂度的不同，所以上述代码不同场景会有不同复杂度。顾名思义，最好时间复杂度就是指在最理想的场景下的时间复杂度，只需要执行一次就可以找到需要的数据，此时时间复杂度为O(1)；最不理想的场景下，元素不在数组中，所以导致要遍历所有元素，此时时间复杂度为O(n)；而平均时间复杂度的分析，首先假设元素在数组中和不在数组中的概率分别为1/2，那么出现每个位置的的概率都是1/n，所以出现在第一个位置的代码执行次数是1 * 1/n，第二个位置的代码执行次数为2 * 1/n，而不在数组中代码执行次数为n，依此类推：

O((1\*1/n+2\*1/n+ ... + n \* 1/n) \* 1/2 + n\*1/2) = O(n(n+1)/2\*1/2n+n/2)=O((3n+1)/4)=O(n)

由于低阶、常数、系数都可以不计，所以平均时间复杂度也是O(n)，所以平均时间复杂度严格来说可以称之为平均加权复杂度或者期望时间复杂度，至于均摊时间复杂度，借助下面代码进行展示：

// 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;
}

对于大部分情况，数据一次插入，只有插入到最后一位时会执行遍历相加的操作并放到第一位，因此对于这种连续的低时间复杂度操作，其中只有少数高复杂度的操作的，分析的方式就是尝试将高复杂度的操作分摊到低复杂度操作上。一般情况下，能够分摊复杂度的算法的均摊时间复杂度都等于最好时间复杂度。