当前位置：首页 > news >正文

【初探数据结构】时间复杂度和空间复杂度

news 来源：原创 2025/9/16 4:14:00

💬 欢迎讨论：在阅读过程中有任何疑问，欢迎在评论区留言，我们一起交流学习！
👍 点赞、收藏与分享：如果你觉得这篇文章对你有帮助，记得点赞、收藏，并分享给更多对数据结构感兴趣的朋友

文章目录

- 时间复杂度
- - 时间复杂度的概念
  - 大O渐进表示法
  - 易错建议
- 空间复杂度
- 常见的复杂度对比
- 总结

时间复杂度

时间复杂度的概念

算法执行时间随输入规模（N）增长的渐进趋势的数学函数，具体表现为算法中基本操作的执行次数。

由于一个算法所花费的时间与其中语句的执行次数成正比例，所以算法中的基本操作的执行次数，为算法的时间复杂度。

为什么不用时间呢？

不同硬件设备运行速度差异大，实际时间不具备普适性。

即：

找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度

// 请计算一下Func1中++count语句总共执行了多少次？
void Func1(int N)
{int count = 0;for (int i = 0; i < N ; ++ i){for (int j = 0; j < N ; ++ j){++count;}}for (int k = 0; k < 2 * N ; ++ k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}

Func1执行的基本操作次数：
$F(N)=N^2+2*N+10$

那么，我们每次表示时间复杂度都要写像这样长长的表达式吗？

麻烦，而且我们没有必要去精确计算执行次数，只需要一个大概次数，所以我们使用大O渐进表示法。

大O渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。
推导大O阶方法：

目标：忽略低阶项和常数系数，聚焦最高阶项的增长趋势。

推导步骤：

用常数1替代所有加法常数（如 F(N)=1000 → O(1)）。
只保留最高阶项（如 F(N)=N³ + N² + 1 → O(N³)）。
去除最高阶项的系数（如 F(N)=3N² → O(N²)）。

使用大O的渐进表示法后，Func1的时间复杂度为：
$O(N^2)$

大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。

此外，有一些算法的时间复杂的存在最好、最坏和平均的情况：

最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)

看一个例子：在一个长度为N数组中搜索一个数据x

最坏情况：N次且没有找到
平均情况：N/2次找到
最好情况：1次找到

一般时间复杂度取用算法的最坏运行情况

所以：数组中搜索数据的时间复杂度为O(N)

易错建议

