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

目录
  • 前言
  • 时间复杂度
  • 空间复杂度

前言

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

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

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

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

时间复杂度

所谓的时间复杂度就是用于定性描述算法所运行需要花费的时间，所谓的定性就是大概进行描述一下运行时间的趋势，不会去具体到运行需要多少秒；时间复杂度通常用大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时间复杂度和空间复杂度的文章就介绍到这了,更多相关JavaScript时间复杂度内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • 通过js示例讲解时间复杂度与空间复杂度

    通过js示例讲解时间复杂度与空间复杂度

    1. 博客背景 今天有同事在检查代码的时候,由于函数写的性能不是很好,被打回去重构了,细思极恐,今天和大家分享一篇用js讲解的时间复杂度和空间复杂度的博客 2. 复杂度的表示方式 之前有看过的,你可能会看到这么一串东西 T(n) = O(f(n)) S(n) = O(f(n)) 这个叫做大O表示法,其中的T代表的是算法需要执行的总时间 S表示的算法需要的总空间 f(n)表示的是代码执行的总次数 举个例子 function go(n) { var item = 0; // 这里执行了一次 for

  • Javascript校验密码复杂度的正则表达式

    Javascript校验密码复杂度的正则表达式

    目前使用的正则表达式如下: 复制代码 代码如下: (?=.*\d)(?=.*[a-zA-Z])(?=.*[^a-zA-Z0-9]).{8,30} 对应的验证规则是:密码中必须包含字母.数字.特称字符,至少8个字符,最多30个字符. 这个正则表达式在C#可以正常使用,但是在Javascript中却有问题. 请问是在js中如何写这样的正则表达式? 测试字符串:a123456- 解决方法如下所示: 把\d改为[0-9]问题就解决了,正则表达式如下: 复制代码 代码如下: var regex = new

  • 如何用JavaScript学习算法复杂度

    如何用JavaScript学习算法复杂度

    概述 在本文中,我们将探讨 "二次方" 和 "n log(n)" 等术语在算法中的含义. 在后面的例子中,我将引用这两个数组,一个包含 5 个元素,另一个包含 50 个元素.我还会用到JavaScript中方便的performance API来衡量执行时间的差异. const smArr = [5, 3, 2, 35, 2]; const bigArr = [5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3, 2, 35, 2, 5, 3,

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

    目录 前言 时间复杂度 空间复杂度 前言 在上一篇文章中介绍了算法和数据结构的基本概念,这篇文章来介绍一下时间复杂度和空间复杂度. 时间复杂度和空间复杂度是衡量一个算法是否优秀的标准,通常我们比较两个算法时会用到以下两种方法: 预先估算:就是说在算法设计出来之后,根据算法中的步骤,去估算这个算法所需的时间复杂度和空间复杂度,然后两个进行比较,选择更优秀的那个: 事后统计:根据两个算法分别编写一个可执行程序/脚本,交给计算机去执行,分别记录两个算法所需要的时间复杂度和空间复杂度,然后两个进行比较,

  • Python算法的时间复杂度和空间复杂度(实例解析)

    算法复杂度分为时间复杂度和空间复杂度. 其作用: 时间复杂度是指执行算法所需要的计算工作量: 而空间复杂度是指执行这个算法所需要的内存空间. (算法的复杂性体现在运行该算法时的计算机所需资源的多少上,计算机资源最重要的是时间和空间(即寄存器)资源,因此复杂度分为时间和空间复杂度). 简单来说,时间复杂度指的是语句执行次数,空间复杂度指的是算法所占的存储空间 计算时间复杂度的方法: 用常数1代替运行时间中的所有加法常数 修改后的运行次数函数中,只保留最高阶项 去除最高阶项的系数 时间复杂度 算法的

  • Java算法之时间复杂度和空间复杂度的概念和计算

    Java算法之时间复杂度和空间复杂度的概念和计算

    一.算法效率 算法效率分析分为两种:第一种是时间效率,第二种是空间效率.时间效率被称为时间复杂度,而空间效率被称作空间复杂度. 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额外空间. 在计算机发展的早期,计算机的存储容量很小.所以对空间复杂度很是在乎.但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度.所以我们如今已经不需要再特别关注一个算法的空间复杂度.因为现在的内存不像以前那么贵,所以经常听到过牺牲空间来换取时间的说法 二.时间复杂度 2.1

  • C语言数据结构时间复杂度及空间复杂度简要分析

    C语言数据结构时间复杂度及空间复杂度简要分析

    目录 一.时间复杂度和空间复杂度是什么? 1.1算法效率定义 1.2时间复杂度概念 1.3空间复杂度概念 二.如何计算常见算法的时间复杂度和空间复杂度 2.1时间复杂度计算 2.2空间复杂度计算 2.3快速推倒大O渐进表达法 三.一些特殊的情况 总结 一.时间复杂度和空间复杂度是什么? 1.1算法效率定义 算法效率分为两种,一种是时间效率--时间复杂度,另一种是空间效率--空间复杂度 1.2时间复杂度概念 时间复杂度,简言之就是你写一个代码,它解决一个问题上需要走多少步骤,需要花费多长时间.打个

  • Java 数据结构之时间复杂度与空间复杂度详解

    Java 数据结构之时间复杂度与空间复杂度详解

    目录 算法效率 时间复杂度 什么是时间复杂度 推导大 O 阶的方法 算法情况 计算冒泡排序的时间复杂度 计算二分查找的时间复杂度 计算阶乘递归的时间复杂度 计算斐波那契递归的时间复杂度 空间复杂度 计算冒泡排序的空间复杂度 计算斐波那契数列的空间复杂度(非递归) 计算阶乘递归Factorial的时间复杂度 算法效率 在使用当中,算法效率分为两种,一是时间效率(时间复杂度),二是空间效率(空间复杂度).时间复杂度是指程序运行的速度.空间复杂度是指一个算法所需要的额外的空间. 时间复杂度 什么是时间

  • Java 关于时间复杂度和空间复杂度的深度刨析

    Java 关于时间复杂度和空间复杂度的深度刨析

    目录 1.算法效率 2.时间复杂度 2.1时间复杂度的概念 2.2大O的渐进表示法 2.3常见时间复杂度计算 2.3.1常用的时间复杂度量级 2.3.2常见示例举例 2.3.2示例答案及分析 3.空间复杂度 1.算法效率 算法效率分析分为两种:第一种是时间效率,第二种是空间效率.时间效率被称为时间复杂度,而空间效率被称作空间复杂度. 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额外空间 如今我们更关注的是时间复杂度,而对空间复杂度已不再关注. 2.时间复杂度 2

  • Java时间复杂度、空间复杂度的深入详解

    Java时间复杂度、空间复杂度的深入详解

    目录 算法效率 时间复杂度 什么是时间复杂度 推导大 O 阶的方法 算法情况 计算冒泡排序的时间复杂度 计算二分查找的时间复杂度 计算阶乘递归的时间复杂度 计算斐波那契递归的时间复杂度 空间复杂度 计算冒泡排序的空间复杂度 计算斐波那契数列的空间复杂度(非递归) 计算阶乘递归Factorial的时间复杂度 总结 算法效率 在使用当中,算法效率分为两种,一是时间效率(时间复杂度),二是空间效率(空间复杂度).时间复杂度是指程序运行的速度.空间复杂度是指一个算法所需要的额外的空间. 时间复杂度 什么

  • C语言三分钟精通时间复杂度与空间复杂度

    C语言三分钟精通时间复杂度与空间复杂度

    目录 一.时间复杂度 1)O(n)的含义 2)复杂表达式的简化 3)O(n)不一定优于O(n^2) ​4)递归的时间复杂度 二.空间复杂度 1)O(1)空间复杂度​ 2)​​​​​​​O(n)空间复杂度​ 3)​​​​​​​O(mn)空间 复杂度​ 4)递归算法空间算法复杂度分析​ 一.时间复杂度 1)O(n)的含义 程序消耗的时间用算法的操作单元数来表示 假设数据的规模为n,则用f(n)表示操作单元数的大小,而f(n)常被简化 O表示的是一般的情况,而不是上界或下界.并且它是在数据量级非常大的

  • Java 数据结构与算法系列精讲之时间复杂度与空间复杂度

    Java 数据结构与算法系列精讲之时间复杂度与空间复杂度

    目录 概述 算法的衡量标准 时间复杂度 最优时间复杂度 平均时间复杂度 最坏时间复杂度 O(1) O(n) O(n^2) O(logN) 空间复杂度 O(1) O(n) 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 算法的衡量标准 当我们需要衡量一个算法的的优越性, 通常会使用时间复杂度 (Time Complexity) 和空间复杂度 (Space Complexity) 来衡量. 时间复杂度 时间复杂度 (Time Complexity) 通常用 O(n)

随机推荐