亲宝软件园·资讯

展开

JavaScript时间复杂度

​ 一碗周​ 人气:0

前言

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

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

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

时间复杂度

所谓的时间复杂度就是用于定性描述算法所运行需要花费的时间,所谓的定性就是大概进行描述一下运行时间的趋势,不会去具体到运行需要多少秒;时间复杂度通常用大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
}

加载全部内容

相关教程
猜你喜欢
用户评论