很多初学者，找时间复杂度习惯用循环去计算，实则很容易出错。建议读者一定要去观察程序的执行逻辑。
误区：循环层数越多，时间复杂度一定越高。
反例：

		for (int i = 0; i < N; i++) {       // O(N)for (int j = 0; j < 100; j++) { // 固定执行100次// 操作}}

总时间复杂度为 O(N)，而非 O(N²)

时间复杂度代表的是一个量级。你可以尽你最大的想象力去想象他有多大，我的意思是，他是无法被轻易改变的。如： $N - 9999999999999999999999 \dots\dots$ 他的时间复杂度依然为： $O (N)$ 同样的： $9999999999999999999999 \dots\dots$ 他的时间复杂度依然为： $O (1)$

空间复杂度

空间复杂度也是一个数学表达式（函数），是对一个算法在运行过程中临时占用存储空间大小的量度（注意这个临时）。也使用大O渐进表示法。

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

你知道为什么要有这个”临时“吗？

因为空间是可以重复利用的，算法中开辟过的空间重复使用空间复杂度不会增加。
而时间是一去不复返的，无法重复使用。

看一个例题你就明白了

// 计算Fib的空间复杂度？
// 返回斐波那契数列的前n项
long long Fib(size_t N)
{
if(N < 3)
return 1;
return Fib(N-1) + Fib(N-2);
}

这里的时间复杂度不难推导：O(2^N)

那么空间复杂度呢？
也是O(2^N)吗？
没错，这里重复利用了空间，实际上空间复杂度为:
$O (N)$

误区：递归算法的空间复杂度一定很高。
反例：递归遍历链表的空间复杂度为 O(N)（递归栈深度），而迭代法为 O(1)。

常见的复杂度对比

在这里插入图片描述

总结

时间复杂度关注算法执行次数的增长趋势，空间复杂度关注额外空间的占用。
大O渐近表示法通过简化表达式，聚焦主要矛盾。
实际应用中需结合具体场景选择最优算法。

【初探数据结构】时间复杂度和空间复杂度

💬 欢迎讨论：在阅读过程中有任何疑问，欢迎在评论区留言，我们一起交流学习！ 👍 点赞、收藏与分享：如果你觉得这篇文章对你有帮助，记得点赞、收藏，并分享给更多对数据结构感…...

编程日记 2025/9/16 4:14:00

将DeepSeek接入vscode的N种方法

接入deepseek方法一：cline 步骤1：安装 Visual Studio Code 后，左侧导航栏上点击扩展。步骤2：搜索 cline，找到插件后点击安装。步骤3：在大模型下拉菜单中找到deep seek，然后下面的输入框输入你在deepseek申请的api key，就可以用了让deepseek给我写了一首关于天气的…...

编程日记 2025/9/16 4:09:15

《TransMamba：一种混合Transformer-Mamba网络用于单图像去雨》学习笔记

paper：2409.00410 GitHub：sunshangquan/TransMamba 目录摘要 1、介绍 2、相关工作 2.1 单图像去雨 2.2 视觉Transformer 2.3 光谱域中的Transformer 2.4 光谱域中的图像恢复 2.5 视觉Mamba 3、方法 3.1 整体网络架构 3.2 光谱域变换块&am…...

编程日记 2025/9/16 4:03:23

危化品经营单位安全管理人员的职责及注意事项

危化品经营单位安全管理人员肩负着保障经营活动安全的重要责任，以下是其主要职责及注意事项： 职责 1. 安全制度建设与执行：负责组织制定本单位安全生产规章制度、操作规程和生产安全事故应急救援预案，确保这些制度符合国家相关法…...

编程日记 2025/9/16 4:09:15

安装Redis并把Redis设置成windows下的服务然后进行Redis实例演示

目录 （一）安装Redis （二）Redis设置成windows下的服务 1、把redis设置成windows下的服务 2、设置服务命令 （三）Redis实例演示 1、Redis插入数据 2、Redis修改数据 3、Redis删除数据 4、Redis查询数…...

编程日记 2025/9/11 10:28:14

基于 Python 的项目管理系统开发

基于 Python 的项目管理系统开发一、引言在当今快节奏的工作环境中，有效的项目管理对于项目的成功至关重要。借助信息技术手段开发项目管理系统，能够显著提升项目管理的效率和质量。Python 作为一种功能强大、易于学习且具有丰富库支持的编程语言&…...

编程日记 2025/9/9 3:05:41

牛客周赛 Round 82（思维、差分、树状数组、大根堆、前后缀、递归）

文章目录牛客周赛 Round 82（思维、差分、树状数组、大根堆、前后缀、递归）A. 夹心饼干B. C. 食堂大作战（思维）D. 小苯的排列计数(差分、树状数组)E. 和和（大根堆，前缀和）F. 怎么写线性SPJ &…...

编程日记 2025/9/14 9:21:10

【python】解析自动化脚本文件并按照=测试周期=存储记录

【python】连接Jira获取token以及jira对象【python】解析自动化脚本文件并按照测试周期存储记录【python】向Jira推送自动化用例执行成功【python】向Jira测试计划下，附件中增加html测试报告将已编写的自动化测试用例按照jira号解析出来，并按照测试计…...

编程日记 2025/9/14 20:49:40

一种简单有效的分析qnx+android智能座舱项目中的画面闪烁的方法（8155平台）

在智能座舱项目的开发过程中，画面闪烁问题是一个常见但棘手的挑战。由于这些闪烁现象往往转瞬即逝，传统的分析工具如截图、录屏或dump图层等方法难以捕捉和定位问题根源。针对这一难题，本文介绍了一种较为有效的分析方法，能够帮助…...

编程日记 2025/9/16 3:28:11

架构师论文《论湖仓一体架构及其应用》

软考论文-系统架构设计师摘要作为某省级商业银行数据中台建设项目技术负责人，我在2020年主导完成了从传统数据仓库向湖仓一体架构的转型。针对日益增长的支付流水、用户行为埋点及信贷审核影像文件等多模态数据处理需求，原有系统存在存储成本激增、实…...

编程日记 2025/9/14 3:06:47

一篇文章学懂Vuex

一、基于VueCli自定义创建项目 233 344 二、Vuex 初始准备建项目的时候把vuex勾选上就不用再yarn add vuex3了 store/index.js // 这里面存放的就是vuex相关的核心代码 import Vuex from vuex import Vue from vue// 插件安装 Vue.use(Vuex)// 创建仓库（空仓库…...

编程日记 2025/9/10 4:15:52

模拟实现Java中的计时器

定时器是什么定时器也是软件开发中的⼀个重要组件. 类似于⼀个 "闹钟". 达到⼀个设定的时间之后, 就执⾏某个指定好的代码. 前端/后端中都会用到计时器. 定时器是⼀种实际开发中⾮常常⽤的组件. ⽐如⽹络通信中, 如果对⽅ 500ms 内没有返回数据, 则断开连接尝试重…...

编程日记 2025/9/9 18:06:35

全面理解-深拷贝与浅拷贝

在 C 中，深拷贝（Deep Copy） 和浅拷贝（Shallow Copy） 是两种完全不同的对象拷贝策略，主要区别在于对指针和动态分配资源的处理方式。正确理解二者的区别是避免内存泄漏、悬空指针和程序崩溃的关键。一、核…...

编程日记 2025/9/14 9:54:26

20250212：https通信

1：防止DNS劫持：使用 https 进行通信。因为是SDK授权开发，需要尽量压缩so库文件和三方依赖。所以第一想法是使用 head only 的 cpp-httplib 进行开发。 cpp-httplib 需要 SSL 版本是 3.0及以上。但本地已经在开发使用的是1.0.2a版本，不满足需求。方案1：升级OpenSSL 将Op…...

编程日记 2025/9/14 22:30:02

如何使用爬虫获取淘宝商品详情：API返回值说明与案例指南

在电商数据分析和运营中，获取淘宝商品详情是常见的需求。淘宝开放平台提供了丰富的API接口，允许开发者通过合法的方式获取商品信息。本文将详细介绍如何使用PHP编写爬虫，通过淘宝API获取商品详情，并解析API返回值的含义和结构。一…...

编程日记 2025/9/10 22:29:24

List 接口中的 sort 和 forEach 方法

List 接口中的 sort 和 forEach 方法是 Java 8 引入的两个非常实用的函数，分别用于排序和遍历列表中的元素。以下是它们的详细介绍和用法： sort 函数功能对列表中的元素进行排序。默认使用自然顺序（如数字从小到大，字符…...

编程日记 2025/9/14 9:55:52

7.建立文件版题库|编写model文件|使用boost split字符串切分(C++)

建立文件版题库题目的编号题目的标题题目的难度题目的描述，题面时间要求(内部处理)空间要求(内部处理) 两批文件构成第一个：questions.list : 题目列表（不需要题目的内容）第二个：题目的描述，题目的预设置…...

编程日记 2025/9/15 0:16:51

鸿蒙NEXT应用App测试-专项测试（DevEco Testing）

注意：大家记得先学通用测试在学专项测试鸿蒙NEXT应用App测试-通用测试-CSDN博客注意：博主有个鸿蒙专栏，里面从上到下有关于鸿蒙next的教学文档，大家感兴趣可以学习下如果大家觉得博主文章写的好的话，可以点下关注…...

编程日记 2025/9/15 4:18:37

一周学会Flask3 Python Web开发-Jinja2模板访问对象

锋哥原创的Flask3 Python Web开发 Flask3视频教程： 2025版 Flask3 Python web开发视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili 如果渲染模板传的是对象，如果如何来访问呢？ 我们看下下面示例： 定义一个Student类 cla…...

编程日记 2025/9/15 8:42:22

docker离线安装记录

1.安装包首先需要从官方网站下载Docker的离线安装包，可以通过以下地址找到自己想安装的版本： wget https://download.docker.com/linux/static/stable/x86_64/docker-20.10.7.tgz 【Docker】Docker学习之一：离线安装Docker步骤_docker离线…...

编程日记 2025/9/13 20:14:13

FreiHAND （handposeX-json 格式）数据集-release ＞＞ DataBall

FreiHAND （handposeX-json 格式）数据集-release 注意： 1)为了方便使用，按照 handposeX json 自定义格式存储 2)使用常见依赖库进行调用,降低数据集使用难度。 3)部分数据集获取请加入：DataBall-X数据球(free) 4)完…...

