通过js例子解释时间复杂度和空间复杂度

1.博客背景

今天有同事查代码的时候，因为函数写的性能不是很好，被叫回来重构，很害怕。今天，我分享了一个关于js解释的时间复杂性和空间复杂性的博客

2.复杂性的表达

如果你以前看过，你可能会看到这样一串东西

T(n)=O(f(n)) S(n)=O(f(n))称为大O符号，其中t表示算法需要执行的总时间

s表示算法所需的总空间

F(n)表示代码执行的总数

例如

函数go(n){ var item=0；//这里，a为(var I=0；I n；I) {//这里，for被执行了n次for(var j=0；j n；J) {//item=item i j在这里执行n*n次；//此处执行n*n次}}返回项；//这里执行过一次。}所以上面的代码是1 n n * n * 2 1=2 n 2n n

即t (n)=o (f (2n2n))

然后，就像我之前说的，时间复杂度看的是一个代码执行的时间趋势，所以当n，也就是规模比较大的时候，那些常量就起不到决定性的作用，所以我们这个时候忽略这些常量。这里的例子是单段代码，这里只能看到幅度最大的循环。

因此，这个最终代码的时间复杂度是t (n)=o (n)

你可以考虑数据中的平方曲线

3.时间复杂性

3.1时间复杂性的定义

首先，什么是时间复杂度？如果之前没有接触过时间复杂度的定义，你可能会认为它代表了一个代码的执行时间，其实不然。算法的时间复杂性意味着算法的执行时间是基于数据规模增长的趋势，而不是代码执行的具体时间。

3.2几种常见的时间复杂性

最简单的O(n)

for(var I=0；I n；I){ sum=I；}容易理解，这段代码的执行时间完全由N控制，所以T(n)=O(n)

当然，还有一个更简单的O(1)

函数total (n) {console.log (1)}无论如何，这个函数不受任何参数的影响，代码会完成一次。这种代码由T(n)=O(1)表示

T(n)=O(n)

上面的例子已经说了两层循环，在时间复杂度多块码的情况下，时间复杂度的计算方法

函数go(I){ var sum=0；for(var j=0；j . I；j){ sum=I；}返回总和；}函数main(n){ var RES=0；for(var I=0；I n；I){ RES=RES go(I)；//这是重点}}上述代码类型的第二个代码中调用了第一个代码，所以说在这个代码中，

go:(1 n)

在主函数中，它是(1 n*go)=(1 n n*n)

因此，最终的时间复杂度是t (n)=o (n)

3.3多块码的时间复杂度

T (n)=o (n)，用上面的距离来解释，意味着在另一个函数中调用一个函数，在这种情况下，两个函数的时间复杂度相乘。

还有一种情况，就是一个函数中有多段代码，但是没有互相调用。在这种情况下，我们只需要取最复杂的代码块

例如

函数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的最大值。

3.4对数顺序和加法

var I=1；而(I=n){ I=I * 10；}在这段代码中，可以看到while，I作为判断条件，每次都是*10，所以最后一次循环的次数不是n次，而是n次的十分之一，所以此时的时间复杂度是10i=n，i=logn

因此，结论是时间复杂度为T(n)=O(logn)

然后还有另一种情况，即通过改变变量来增加周期数，这也增加了时间复杂度

还有其他情况，如时间复杂度增加

函数go(m，n){ for(var I=0；I n；I){ console . log(1)} for(var I=0；我是；I) {console.log(2) }}请看上一段。在这段代码中，一个函数有两个循环，但是有两个形式参数。现在我们无法知道谁大谁小，所以此时代码的时间复杂度为O(m ^ n)

4.空间复杂性

4.1空间复杂性的定义

我上面提到了很多时间复杂度，比其他人都清楚。就名称而言，时间复杂性着眼于代码执行时间的趋势。同样，空间复杂度是指占用内存的趋势。

4.2常见的空间复杂性

空间复杂度没有时间复杂度复杂，常见的只有几个

毕竟，我不认为有人会一直循环各种声明变量。

如果有，请杀了它。

O(1)让a=1；设b=1；设c=1；设d=1；很简单，O(1)

让arr=Array看看这段代码。代码中创建了一个n长度的数组。显然，数组的长度是根据n决定的，所以o (n)

这里需要说明的是，这里没有循环，因为只要不在循环中不断声明变量，只改变值就不会有空间复杂度

O(n)让arr=[]为(var I=0；I n；I){ arr[I]=I for(var j=0；j n；怎么样？我突然看到这个代码是不是很刺激。我觉得如果有这样的情况，一般都会被乱棍打死。

复杂性优化

另外，在优化之前，我会偷拍一张图片给大家展示各种复杂程度的曲线，让大家有一个直观的了解

举一个优化的简单例子

console.time('a ')函数go(n){ var item=0；for(var I=1；I=n；I){ item=I；}退货项目；} console . timeend(' a ')console . time(' b ')函数go2(n){ var item=n *(n ^ 1)/2返回项；}控制台。时间结束(' b') go (1000) go2 (1000)你可以打印出来看看。

我希望你能原谅我数学不好。我记得以前看到过算术级数的例子，但是我想不出其他性能优化的例子

希望大家看完之后能理解这些概念。有时候这东西真的很重要。找一个高曲线的例子

斐波那契等于从第三个项目开始依次前两个项目的总和

斐波那契定义

函数Fibonacci(n){ if(n=1){ return n；} else { return Fibonacci(n-1)Fibonacci(n-2)；}}console.time('b ')斐波那契(？)console.timeEnd('b ')如果你感兴趣，可以尝试打印出来并查看时间，但大约50次后浏览器应该不会响应。详情请查阅图表。

以上是我对时间复杂度和空间复杂度的理解，有一些不足或错误。我希望指出它们

摘要

以上就是本文的全部内容。希望本文的内容对大家的学习或工作有一定的参考价值。谢谢你的支持。