JavaScript时间复杂度

一碗周 2022-09-28 我要评论

前言

在上一篇文章中介绍了算法和数据结构的基本概念，这篇文章来介绍一下时间复杂度和空间复杂度。

时间复杂度和空间复杂度是衡量一个算法是否优秀的标准，通常我们比较两个算法时会用到以下两种方法：

预先估算：就是说在算法设计出来之后，根据算法中的步骤，去估算这个算法所需的时间复杂度和空间复杂度，然后两个进行比较，选择更优秀的那个；
事后统计：根据两个算法分别编写一个可执行程序/脚本，交给计算机去执行，分别记录两个算法所需要的时间复杂度和空间复杂度，然后两个进行比较，选择更优秀的那个。、

通常情况下我们都会采用第一种方式进行对比，因为第二种在不同环境、不同语言、不同计算机下的运行结果是有差异的，而且第二种的工作量也要比第一种要大。

所谓的时间复杂度就是用于定性描述算法所运行需要花费的时间，所谓的定性就是大概进行描述一下运行时间的趋势，不会去具体到运行需要多少秒；时间复杂度通常用大O来表示，例如O(1)、O(n)、O(logn)等。

接下来我们通过具体的代码来展示一下时间复杂度，这样更方便去理解：

let i = 0
console.log(i)

因为在这个代码中，这两行代码永远只执行一次，所以时间复杂度是`O(1)`

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

在上面的代码中，运行时间取决与`n`，所以时间复杂度是`O(n)`。

let i = 1
while (i < n) {
  console.log(i)
  i *= 2
}

如果是下面这种情况：

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

它的时间复杂度是O(1) + O(n)，它最终的时间复杂度是O(n)，两个时间复杂度相加的话一般会忽略较小的那个。

如果是两个时间复杂度相乘的话，例如下面这段代码：

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    console.log(j)
  }
}

这段代码的时间复杂度是O(n^2)，如果是相乘的话会将两个时间复杂度进行相乘。

空间复杂度与时间复杂度差不多，表示的是算法在运行过程中临时占用存储空间的大小的一个计量单位，

现在我们来看一下几个例子：

let i = 0
console.log(i)

因为在这个代码中，仅仅定义了一个临时变量，所以空间复杂度是`O(1)`

const arr = []
for (let i = 0; i < n; i++) {
  arr.push(i)
}

在上面的代码中，我们声明了一个数组，每循环一次都要往数组中存储一个变量，所以时间复杂度是`O(n)`

O(n^2)

let i = 1
while (i < n) {
  console.log(i)
  i *= 2
}