编程日记 2025/9/15 10:08:17

unity学习51：所有UI的父物体：canvas画布

目录 1 下载资源 1.1 在window / Asset store下下载一套免费的UI资源 1.2 下载，导入import 1.3 导入后在 project / Asset下面可以看到 2 画布canvas，UI的父物体 2.1 创建canvas 2.1.1 画布的下面是 event system是UI相关的事件系统 2.2 canvas…...

编程日记 2025/9/4 8:26:45

anaconda不显示jupyter了？

以前下载的anaconda显示jupyter，但是最近学习吴恩达的机器学习视频，需要用到jupyter，以前的jupyter运行不了，就重新下载了一个anaconda，发现新版的anaconda首页不显示jupyter了，在查找资料之后，…...

编程日记 2025/9/8 16:40:50

WordPress平台如何接入Deepseek，有效提升网站流量

深夜改代码到崩溃？《2024全球CMS生态报告》揭露：78%的WordPress站长因API对接复杂，错失AI内容红利。本文实测「零代码接入Deepseek」的保姆级方案，配合147SEO的智能发布系统，让你用3个步骤实现日均50篇EEAT合规内容自动…...

编程日记 2025/9/15 17:17:06

第十三：路由两个注意点：

4.3. 【两个注意点】路由组件通常存放在pages 或 views文件夹，一般组件通常存放在components文件夹。通过点击导航，视觉效果上“消失” 了的路由组件，默认是被卸载掉的，需要的时候再去挂载。 <script setup lang"ts&q…...

