复杂度 | 渣渣大星星的学习笔记

一、什么是复杂度分析，为什么需要复杂度分析

什么是复杂度分析

复杂度分析的是算法执行时间（或占用空间）与数据规模的增长关系

为什么需要复杂度分析

和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点，并且掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。

二、如何进行复杂度分析

大 O 表示法

算法的执行时间与每行代码的执行次数成正比，用 T(n) = O(f(n)) 表示。其中 T(n) 表示算法执行总时间，f(n) 表示每行代码执行总次数，而 n 往往表示数据的规模。这就是大 O 时间复杂度表示法。

时间复杂度

大 O 时间复杂度表示法 实际上并不具体表示代码真正的执行时间，而是表示 代码执行时间随数据规模增长的变化趋势，所以也叫 渐进时间复杂度，简称 时间复杂度（asymptotic time complexity）。

时间复杂度分析

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

单段代码看高频：比如循环

function cal(n) { 
   let sum = 0;
   let i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }

执行次数最多的是 for 循环及里面的代码，执行了 n 次，所以时间复杂度为 O(n)。

2.加法法则：总复杂度等于量级最大的那段代码的复杂度

多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。

function cal(n) {
   let sum_1 = 0;
   let p = 1;
   for (; p < 100; ++p) {
     sum_1 = sum_1 + p;
   }

   let sum_2 = 0;
   let q = 1;
   for (; q < n; ++q) {
     sum_2 = sum_2 + q;
   }
 
   let sum_3 = 0;
   let i = 1;
   let j = 1;
   for (; i <= n; ++i) {
     j = 1; 
     for (; j <= n; ++j) {
       sum_3 = sum_3 +  i * j;
     }
   }
 
   return sum_1 + sum_2 + sum_3;
 }

sum_1 ，明确知道执行了 100 次，而和 n 的规模无关，所以时间复杂度为 O(1)。

sum_2 时间复杂度为 O(n)

sum_3时间复杂度为O(n^2)（同理类推，如果有 3 层 for 循环，那么时间复杂度为 O(n^3)，4 层就是 O(n^4)）

总的时间复杂度就等于量级最大的那段代码的时间复杂度，所以最终时间复杂度为O(n^2)

3.乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

嵌套代码求乘积：比如递归、多重循环等。

function cal(n) {
   let ret = 0; 
   let i = 1;
   for (; i < n; ++i) {
     ret = ret + f(i); // 重点为  f(i)
   } 
 } 
 
function f(n) {
  let sum = 0;
  let i = 1;
  for (; i < n; ++i) {
    sum = sum + i;
  } 
  return sum;
 }

方法 cal 循环里面调用 f 方法，而 f 方法里面也有循环。

所以，整个 cal() 函数的时间复杂度就是，T(n) = T1(n) * T2(n) = O(n*n) = O(n2)。

4.多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加

function cal(m, n) {
  let sum_1 = 0;
  let i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }

  let sum_2 = 0;
  let j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }

  return sum_1 + sum_2;
}

以上代码也是求和，求 sum_1 的数据规模为 m、求 sum_2 的数据规模为 n，所以时间复杂度为 O(m+n)。

常用的时间复杂度分析

O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2) （平方阶）、O(n^3)（立方阶）。

举例说明 O(logn)（对数阶）:

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

代码是从 1 开始，每次循环就乘以 2，当大于 n 时，循环结束。在数学中:

2^0 2^1 2^2 … 2^k … 2^x = n

举例说明 O(nlogn)（对数阶）：

function aFun(n){
  let i = 1;
  while (i <= n)  {
     i = i * 2;
  }
  return i
}

function cal(n) { 
   let sum = 0;
   for (let i = 1; i <= n; ++i) {
     sum = sum + aFun(n);
   }
   return sum;
 }

aFun 的时间复杂度为 O(logn)，而 cal 的时间复杂度为 O(n)，所以上面代码的时间复杂度为 T(n) = T1(logn) * T2(n) = O(logn*n) = O(nlogn)

举例说明O(2n)（指数阶）：

aFunc( n ) {
    if (n <= 1) {
        return 1;
    } else {
        return aFunc(n - 1) + aFunc(n - 2);
    }
}

显然运行次数，T(0) = T(1) = 1，同时 T(n) = T(n - 1) + T(n - 2) + 1

补充：

什么是对数函数？

WX20190726-190600@2x

同时a大于0且a不等于1

时间复杂度分类

时间复杂度可以分为：

最好情况时间复杂度（best case time complexity）：在最理想的情况下，执行这段代码的时间复杂度。

最坏情况时间复杂度（worst case time complexity）：在最糟糕的情况下，执行这段代码的时间复杂度。

平均情况时间复杂度（average case time complexity），用代码在所有情况下执行的次数的加权平均值表示。也叫 加权平均时间复杂度 或者 期望时间复杂度。

均摊时间复杂度（amortized time complexity）: 在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

时间复杂度总结

WX20190726-201609@2x

空间复杂度分析

类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模 n 的函数。
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模 n 有关，它随着 n 的增大而增大，当 n 较大时，将占用较多的存储单元，例如快速排序和归并排序算法, 基数排序就属于这种情况
在做算法分析时，主要讨论的是时间复杂度。 从用户使用体验上看，更看重的程序执行的速度。一些缓存产品(redis, memcache)和算法(基数排序)本质就是用空间换时间。

JavaScript 数据结构与算法之美 - 时间和空间复杂度

一、 什么是复杂度分析 ，为什么需要复杂度分析