shimmer的博客

js时间复杂度与空间复杂度

前端|其它

发布于2021-12-26 最近修改2022-04-29

744

Shimmer

定义：

时间复杂度：

时间复杂度看的是代码的执行时间的趋势

空间复杂度：

空间复杂度就是指的占用内存的趋势

复杂度的表示方式：

大O表示法：

javascript
复制代码
T(n) = O(f(n)) 
S(n) = O(f(n))

T代表的是算法需要执行的总时间
S表示的算法需要的总空间
f(n)表示的是代码执行的总次数

举个例子

javascript
复制代码
function go(n) { 
 var item = 0;   // 这里执行了一次
 for (var i = 0; i < n; i++) {  //这里执行了N次
  for (var j = 0; j < n; j++) {   //这里执行了n*n次
   item = item + i + j;   //这里执行了n*n次
  }
 }
 return item; //这里执行了一次
}

所以说上边这段代码是 1+n+nn2+1=2+n+2n²
也就是说 T(n) = O(f(2+n+2n²))
然后之前说了时间复杂度看的是一个代码执行的时间的趋势，所以说在N，也就是规模比较大的时候，那些常量是起不到决定性的作用的，所以这个时候我们忽略这些常量，这里的例子是一个单段的代码，这里只看最大量级的循环就可以了
所以最后的这个代码的时间复杂度是T(n) = O(n²)

时间复杂度

首先什么是时间复杂度，时间复杂度这个定义如果在之前没有接触过的话，你可能会认为他代表的是一个代码执行的时间，其实不然，算法的时间复杂度就是说一个算法的执行时间根据数据规模增长的一个趋势，并不是说代码执行的具体时间

几种常见的时间复杂度

**最简单的O(n) **

javascript
复制代码
for (var i = 0; i < n; i++) { 
	sum += i; 
}

通俗易懂，这段代码的执行时间完全由N来控制，所以说T(n) = O(n)
当然还有个更简单的O(1)

javascript
复制代码
function total(n) {
	console.log(1)
}

无论怎么样，这段函数不受任何参数影响，代码走一遍就完事，这种的代码用T(n) = O(1) 表示
T(n) = O(n²)

上边的例子已经说了一个了两层循环的那种，在举一个时间复杂度多块代码的情况时间复杂度的计算方式

javascript
复制代码
function go(i) {
 var sum = 0;
 for (var j = 0; j < i; j++) {
  sum += i;
 }
 return sum;
}
function main(n) {
 var res = 0;
 for (var i = 0; i < n; i++) {
  res = res + go(i); // 这里是重点
 }
}

在上边的代码种第二段代码里边调用了第一段代码，所以说在这个代码里边是：go：（1+n）
在main函数里边的时候是(1+ngo)=(1+n+nn)，所以最后的时间复杂度是T(n) = O(n²)

多块代码的时间复杂度

上边距离说明的T(n) = O(n²) ，是一个函数在另一个函数里边被调用，这种情况是被把两个函数的时间复杂度相乘。
还有另外一种情况，就是说在一个函数里边有多块代码，但是并没有被相互调用，那么这种情况的时候，我们只需要取复杂度最大的代码块就可以了
比如说

javascript
复制代码
    function go(n) {
     for (var i = 0; i < n; i++) {
      for (var j = 0; j < n; j++) {
       console.log(1)
      }
     }

     for (var i = 0; i < n; i++) {
      console.log(2)
     }
    }

上边这块代码中，第一块代码有两层循环，通过上边的例子我们已经得知复杂度是n²
下边这块代码，是n
那么在这种情况的时候，当N接近无限大的时候N是对n²起不到决定性作用的，所以上边这块代码的时间复杂度就是取最大值的n²

对数阶和相加情况

javascript
复制代码
var i = 1;
while (i <= n) {
    i = i * 10;
}

在这段代码中，可以看到while里边，作为判断条件的i被每次*10，那么所以说最后循环的次数并不是n次，而是说十分之一n次，所以说这个时候的时间复杂度是10i=n，
i=logn
所以得出结论就是时间复杂度是T(n)=O(logn)
然后还有一种情况就是通过改变的变量去增加循环次数的，同理是增加了时间复杂度
还有一些其他的情况比如时间复杂度相加

javascript
复制代码
function go(m,n) {

 for (var i = 0; i < n; i++) {
  console.log(1)
 }

 for (var i = 0; i < m; i++) {
  console.log(2)
 }

}

请看上边这一段，这段代码里边一个函数里边有两个循环，但是形参有两个，我们现在无法得知n和m到底谁大谁小，所以说这个时候代码的时间复杂度是O(m+n)

空间复杂度

空间复杂度就是指的占用内存的趋势

常见的空间复杂度

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

O(1)

javascript
复制代码
let a = 1;
let b = 1;
let c = 1;
let d = 1;

很简单，O(1)

O(n)

javascript
复制代码
let arr =Array(n)

看这句代码，代码中创建了一个n长度的数组，很明显数组的长度根据n来决定，所以说O(n)
这里需要说明一下，这里没有用循环，是因为只要不是在循环里边不停的声明变量，只改变值的话是不会层架空间复杂度的

O(n²)

javascript
复制代码
let arr=[]
for (var i = 0; i < n; i++) {
  arr[i]=i
  for (var j = 0; j < n; j++) {
    arr[i][j]=j
  }
}

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

复杂度的优化

在说优化之前我先盗一张图给大家看一下各个复杂度的曲线图，方便大家有一个直观的认识

Preview

举个比较简单的优化的例子

javascript
复制代码
console.time('a')
function go(n) {
   var item = 0;
   for (var i = 1; i <= n; i++) {
    item += i;
   }
   return item;
}
console.timeEnd('a')

console.time('b')
function go2(n) {
 var item = n*(n+1)/2
 return item;
}
console.timeEnd('b')

go(1000)
go2(1000)

大家可以打印一下看一下
希望大家原谅我数学不好，记得之前看到过一个等差数列的例子，想不到其他的性能优化的例子
希望大家看完之后可以了解这些概念，有的时候这个东西真的很重要，找一个曲线比较高的例子
斐波那契，就是从第三项开始依次等于前两项的和
斐波那契定义

javascript
复制代码
function Fibonacci(n) {
  if (n <= 1 ) {
    return n;
  } else {
    return Fibonacci(n - 1) + Fibonacci(n - 2);
  }
}

console.time('b')
Fibonacci(????)
console.timeEnd('b')

有兴趣的可以试试打印一下，看看时间，不过大概50次的时候你得浏览器就应该没有响应了，具体请往上看曲线图。。。。

常见的时间复杂度分析

最高量级的复杂度，效率是递减的

Preview

如上图可以粗略的分为两类，多项式量级和非多项式量级。其中，非多项式量级只有两个：O(2n) 和 O(n!) 对应的增长率如下图所示

Preview

当数据规模 n 增长时，非多项式量级的执行时间就会急剧增加，所以，非多项式量级的代码算法是非常低效的算法。

总结

分析算法执行效率与数据规模之间的增长关系，可以粗略的表示，越高阶复杂度的算法，执行效率越低。复杂度学习之后，有时候可以避免写出效率低的代码。

版权所属：Shimmer

本文链接：https://wp-boke.work/blog-details/15

作品许可：本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。

没有了