编程日记 2025/9/8 13:28:06

【前端学习笔记】Pinia

1.介绍 Pinia 是 Vue 3 中的官方状态管理库，作为 Vuex 的继任者，它为 Vue 3 提供了一个更现代、更灵活、更易用的状态管理解决方案。Pinia 主要用于管理应用中的全局状态，并提供了一个清晰、简洁的 API 来处理复杂的状态逻辑、数据流和副作用…...

编程日记 2025/9/15 6:29:07

Windows 11【1001问】Windows 11系统硬件配置要求

Windows 11 的设计目标是让用户更贴近自己喜欢的内容，在其发布之际，计算机在连接、创作以及游戏体验方面扮演了更加核心的角色。在设定 Windows 11 的最低系统要求时，我们依据三个关键原则来指导决策，以确保用户能够获得卓越的使用…...

编程日记 2025/9/10 6:54:03

ROS ur10机械臂添加140夹爪全流程记录

ROS ur10机械臂添加140夹爪系统版本：Ubuntu20.04 Ros版本：noetic Moveit版本：moveit-noetic 参考博客： ur3robotiq ft sensorrobotiq 2f 140配置rviz仿真环境_有末端力传感器的仿真环境-CSDN博客 UR5机械臂仿真实例&#xf…...

编程日记 2025/9/4 13:27:22

火绒终端安全管理系统V2.0网络防御功能介绍

火绒终端安全管理系统V2.0 【火绒企业版V2.0】网络防御功能包含网络入侵拦截、横向渗透防护、对外攻击检测、僵尸网络防护、Web服务保护、暴破攻击防护、远程登录防护、恶意网址拦截。火绒企业版V2.0的网络防御功能，多层次、多方位，守护用户终端安全。 …...

编程日记 2025/9/15 14:48:22

halcon三维点云数据处理（二十五）moments_object_model_3d

目录一、moments_object_model_3d例程二、moments_object_model_3d函数三、效果图一、moments_object_model_3d例程这个例子说明了如何使用moments_object_model_3d运算符来将3D数据与x、y、z坐标轴对齐。在实际应用中，通过3D传感器获取的物体模型可能具有一个与物体主轴不…...

