1. 时间复杂度

算法的时间复杂度就是说一个算法的执行时间根据数据规模增长的一个趋势，并不是说代码执行的具体时间。通常用O来表示。

常见的时间复杂度由低到高排列：

  • O(1)：常数阶
  • O(log n)：对数阶
  • O(n)：线性阶
  • O(n^2)：平方阶
  • O(n^3)：立方阶
  • O(2^n)：指数阶
  • O(n!)：阶乘阶

image.png

1.1 时间复杂度分析准则

  • 只关注循环执行次数最多的一段代码；
  • 加法法则：总复杂度等于量级最大的那段代码的复杂度；
  • 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

1.2 几种常见的时间复杂度分析

1.2.1 O(1)

这是理想的情况，无论有多少个项目，不管是一个还是一百万个，完成的时间量都将保持不变。执行单个操作的大多数操作都是O(1)。把数据写到数组、在特定索引处获取项目、添加子元素等都将会花费相同的时间量，这与数组的长度无关。

  1. function test(n) {
  2.   Array(5).push(n)
  3. }

1.2.2 O(n)

在默认情况下，所有的循环都是线性增长的，因为数据的大小和完成的时间之间存在一对一的关系。所以如果你有1,000个数组项，将会花费的1,000倍时间。

  1. function test(n) {
  2.   for(let i = 0; i < n; i++) {
  3.     console.log(i)
  4.   }
  5. }

1.2.3 O(n^2)

指数增长是一个陷阱，我们都掉进去过。你是否需要为数组中的每个项目找到匹配对？将循环放入循环中是一种很好的方式，可以把1000个项目的数组变成一百万个操作搜索，这将会使你的浏览器失去响应。与使用双重嵌套循环进行一百万次操作相比，最好在两个单独的循环中进行2,000次操作。

  1. function test(n, m) {
  2.   for(let i = 0; i < n; i++) {
  3.     for(let j = 0; j < m; j++) {
  4.       console.log(i, j)
  5.     }
  6.   }
  7. }

1.2.4 O(logn) / O(nlogn)

对数阶时间复杂度的常见代码如下：

  1. function total1(n) {
  2.   var sum = 0;
  3.   var i = 1;
  4.   while (i <= n) {
  5.     sum += i;
  6.     i = i * 2;
  7.   }
  8. }
  10. function total2(n) {
  11.   var sum = 0;
  12.   for (var i = 1; i <= n; i = i * 2) {
  13.     sum += i;
  14.   }
  15. }

复制代码上面两个函数都有一个相同点，变量i从1开始取值，每循环一次乘以2，当大于n时，循环结束。实际上，i的取值就是一个等比数列，就像下面这样：

  1. 2^1 2^2 2^4...2^x

所以只要知道x的值，就可以知道这两个函数的执行次数了。那由2^x = n可以得出x = log2n，所以这两个函数的时间复杂度为 O(log2n)。

再看下面两个函数的时间复杂度：

  1. function total1(n) {
  2.   var sum = 0;
  3.   var i = 1;
  4.   while (i <= n) {
  5.     sum += i;
  6.     i = i * 3;
  7.   }
  8. }
  10. function total2(n) {
  11.   var sum = 0;
  12.   for (var i = 1; i <= n; i = i * 3) {
  13.     sum += i;
  14.   }
  15. }

复制代码由上可以得知，这两个函数的时间复杂度为O(log3n)。由于我们可以忽略常数，也可以忽略对数中的底数，所以在对数阶复杂度中，统一表示为O(logn)；那O(nlogn)的含义就很明确了，时间复杂度为O(logn)的代码执行了n次。

1.2.5 O(n!)

最糟糕的一种可能性是析因增长。最经典的例子就是旅行的推销员问题。如果你要在很多距离不同的城市之间旅行，如何找到在所有城市之间返回起点的最短路线？暴力方法将是检查每个城市之间所有可能的路线距离，这是一个阶乘并且很快就会失控。

由于这个问题很快会变得非常复杂，因此我们将通过简短的递归函数演示这种复杂性。这个函数会将一个数字去乘以函数自己，然后将数字减去1。阶乘中的每个数字都会这样计算，直到为0，并且每个递归层都会把其乘积添加到原始数字中。

  1. const factorial = n => {
  2.   let num = n;
  4.   if (n === 0) return 1
  5.   for (let i = 0; i < n; i++) {
  6.     num = n * factorial(n - 1);
  7.   };
  9.   return num;
  10. 10};

2. 空间复杂度

时间复杂度看的是代码的执行时间的趋势，那么同理的，空间复杂度就是指的占用内存的趋势。

空间复杂度没有时间复杂度那么复杂，常见的就那么几种

毕竟我感觉不会有人一直循环着各种花样的声明变量吧。。。

如果有，那么请打死。。。。

2.1 几种常见的空间复杂度分析

2.1.1 O(1)

  1. let a = 1;
  2. let b = 1;
  3. let c = 1;
  4. let d = 1;

2.1.2 O(n)

  1. let arr = Array(n);

看这句代码，代码中创建了一个n长度的数组，很明显数组的长度根据n来决定，所以说O(n)。

这里需要说明一下，这里没有用循环，是因为只要不是在循环里边不停的声明变量，只改变值的话是不会层架空间复杂度的。

2.1.3 O(n^2)

  1. let arr=[]
  2. for (var i = 0; i < n; i++) {
  3.   arr[i]=i
  4.   for (var j = 0; j < n; j++) {
  5.     arr[i][j]=j
  6.   }
  7. }

怎么样，猛的一看这个代码是不是很刺激，我觉得如果有这种情况的话，一般都会被乱棍打死了。。。

3. 总结

复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，一个表示执行的快慢，一个表示内存的消耗，用来分析算法执行效率与数据规模之间的增长关系，可以粗略的表示，越高阶复杂度的算法，执行效率越低。