资讯专栏INFORMATION COLUMN

JavaScript时间复杂度和空间复杂度

3403771864 / 460人阅读

  前言

  在JS是用来时间复杂度和空间复杂度,时间复杂度和空间复杂度是衡量一个算法是否优秀的标准,现在我们就来说手时间复杂度和空间复杂度。

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

  预先估算:首先做出算法设计,在去估算这个算法所需的时间复杂度和空间复杂度,两者进行比较,择优。

  事后统计:写一个可执行程序/脚本用来表达两个算法,交给计算机去执行,分别记录两个算法所需要的时间复杂度和空间复杂度,然后两个进行比较,选择更优秀的那个。、

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

  时间复杂度

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

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

  O(1)

  let i = 0
  console.log(i)

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

  O(n)

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

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

  O(logn)

  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),如果是相乘的话会将两个时间复杂度进行相乘。

  空间复杂度

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

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

  O(1)

  let i = 0
  console.log(i)

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

  O(n)

  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
  }

  有关JavaScript时间复杂度和空间复杂度的相关内容已讲述完毕,希望你获得更多知识。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/127836.html

相关文章

  • javascript系列】时间杂度空间杂度

    摘要:第三段,时间复杂度。五空间复杂度分析空间复杂度的话和时间复杂度类似推算。 一、前言 时间复杂度和空间复杂度,我们在大学里的算法与数据结构课程中已经学习过,这回根据项目工作中整理一下,这个估计只是一个粗略的估计分析,并不是一个准确的估计分析。 1、学习时间复杂度和空间复杂度是很有必要的,这个属于算法与数据结构的范畴,学这个是为了解决代码中的快和省的问题。这样才能使你的代码运行效率更高,占...

    dcr309duan 评论0 收藏0
  • JavaScript中的算法(附10道面试常见算法题解决方法思路)

    摘要:中的算法附道面试常见算法题解决方法和思路关注每日一道面试题详解面试过程通常从最初的电话面试开始,然后是现场面试,检查编程技能和文化契合度。值得记住的数组方法有和。一个好的解决方案是使用内置的方法。 JavaScript中的算法(附10道面试常见算法题解决方法和思路) 关注github每日一道面试题详解 Introduction 面试过程通常从最初的电话面试开始,然后是现场面试,检查编程...

    Cruise_Chan 评论0 收藏0
  • LeetCode 之 JavaScript 解答第一题 —— 两数之(Two Sum)

    摘要:步骤遍历数组数据,将根据下标和元素值存放到散列表中。目标值减去数组元素差值并在散列表中查找。测试法三一遍哈希表算法思路遍历目标值减去数组元素的差值同时判断该值在散列表中是否存在差值,如果存在,则返回否则将数据加入到散列表中。 Time:2019/4/1Title:Two SumDifficulty: simpleAuthor:小鹿 题目一:Two Sum Given an array ...

    k00baa 评论0 收藏0
  • JavaScript 数据结构与算法之美 - 冒泡排序、插入排序、选择排序

    摘要:之所以把冒泡排序选择排序插入排序放在一起比较,是因为它们的平均时间复杂度都为。其中,冒泡排序就是原地排序算法。所以冒泡排序是稳定的排序算法。选择排序思路选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 算法为王。 想学好前端,先练好内功,...

    canger 评论0 收藏0
  • JavaScript 数据结构与算法之美 - 十大经典排序算法汇总

    摘要:笔者写的数据结构与算法之美系列用的语言是,旨在入门数据结构与算法和方便以后复习。这应该是目前较为简单的十大经典排序算法的文章讲解了吧。比如原本在的前面,而,排序之后,在的后面十大经典排序算法冒泡排序思想冒泡排序只会操作相邻的两个数据。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言 算法为王。想学好前端,先练好内功,内功不行,就...

    zsy888 评论0 收藏0

发表评论

0条评论

3403771864

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<