编程日记 2025/9/13 7:17:57

网络安全漏洞管理要求网络安全产品漏洞

一、漏洞类型缓冲区溢出、跨站脚本、DOS攻击、扫描、SQL 注入、木马后门、病毒蠕虫、web攻击、僵尸网络、跨站请求伪造、文件包含、文件读取、目录遍历攻击、敏感信息泄露、暴力破解、代码执行漏洞、命令执行、弱口令、上传漏洞利用、webshell利用、配置不当/错误、逻辑/涉及错…...

编程日记 2025/9/16 2:54:18

XML（eXtensible Markup Language）

eXtensible Markup Language（可扩展标记语言）是一种用来存储和传输数据的文本格式。具体定义 XML 可扩展标记语言，是用于标记电子文件使其具有结构性的标记语言，可以用来标记数据、定义数据类型，是一种允许用户对自…...

编程日记 2025/9/11 21:50:36

SpringBoot两种方式接入DeepSeek

方式一：基于HttpClient 步骤 1：准备工作获取 DeepSeek API 密钥：访问 DeepSeek 的开发者平台，注册并获取 API 密钥。步骤 2：引入依赖 <dependency><groupId>org.springframework.boot</groupId&g…...

编程日记 2025/9/11 20:01:50

el-date-picker 组件限制禁止选择当前时间之前的时间

页面代码 <el-date-pickerv-model"xxx.startTime"type"datetime"placeholder"请选择开始时间"value-format"YYYY-MM-DD HH:mm:ss"clearable:disabledDate"disabledDateFn":disabled-hours"disabledHours":dis…...

编程日记 2025/9/13 20:06:01

嵌入式科普(33)深度解析C语言中的const和volatile关键字

1. 关键字基础概念 const：定义"只读变量"，被修饰的变量不可被程序修改 volatile：提醒编译器该变量可能被意外修改，禁止编译器优化九、e2studio VS STM32CubeIDE之const修饰BSP函数的形参嵌入式科普(23)指向寄存器的…...

编程日记 2025/9/15 3:43:41

DIP的实际举例

SOLID原则。依赖倒置原则（DIP）的核心是高层模块不应该依赖于低层模块，二者都应该依赖于抽象（接口或抽象类） 例如，随着业务的发展，订单总金额的计算规则可能需要根据不同的客户类型或促销活动…...

编程日记 2025/9/14 5:58:54

【GESP】C++二级真题 luogu-b3955, [GESP202403 二级] 小杨的日字矩阵

GESP二级真题，多层循环、分支语句练习，难度★✮☆☆☆。题目题解详见：https://www.coderli.com/gesp-2-luogu-b3955/ 【GESP】C二级真题 luogu-b3955, [GESP202403 二级] 小杨的日字矩阵 | OneCoderGESP二级真题，多层循环、分支…...

编程日记 2025/9/14 3:04:14

python类型转换深浅拷贝

1.类型转换 1.1 int(x):转化为一个整数，只能转换由纯数字组成的字符串 float->int 浮点型强转整形会去掉小数点后面的数，只保留整数部分 a 1.2 print(type(a)) #<class float> b int(a) print(type(b)) #<class int>print(int…...

编程日记 2025/9/2 19:19:19

Kafka面试题汇总

基础篇 1、什么是 Apache Kafka？它的主要用途是什么？ 2、Kafka 中的几个核心概念是什么？请简要说明每个概念的作用。 3、Kafka 的 Producer 和 Consumer 是如何工作的？它们之间的数据传递机制是什么？ 进阶篇 1、K…...

编程日记 2025/9/11 6:40:07

window安装MySQL5.7

1、下载MySQL5.7.24 浏览器打开： https://dev.mysql.com/get/Downloads/MySQL-5.7/mysql-5.7.24-winx64.zip 2、解压缩下载下来的是一个压缩包，解压到你想放到的目录下面，我放的是“C:\MySQL” 3、配置MySQL环境变量计算机右键 - 属性 …...

