时间复杂度和空间复杂度理解
空间复杂度和时间复杂度是算法分析中两个重要的概念,用于评估算法的性能。在前端 JavaScript 中,时间复杂度用于评估算法在最坏情况下的运行时间;空间复杂度描述了算法在执行过程中所需的内存空间的增长率,它包括算法所需的临时空间和输入数据所需的空间;理解时间复杂度和空间复杂度有助于选择更高效的算法和数据结构。
常见时间复杂度
-
O(1) - 常数时间复杂度
-
无论输入大小如何,算法所需的时间是固定的
例如:访问数组的某个元素。
const arr = [1, 2, 3]; console.log(arr[1]); // O(1)
-
-
O(log n) - 对数时间复杂度
-
每次操作都将问题规模减少一半
例如:二分查找
function binarySearch(arr, target) {let left = 0;let right = arr.length - 1;while (left <= right) {const mid = Math.floor((left + right) / 2);if (arr[mid] === target) return mid;if (arr[mid] < target) left = mid + 1;else right = mid - 1;}return -1; }
-
-
O(n) - 线性时间复杂度
-
随着输入规模的增加,运行时间线性增加
例如:遍历数组
function sum(arr) {let total = 0;for (let num of arr) {total += num; // O(n)}return total; }
-
-
O(n log n) - 线性对数时间复杂度
-
通常出现在高效的排序算法中,如归并排序和快速排序
function mergeSort(arr) {if (arr.length <= 1) return arr;const mid = Math.floor(arr.length / 2);const left = mergeSort(arr.slice(0, mid));const right = mergeSort(arr.slice(mid));return merge(left, right); }function merge(left, right) {const result = [];while (left.length && right.length) {if (left[0] < right[0]) {result.push(left.shift());} else {result.push(right.shift());}}return result.concat(left, right); }
-
-
O(n^2) - 平方时间复杂度
-
通常出现在嵌套循环中
例如:冒泡排序或选择排序
function bubbleSort(arr) {const n = arr.length;for (let i = 0; i < n; i++) {for (let j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];}}}return arr; }
-
-
O(2^n) - 指数时间复杂度
-
输入大小增加时,运行时间以指数方式增加,通常出现在解决组合问题的递归算法中
function fibonacci(n) {if (n <= 1) return n;return fibonacci(n - 1) + fibonacci(n - 2); // O(2^n) }
-
常见空间复杂度
分析空间复杂度时,需要考虑以下几个方面:
- 基本数据类型:原始类型(如数字、字符串、布尔值)占用固定大小的内存。
- 数据结构:使用的数组、对象等数据结构会影响空间复杂度。例如,数组的大小和对象的属性数量会直接影响所需的内存。
- 递归:递归调用时,每次调用都会在调用栈中占用一定的空间,因此递归的空间复杂度通常与递归的深度有关。
- 辅助空间:在某些算法中可能会使用额外的存储空间(例如,临时数组、哈希表等),这部分空间也需要计算在内。
-
O(1):常数空间复杂度。算法所需的空间不随输入规模而变化
-
在数组中查找元素而不使用额外的存储空间
function containsDuplicate(arr) {// 使用两个嵌套循环,但不使用额外的数组或对象for (let i = 0; i < arr.length; i++) {for (let j = i + 1; j < arr.length; j++) {if (arr[i] === arr[j]) {return true; // 找到重复元素}}}return false; // 没有找到重复元素 }// 示例用法 const numbers = [1, 2, 3, 4, 5, 1]; console.log(containsDuplicate(numbers)); // 输出: true
- 空间复杂度 O(1):这个函数只使用了几个基本的变量(
i
和j
),不依赖于输入数组的大小,因此其空间复杂度为 O(1)。 - 时间复杂度:虽然这个例子在时间复杂度上是 O(n²),但在空间上它并没有使用额外的空间。
- 空间复杂度 O(1):这个函数只使用了几个基本的变量(
-
-
O(n):线性空间复杂度。算法的空间需求与输入规模成正比
-
数组反转
// 空间复杂度:O(n),因为需要一个新的数组来存储反转后的结果 function reverseArray(arr) {let reversed = [];for (let i = arr.length - 1; i >= 0; i--) {reversed.push(arr[i]);}return reversed; }
-
递归求和
// 空间复杂度:O(n),因为每次递归调用都会占用栈空间,最多会有 n 层 function sum(n) {if (n === 0) return 0;return n + sum(n - 1); }
-
-
O(n^2):平方空间复杂度。常见于需要二维数据结构(如矩阵)的情况
-
输入大小增加时,运行时间以指数方式增加,通常出现在解决组合问题的递归算法中
function fibonacci(n) {if (n <= 1) return n;return fibonacci(n - 1) + fibonacci(n - 2); // O(2^n) }
-
如何计算或者判断时间复杂度和空间复杂度?
如何计算时间复杂度:
- 识别基本操作:
- 确定算法中最频繁执行的操作(例如,循环、递归)。
- 分析控制结构:
- 循环:每个循环的复杂度通常是O(n),其中n是循环次数。
- 嵌套循环:外层循环为O(n),内层循环也为O(n),则总复杂度为O(n²)。
- 递归:使用递归树或主定理进行分析。
- 简化表达:
- 忽略常数项和低阶项,保留最高阶项。
示例:
// 时间复杂度 O(n)
function linearSearch(arr, target) {for (let i = 0; i < arr.length; i++) {if (arr[i] === target) return i;}return -1;
}// 时间复杂度 O(n^2)
function bubbleSort(arr) {for (let i = 0; i < arr.length; i++) {for (let j = 0; j < arr.length - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交换[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];}}}
}
如何计算空间复杂度:
- 固定空间:
- 计算算法中使用的固定大小的变量、常量和输入输出。
- 动态空间:
- 计算依赖于输入规模的额外空间(如数组、对象、递归栈等)。
- 总空间:
- 将固定空间和动态空间相加,得出总空间复杂度。
示例:
// 空间复杂度 O(1)
function findMax(arr) {let max = arr[0]; // 使用一个额外的变量for (let i = 1; i < arr.length; i++) {if (arr[i] > max) {max = arr[i];}}return max;
}// 空间复杂度 O(n)
function createCopy(arr) {let copy = []; // 新数组,空间复杂度O(n)for (let i = 0; i < arr.length; i++) {copy[i] = arr[i];}return copy;
}
相关文章:
时间复杂度和空间复杂度理解
空间复杂度和时间复杂度是算法分析中两个重要的概念,用于评估算法的性能。在前端 JavaScript 中,时间复杂度用于评估算法在最坏情况下的运行时间;空间复杂度描述了算法在执行过程中所需的内存空间的增长率,它包括算法所需的临时空…...
详细解读sedex验厂
SEDEX验厂,即供货商商业道德信息交流认证(Supplier Ethical Data Exchange),是一种表明企业遵守商业道德的认证。以下是对SEDEX验厂的详细解读: 一、SEDEX验厂概述 SEDEX是一家总部位于英国伦敦的非营利组织…...
IOT、MES、WMS、MOM 和 EPMS 系统综合技术与业务文档
IOT、MES、WMS、MOM 和 EPMS 系统综合技术与业务文档 一、引言 在现代制造业和工业管理领域,IOT(物联网)、MES(制造执行系统)、WMS(仓库管理系统)、MOM(制造运营管理系统ÿ…...
ESP32S3 使用LVGL驱动LCD屏(ST7789主控)
ESP32S3 使用LVGL驱动LCD屏(ST7789主控) 目录 1 分析原理图 2 驱动、点亮LCD(ST7789) 2.1 在工程中添加目录、文件 2.2 添加esp_lvgl_port组件 2.3 对工程进行必要的配置 2.4 编写必要代码 3 烧录、验证 1 分析原理图 要使用SOC驱动LCD屏&#…...
Zed调试宏 C语言错误日志 异常错误调试信息
1、C中的错误码 在C语言中通过返回错误码或设置全局的errno值来反馈错误问题。errno.h是一个头文件,它定义了一个全局变量errno,用于在程序中记录和报告错误的原因。这个机制主要用于处理系统调用或标准库函数出错时的错误反馈。当系统调用或库函数…...
GitCode 光引计划征文|JavaVision:引领全能视觉智能识别新纪元
在人工智能技术飞速发展的今天,计算机视觉作为AI领域的重要分支,正逐渐渗透到各行各业中。JavaVision,作为[光引计划]的一部分,致力于提供一个基于Java的全能视觉智能识别解决方案。同时它集成了MilvusPlus,旨在提供一…...
数据分析思维(五):分析方法——假设检验分析方法
数据分析并非只是简单的数据分析工具三板斧——Excel、SQL、Python,更重要的是数据分析思维。没有数据分析思维和业务知识,就算拿到一堆数据,也不知道如何下手。 推荐书本《数据分析思维——分析方法和业务知识》,本文内容就是提取…...
《OpenCV计算机视觉》--介绍及基础操作
文章目录 《OpenCV计算机视觉》--介绍及基础操作一.OpenCV介绍二.下载OpenCV三.基础操作1.调用OpenCV2.读取图片信息3.读取图片的灰度图4.视频文件读取5.对图片进行切片6.提取RGB颜色通道7.合并颜色通道8.图片修改图片打码图片组合 9.cv2.resize10.图形运算图像加法运算cv2.add…...
利用Java爬虫获取苏宁易购商品详情
在数字化时代,电商平台的商品信息对于市场分析、价格监控和消费者决策至关重要。苏宁易购作为中国领先的电商平台之一,提供了丰富的商品信息。本文将介绍如何使用Java语言开发爬虫,获取苏宁易购商品的详细信息。 Java爬虫技术简介 Java作为一…...
【CVE-2024-53375】TP-Link Archer系列路由器认证操作系统命令注入(内附远离和代码利用)
CVE-2024-53375 TP-Link Archer系列路由器认证操作系统命令注入 受影响的设备 使用 HomeShield 功能的 TP-Link 设备容易受到此漏洞的影响。这包括 TP-Link Archer 系列的多款路由器。 经过测试 Archer AXE75(EU)_V1_1.2.2 Build 20240827(发布日期 2024 年 11 月 4 日)…...
DP动态规划(装箱问题)
# [NOIP2001 普及组] 装箱问题 ## 题目描述 有一个箱子容量为 $V$,同时有 $n$ 个物品,每个物品有一个体积。 现在从 $n$ 个物品中,任取若干个装入箱内(也可以不取),使箱子的剩余空间最小。输出这个最小值。…...
selenium学习笔记(一)
文章目录 前言一、selenium的简介java使用seleniumPython使用selenium常用的浏览器selenium的功能 二、chromeDriver的安装查看本机的chrome版本?匹配对应的chromedriver并下载在服务器上例如Centos如何安装Chrome 三、selenium内容详解chrome启动chrome启动参数元素…...
jest expect().resolves和expect().rejects原理
假设存在如下代码 export default function fetchData(fn) {return Axios.get(http://www.dell-lee.com/react/api/demo.json) } 接口返回的数据为 {"success": true } 那么对于测试代码 test(fetchData, async () > {await expect(fetchData()).resolves.to…...
大语言模型驱动的Agent:定义、工作原理与应用
文章目录 引言什么是大语言模型? Agent的概念LLM Agent的工作原理 Dify平台上的AgentLLM Agent的应用场景挑战与展望结论 引言 随着人工智能(AI)技术的发展,特别是自然语言处理(NLP)领域的进步,…...
写作词汇积累:纰漏、坎肩、颠三倒四、隔阂
纰漏 【纰漏】是指因粗心而产生的差错、小事故或漏洞 1. 在准备这次会议的过程中,我们反复核对资料,力求不出现任何【纰漏】。2. 在这次重要的项目汇报中,他小心翼翼地检查每一页 PPT,生怕出现任何【纰漏】。3. 尽管她工作一向细…...
一种简易的免杀绕过方法
一种简易的免杀绕过方法 这里我们直接参考师兄的项目https://github.com/snnxyss/In-Swor exe-shellcode-加密-运行 话不多说直接上图 这里我们用geacon作为本次实验 从这里我们可以看到 geacon已经不行了 这里我们将exe转shellcode 生成之后将123.txt放到config目录下 利…...
CTF web解题 [NISACTF 2022]popchains PHP反序列化 pop链
不积跬步无以至千里 不积小流无以成江海 对web方向有了更近一步的了解,根据一道题目来学习PHP反序列化及pop链 [NISACTF 2022]popchains flag:NSSCTF{3096663a-4b18-4567-bdfb-8403f9414704} Happy New Year~ MAKE A WISH <?php echo?Happy?Ne…...
重温设计模式--单例模式
文章目录 单例模式(Singleton Pattern)概述单例模式的实现方式及代码示例1. 饿汉式单例(在程序启动时就创建实例)2. 懒汉式单例(在第一次使用时才创建实例) 单例模式的注意事项应用场景 C代码懒汉模式-经典…...
AI的进阶之路:从机器学习到深度学习的演变(一)
AI的进阶之路:从机器学习到深度学习的演变 在当今科技迅猛发展的时代,人工智能(AI)、机器学习(ML)和深度学习(DL)已成为推动创新的核心力量。这三个领域虽然紧密相连,却…...
WPF+MVVM案例实战与特效(四十七)-实现一个路径绘图的自定义按钮控件
文章目录 1、案例效果2、创建自定义 PathButton 控件1、定义 PathButton 类2、设计样式与控件模板3、代码解释3、控件使用4、直接在 XAML 中绑定命令3、源代码获取4、总结1、案例效果 2、创建自定义 PathButton 控件 1、定义 PathButton 类 首先,我们需要创建一个新的类 Pat…...
Python 写的 智慧记 进销存 辅助 程序 导入导出 excel 可打印
图样: 就可以导入了 上代码 import tkinter as tk from tkinter import ttk import sqlite3 from datetime import datetime from tkinter import messagebox, filedialog import pandas as pd import reclass OrderSystem:def __init__(self, root):self.root r…...
【电商搜索】CRM: 具有可控条件的检索模型
【电商搜索】CRM: 具有可控条件的检索模型 目录 文章目录 【电商搜索】CRM: 具有可控条件的检索模型目录文章信息摘要研究背景问题与挑战如何解决核心创新点算法模型实验效果(包含重要数据与结论)相关工作后续优化方向 后记 https://arxiv.org/pdf/2412.…...
python使用pip进行库的下载
前言 现如今有太多的python编译软件,其库的下载也是五花八门,但在作者看来,无论是哪种方法都是万变不离其宗,即pip下载。 pip是python的包管理工具,无论你是用的什么python软件,都可以用pip进行库的下载。 …...
Golang 的并发优势
在如今的编程领域,一个程序能够同时处理多个任务的能力非常重要,这就是所谓的并发处理。而 Golang 在并发编程方面表现十分出色,具有很多独特的优势,简直不要太简单。 一、轻量级的协程(Goroutine) 在传统…...
5G学习笔记之Non-Public Network
目录 0. NPN系列 1. 概述 2. SNPN 2.1 SNPN概述 2.2 SNPN架构 2.3 SNPN部署 2.3.1 完全独立 2.3.2 共享PLMN基站 2.3.3 共享PLMN基站和PLMN频谱 3. PNI-NPN 3.1 PNI-NPN概述 3.2 PNI-NPN部署 3.2.1 UPF独立 3.2.2 完全共享 0. NPN系列 1. NPN概述 2. NPN R18 3. 【SNPN系列】S…...
SpringBoot——核心概念
文章目录 一.核心概念IoC/DI思想2.Ioc容器3.Bean 二.IoC入门案例三.DI入门案例分析四.bean基础配置五.bean的实例化(创建)六.bean实例化——静态工厂七.bean实例化——示例工程与FactoryBean八.bean的生命周期九.依赖注入的两种方式十.构造器注入十一.依…...
【HarmonyOs学习日志(14)】计算机网络之域名系统DNS
域名系统DNS 域名系统DNS——从域名解析出IP地址 文章目录 域名系统DNS概述域名到IP地址的解析 互联网的域名结构命名标准 域名服务器域名的解析过程 概述 域名系统DNS(Domain Name System)是互联网使用的命名系统,用来把便于人们使用的机器…...
电脑丢失bcrypt.dll文件是什么原因?找不到bcrypt.dll文件修复办法来啦!
电脑运行时常见问题及解决方案:文件丢失、文件损坏与系统报错 作为一名软件开发从业者,深知电脑在日常使用中难免会遇到各种问题,如文件丢失、文件损坏和系统报错等。这些问题不仅影响工作效率,还可能带来数据丢失的风险。今天&a…...
shell编程3
声明 学习视频来自B站UP主 泷羽sec 向脚本程序传递参数 可以向脚本程序传递一个或多参数 echo 执行的文件名是:S0 echo 第一个参数是: 1 e c h o 传递的参数作为一个字符串显示 : 1 echo 传递的参数作为一个字符串显示: 1echo传递的参数作为一个字符串显示:* echo 传递的参数…...
LAUNCHXL_F28379D_Workspace_CCS124
/// 安装 controlSUITE C:\ti\controlSUITE\device_support\F2837xD\v210 /// /// /// /// /// 删除 /// /// /// >> Compilation failure source_common/subdir_rules.mk:9: recipe for target source_common/F2837xD_Adc.obj failed "C:/ti/controlSUITE/devic…...
智慧商城:编辑切换状态,删除功能
编辑切换状态 为 编辑 注册点击事件进行状态取反,为该状态赋一个初始值 false 如果是非编辑状态是要进行结算的,否则删除 点击“编辑”状态是 要进行 “删除”,非编辑状态是要进行 “结算” 当 结算 时,希望是能 全选 进而能多卖…...
支付测试 流程
支付测试 流程 支付测试是确保支付系统安全、稳定、可靠运行的关键环节,以下是其一般流程: 测试计划阶段 明确测试目标:确定本次支付测试的重点和预期达到的目标,如测试支付功能的完整性、安全性、性能等。制定测试计划&#x…...
Ai编程从零开始全栈开发一个后台管理系统之用户登录、权限控制、用户管理-前端部分(十二)
云风网 云风笔记 云风知识库 一、创建前端部分 1、vite初始化项目 npm create vitelatest admin-frontend – --template vue-ts 2、安装必要的依赖 npm install vue-router pinia axios element-plus element-plus/icons-vue安装完成后package.json如下: {&qu…...
LeetCode 197. 上升的温度
LeetCode 197. 上升的温度 表: Weather ---------------------- | Column Name | Type | ---------------------- | id | int | | recordDate | date | | temperature | int | ---------------------- id 是该表具有唯一值的列。 没有具有相同 recordDate 的不同行。…...
ECharts散点图-气泡图,附视频讲解与代码下载
引言: ECharts散点图是一种常见的数据可视化图表类型,它通过在二维坐标系或其它坐标系中绘制散乱的点来展示数据之间的关系。本文将详细介绍如何使用ECharts库实现一个散点图,包括图表效果预览、视频讲解及代码下载,让你轻松掌握…...
【pycharm】对需要传参数以及配置文件的情况进行debug教程
【pycharm】对需要传参数以及配置文件的情况进行debug教程 例如下面这个项目,我们要运行需要在终端输入 python main.py -mtrain -trsr0.03 -vsr0.01其中 -m‘train’ -trsr0.03 -vsr0.01是我们需要传的参数 在终端运行如下: 如果我们要进行debug的话…...
three.js混合白色模型的智慧城市扫光效果
three.js混合白色模型的智慧城市扫光效果 https://threehub.cn/#/codeMirror?navigationThreeJS&classifyshader&idcityBlendLight import * as THREE from three import { OrbitControls } from three/examples/jsm/controls/OrbitControls.js import { FBXLoader …...
【QT常用技术讲解】发送POST包(两种方式:阻塞方式及非阻塞方式)
前言 http/https(应用层)协议是广泛使用的网络通信协议。在很多与第三方API对接的场景中,通常是通过http/https协议完成,比如API对接时,通常要通过POST包获取access_token进行鉴权,然后再进行数据交互(本篇也包含有对接…...
基于Python大数据的电影可视化分析系统
标题:基于 Python 大数据的电影可视化分析系统 内容:1.摘要 本文介绍了一个基于 Python 大数据的电影可视化分析系统。该系统通过收集和分析大量电影数据,提供了对电影市场的深入洞察。文章首先介绍了系统的背景和目的,然后详细描述了系统的架构和功能。…...
Vue3:uv-upload图片上传
效果图: 参考文档: Upload 上传 | 我的资料管理-uv-ui 是全面兼容vue32、nvue、app、h5、小程序等多端的uni-app生态框架 (uvui.cn) 代码: <view class"greenBtn_zw2" click"handleAddGroup">添加班级群</vie…...
VBA技术资料MF243:利用第三方软件复制PDF数据到EXCEL
我给VBA的定义:VBA是个人小型自动化处理的有效工具。利用好了,可以大大提高自己的工作效率,而且可以提高数据的准确度。“VBA语言専攻”提供的教程一共九套,分为初级、中级、高级三大部分,教程是对VBA的系统讲解&#…...
redis使用注意哪些事项
1. 数据类型选择: • Redis支持多种数据类型,如字符串(String)、哈希(Hash)、列表(List)、集合(Set)、有序集合(Sorted Set)等。在选择…...
Go使用sqlx操作MySQL完整指南
# Go使用sqlx操作MySQL完整指南## 1. 安装依赖bash go get github.com/go-sql-driver/mysql go get github.com/jmoiron/sqlx2. 数据库基础操作 package mainimport ("fmt"_ "github.com/go-sql-driver/mysql""github.com/jmoiron/sqlx" )// 定…...
计算机基础复习12.23
ThreadLocal 线程隔离:ThreadLocal为每个线程提供了独立的变量副本,意味着线程之间不会相互影响,可以安全的在多线程环境中使用这些变量而不必担心数据竞争或同步问题 ThreadLocal的实现依赖于Thread类中的一个ThreadLocalMap字段ÿ…...
Jenkins介绍
Jenkins 是一款流行的开源自动化服务器,在软件开发和持续集成 / 持续交付(CI/CD)流程中发挥着关键作用。 一、主要功能 1.持续集成(CI) (1).自动构建:Jenkins 可以配置为监听代码仓…...
RK3588 , mpp硬编码yuv, 保存MP4视频文件.
RK3588 , mpp硬编码yuv, 保存MP4视频文件. ⚡️ 传送 ➡️ Ubuntu x64 架构, 交叉编译aarch64 FFmpeg mppRK3588, FFmpeg 拉流 RTSP, mpp 硬解码转RGBRk3588 FFmpeg 拉流 RTSP, 硬解码转RGBRK3588 , mpp硬编码yuv, 保存MP4视频文件....
Delphi WebBrowser 基本操作与常见问题的解决方案
前言 WebBrowser 作为Delphi 常见的网络浏览控件,我这里整理了一些它的基本操作,遇到了一些问题,我梳理了一下并给出解决方案 基本操作 WebBrowser1.GoHome; //到浏览器默认主页 WebBrowser1.Refresh; //刷新 WebBrowser1.GoBack; //后退 Web…...
【更新】LLM Interview
课程链接:BV1o217YeELo 文章目录 LLM基础相关1. LLMs概述2. 大语言模型尺寸3. LLMs的优势与劣势4. 常见的大模型分类5. 目前主流的LLMs开源模型体系有哪些(Prefix Decoder,Causal Decoder,Encoder-Decoder的区别是什么)…...
从零开始C++棋牌游戏开发之第一篇:C++ 游戏开发环境搭建与工具简介
前言:作者的感想 每一次选择开始一项新技能的学习,总会让人感到既兴奋又有些许忐忑。C 游戏开发,尤其是针对棋牌类游戏规则实现的开发,更是一个有趣而充满挑战的领域。作为一名开发者,我深知面对 C 时的那种 "既…...
Hydrogen-Web 项目常见问题解决方案
Hydrogen-Web 项目常见问题解决方案 hydrogen-web Lightweight matrix client with legacy and mobile browser support [这里是图片001] 项目地址: https://gitcode.com/gh_mirrors/hy/hydrogen-web 项目基础介绍 Hydrogen-Web 是一个轻量级的 Matrix 客户端,专…...