＜ 在 Js 中如何理解 ‘ 时间复杂度 ’ 和 ‘ 空间复杂度 ’ ＞

---

前言

在前端开发中，我们时常需要编写大量的Js代码来实现页面的动态网页交互逻辑，但是我们又是否去思考过，Js代码在运行中，有哪些因素会影响到逻辑的运算速度 以及 是否会导致性能损耗等问题，在这里，我们需要了解两个新词汇： “ 时间复杂度 ” 以及 “ 空间复杂度 ”， 说到这两个词汇。我们需要了解算法一词。

算法是指用来操作数据、解决程序问题的一组方法。对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却会有很大的区别。从表面上来阐述，时间复杂度是指执行当前算法所消耗的时间，空间复杂度是指执行当前算法需要占用多少内存空间，两者可用来衡量算法的优劣和利弊。

接下来，将对 “ 时间复杂度 ” 和 “ 空间复杂度 ” 进行讲解。

---

提示：以下是本篇文章正文内容，下面案例仅供参考

一、时间复杂度、空间复杂度的定义

定义

时间复杂度指的是一个代表算法输入值的字符串的长度的函数，定性描述该算法的运行时间。
时间复杂度是指执行算法所需要的计算工作量，记作T(n)=O(f(n))。

空间复杂度指的是对一个算法在运行过程中临时占用存储空间大小的量度，记作S(n)=O(f(n))。

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

意义

引入时间复杂度和空间复杂度的概念是为了判断该算法的对于计算机资源的需求和占用，以此来衡量算法的优劣和利弊，从而帮助我们挑选最为合适的算法，以提高代码在逻辑运算时的性能及效率，减少性能的损耗。

以下为一些常见算法的时间、空间复杂度信息：

二、借助案例， 理解时间、空间复杂度

> 1. 时间复杂度案例：

function go(n) { 
	let item = 0;      						// 这里执行了一次
	for (let i = 0; i < n; i++) {   	//这里执行了 n 次
    for (let j = 0; j < n; j++) { 	//这里执行了n*n次
      item = item + i + j;     		//这里执行了 n*n 次
    }
  }
  return item;  									//这里执行了一次
}
go(10);
1
2
3
4
5
6
7
8
9
10

所以说上边这段代码是 1 + n + n×n × 2 + 1= 2 + n + 2n²

也就是说 T(n) = O(f(2+n+2n²))

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

所以最后的这个代码的时间复杂度是T(n) = O(f(2 +n +2 n²)) = O(n²)

> 1.1 几种常见的时间复杂度

> T(O) = O(n)

for (var i = 0; i < n; i++) {   
	sum += i;   
} 
1
2
3

通俗易懂，这段代码的执行时间完全由N来控制，所以说T(n) = O(n)；

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

function total(n) { 
	console.log(1)
}
1
2
3

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

> T(n) = O(n²)

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

// 整体时间复杂度为 T(n) = O(n)
function go(i) {
  var sum = 0; 								 // 这里一次
  for (var j = 0; j < i; j++) {   // 这里 N 次
    sum += i;
  }
  return sum;									 // 这里一次
}

function main(n) {
  var res = 0;
  for (var i = 0; i < n; i++) { 	// 这里 N 次
    res = res + go(i); 					// 这里是重点
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

在上边的代码种第二段代码里边调用了第一段代码，所以说在这个代码里边是

go：（1+n）

在main函数里边的时候是(1+n × go)=(1+n+n²)

所以最后的时间复杂度是T(n) = O(n²)；

> 多块代码的时间复杂度

上边距离说明的T(n) = O(n²) ，是一个函数在另一个函数里边被调用，这种情况是被把两个函数的时间复杂度相乘。

还有另外一种情况，就是说在一个函数里边有多块代码，但是并没有被相互调用，那么这种情况的时候，我们只需要取复杂度最大的代码块就可以了

比如说

function go(n) { 
	// 这里整块是 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++) {			// 这里是 N 次
	  console.log(2)
	 }
}
1
2
3
4
5
6
7
8
9
10
11

上边这块代码中，第一块代码有两层循环，通过上边的例子我们已经得知复杂度是：n²

下边这块代码，是n

那么在这种情况的时候，当N接近无限大的时候N是对n²起不到决定性作用的，所以上边这块代码的时间复杂度就是取最大值的n²。

> 对数阶和相加情况

var i = 1;
while (i <= n) {
   i = i * 10;
}
1
2
3
4

在这段代码中，可以看到while里边，作为判断条件的i被每次*10，那么所以说最后循环的次数并不是n次，而是说十分之一 n次，所以说这个时候的时间复杂度是10i=n，i=logn。

所以得出结论就是时间复杂度是T(n)=O(logn)

然后还有一种情况就是通过改变的变量去增加循环次数的，同理是增加了时间复杂度

还有一些其他的情况比如时间复杂度相加

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

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

}
1
2
3
4
5
6
7
8
9
10

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

最后，大家可以想想一下数据中平方的曲线图，这些曲线代表着时间复杂度的趋势：

> 2. 空间复杂度案例：

上边说了那么一大堆的时间复杂度，相比各位已经比较了解了，就名字来看，时间复杂度看的是代码的执行时间的趋势，那么同理的，空间复杂度就是指的占用内存的趋势。

常见的空间复杂度

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

> S(O) = O(1)

常量空间复杂度，在一般计算中，可以省略不计。

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

> S(O) = O(n)

随变量 n 变化而变化，类似 一个一元一次方程，y = n。

let arr =Array(n)
1

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

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

> S(O) = O(n²)

相当于一元二次方程

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

上述代码，空间复杂度为： n²。这样子写，导致空间复杂度增加很多，如没有需要，建议减少循环分配内存（新增变量空间）的情况。

复杂度优化案例

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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

打印出来的内容相同，但是时间复杂度天差地别。 所以合理的优化时间、空间复杂度，对代码的性能有着很显著的提升。

---