编程日记 2025/9/15 6:10:58

什么是手机9008模式？如何进入9008

之前给大家分享了一些有关手机刷机的知识，今天给大家讲一讲如果刷机过程中不慎变砖应该如何应对（当然了，希望大家都不会遇到）😂😄 在给手机 Root 或刷机时，线刷 9008 指的是利用高通 9008 模式…...

编程日记 2025/9/5 22:03:32

【jira】用到几张表

jira用到的几张表测试计划，测试周期，测试用例，问题记录 1. 测试计划 # 记录表，查计划详情 SELECT ID,issuenum,SUMMARY FROM jiraissue where issuenum 22871# 测试计划下，测试周期，查测试周期id&…...

编程日记 2025/9/10 7:17:48

文件包含-session2

[题目信息]： 题目名称题目难度文件包含-session22 [题目考点]： 由于网站功能需求，会让前端用户选择要包含的文件，而开发人员又没有对要包含的文件进行安全考虑，就导致攻击者可以通过修改文件的位置来让后台执行任意…...

编程日记 2025/9/11 7:00:19

在 MySQL 的 InnoDB 存储引擎中，脏页（Dirty Page）的刷盘（Flush）时机

1. 后台线程周期性刷盘触发机制： InnoDB 的 Page Cleaner 线程会周期性地将脏页刷入磁盘，防止内存中脏页堆积。触发条件： 脏页比例阈值：当 Buffer Pool 中脏页占比超过 innodb_max_dirty_pages_pct（默认 90%&#…...

编程日记 2025/9/14 7:32:28

Vscode编辑器获取更新远程最新分支

解决：打开当前项目的终端，输入 git remote update origin --prune # 查看远程分支 git branch -r --prune --prune 参数告诉 Git 清理那些远程仓库中已经删除但本地仍然存在的跟踪分支。命令作用更新远程仓库引用： git remote update …...

编程日记 2025/9/15 11:05:17

`AdminAdminDTO` 和 `userSession` 对象中的字段对应起来的表格

以下是将更正后的表格放在最前面的回答，表格包含序号列，合并了后端 AdminAdminDTO 和前端 userSession 的所有字段，并标注对方没有的字段。token 字段值用省略号（...）表示： 序号字段名AdminAdminDTO (后端…...

编程日记 2025/9/15 10:49:37

存储引擎、索引(MySQL笔记第四期)

p.s.这是萌新自己自学总结的笔记，如果想学习得更透彻的话还是请去看大佬的讲解目录存储引擎概念InnoDB存储引擎MyISAM存储引擎Memory存储引擎存储引擎的选择索引三种索引索引分类语法(创建/查看/删除)性能分析工具SQL执行频率慢查询日志profile详情explain执行计…...

编程日记 2025/9/10 21:24:26

全面汇总windows进程通信（二）

在Windows操作系统下，实现进程间通信（IPC, Inter-Process Communication）有几种常见的方法，包括使用管道（Pipe）、共享内存（Shared Memory）、消息队列（Message Queue）、命名管道（Named Pipe）、套接字（Socket）等。本文介绍如下几种：信号量（Semaphore）和互斥量（…...

编程日记 2025/9/13 10:22:04

【大模型】蓝耘智算云平台快速部署DeepSeek R1/R3大模型详解

目录一、前言二、蓝耘智算平台介绍 2.1 蓝耘智算平台是什么 2.2 平台优势 2.3 应用场景 2.4 对DeepSeek 的支持 2.4.1 DeepSeek 简介 2.4.2 DeepSeek 优势三、蓝耘智算平台部署DeepSeek-R1操作过程 3.1 注册账号 3.1.1 余额检查 3.2 部署DeepSeek-R1 3.2.1 获取…...

编程日记 2025/9/15 0:53:06

心理咨询小程序的未来发展

还在眼巴巴看着心理咨询行业的巨大蛋糕却无从下口？今天就来聊聊心理咨询小程序的无限潜力据统计，全球超 10 亿人受精神心理问题困扰，国内心理健康问题也日益突出，心理咨询需求猛增。可传统心理咨询预约难，费用高&…...

编程日记 2025/9/10 7:12:37