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

【数据结构篇】时间复杂度

article 2026/5/9 9:42:48

一.数据结构前言

 1.1 数据结构的概念

     数据结构(Data Structure)是计算机存储、组织数据的⽅式，指相互之间存在⼀种或多种特定关系的数 据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤，所以我们要学各式各样的数据结构， 如：线性表、树、图、哈希等

1.2 算法

    算法(Algorithm):就是定义良好的计算过程，他取⼀个或⼀组的值为输⼊，并产⽣出⼀个或⼀组值作为输出。简单来说算法就是⼀系列的计算步骤，⽤来将输⼊数据转化成输出结果

二.时间复杂度

2.1 复杂度的概念

    算法在编写成可执⾏程序后，运⾏时需要耗费时间资源和空间(内存)资源 。因此衡量⼀个算法的好 坏，⼀般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度
    时间复杂度主要衡量 ⼀个算法的运⾏快慢 ，⽽空间复杂度主要衡量 ⼀个算法运⾏所需要的额外空 间 。在计算机发展的早期，计算机的存储容量很⼩。所以对空间复杂度非常在乎。但是经过计算机⾏业的迅速发展，计算机的存储容量已经达到了很⾼的程度。所以我们如今已经不需要再特别关注⼀个算法 的空间复杂度

2.2 时间复杂度的定义

    在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运⾏时间（实际上，时间复杂度的本质是，随着输入规模的不断增大，算法运行速度的变化趋势），时间复杂度是描述程序的时间效率，那么为什么不去计算程序的运行时间那？

    1. 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系，⽐如同⼀个算法程序，⽤⼀个⽼编译器进⾏编译和新编译器编译，在同样机器下运⾏时间不同。

    2. 同⼀个算法程序，⽤⼀个⽼低配置机器和新⾼配置机器，运⾏时间也不同。

    3. 并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估

3.3 大O渐进表示法（计算的）

    那么，函数式 T (N) 到底是什么呢？因为算法的运行时间和基本语句执行次数成正比，精确计算执行次数很麻烦，且不同程序代码编译出的指令条数不同，精确计算意义不大，所以我们引入大 O 渐进法，它会去掉影响较小的项。下面具体描述大 O 渐进表示法的计算过程：

 我在简略总结一下：

    常数归一：将运行时间中的加法常数用 1 取代。

    保留高阶：仅保留运行次数函数中的最高阶项。

    去除系数：若最高阶项系数不为 1，去除该系数。

三.时间复杂度计算案例

3.1 示例1

    T(N) = M+N

    由于题目并没有说明M和N的具体大小，所以我们不能去掉其中的任意一项

    时间复杂度O(M+N)

3.2 示例2

    T(N) =  2*N + 10

    先将 +10 变成 +1，由于 +10 为低阶项，去掉 +10 ，高阶项的系数不是1，将系数变为1

    时间复杂度：O(N)    

    看到这我估计有人会想，为啥要去掉系数那，×2不是变化挺大的吗？那你想一想，如果输入规模趋于无穷大，那么给他×多少不是一样的吗

3.3 示例3

    T(n) = 100  

    如果算法的基本操作执行次数是一个与输入规模无关的常数，那么其时间复杂度记为 O(1)

    时间复杂度：O（1）（表示算法的基本执行次数和输入规模无关）

3.4 示例4

（1）若要查找的字符在字符串第⼀个位置，则：
                 T (N) = 1
（2）若要查找的字符在字符串最后的⼀个位置， 则：
                 T (N) = N
（3）若要查找的字符在字符串中间位置，则：
                 T (N) = 2 / N
  因此：strchr的时间复杂度分为：
  最好情况： O ( 1 )
  最坏情况： O ( N )
  平均情况： O ( N / 2 )

为啥关注算法的最坏情况，你可以这样理解：某一天你和女朋友约好下班后去约会看晚上 20:00 的电影，但是你手头有一项工作要完成，这项工作的任务量和难度是不确定的，所以你也不知道具体几点能结束工作出发去赴约。

现在你有三个时间点可以告诉她你大概能结束工作出发，分别是 17:00、18:00、19:00。考虑到工作可能出现各种意外状况，比如遇到复杂问题需要花费更多时间解决、中途可能有新的任务插入等，为了避免让女朋友等待，保证不会耽误看电影，你肯定会选择告诉她最晚的那个时间点 19:00。

这就如同在算法中，最坏情况代表着在任意输入规模下，算法运行的最大次数（上界）。我们关注最坏情况，是因为它能让我们在设计和评估算法时，知晓算法在最糟糕场景下的性能表现，确保算法在任何情况下都能满足一定的性能要求，就像告诉女朋友最晚时间能保证约会按时进行一样

3.5 示例5

若数组有序，只需要遍历一遍数组，所以他的时间复杂度是：O(N)

若数组有序且是降序，那么他要比较n-1趟，第一次比较n-1次 第二次比较n-2次 以此类推 到1次

所以他是一个等差数列，用等差数列求和公式计算是 :

 首项是1        尾项是n-1       公差是1        一共有n-1项

 用大O计算法进行表示：O（N^2）

3.6 示例6

       

3.7 示例7

 

 我看过不少面经都对时间复杂度的计算进行了考察，这没有捷径，多练，多算，加油吧！！！

    相关文章：

    【数据结构篇】时间复杂度

    一.数据结构前言 1.1 数据结构的概念 数据结构(Data Structure)是计算机存储、组织数据的⽅式，指相互之间存在⼀种或多种特定关系的数 据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤，所以我们要学各式各样的数据结构， 如&#xff1a…...

    编程日记 2026/4/28 23:00:44

    网站快速收录：如何优化网站头部与底部信息？

    本文转自：百万收录网 原文链接：https://www.baiwanshoulu.com/46.html 为了加快网站的收录速度，优化网站头部与底部信息是关键一环。以下是一些具体的优化建议： 网站头部信息优化 标题标签（TitleTag）优化…...

    编程日记 2026/5/4 1:36:59

    【数据结构】_链表经典算法OJ（力扣/牛客第二弹）

    目录 1. 题目1：返回倒数第k个节点 1.1 题目链接及描述 1.2 解题思路 1.3 程序 2. 题目2：链表的回文结构 2.1 题目链接及描述 2.2 解题思路 2.3 程序 1. 题目1：返回倒数第k个节点 1.1 题目链接及描述 题目链接： 面试题 …...

    编程日记 2026/4/28 23:00:49

    深度学习之“缺失数据处理”

    缺失值检测 缺失数据就是我们没有的数据。如果数据集是由向量表示的特征组成，那么缺失值可能表现为某些样本的一个或多个特征因为某些原因而没有测量的值。通常情况下，缺失值由特殊的编码方式。如果正常值都是正数，那么缺失值可能被标记为-1…...

    编程日记 2026/5/7 15:23:22

    C#面试常考随笔8：using关键字有哪些用法？

    1. using 指令：引入命名空间 最常用的用法。通过using 命名空间名字，可以在程序中直接使用该命名空间中的类型，而无需指定类型的完整命名空间路径。例如： using System; using System.Collections.Generic; class Program {sta…...

    编程日记 2026/2/19 21:13:54

    Writing an Efficient Vulkan Renderer

    本文出自GPU Zen 2。 Vulkan 是一个新的显式跨平台图形 API。它引入了许多新概念，即使是经验丰富的图形程序员也可能不熟悉。Vulkan 的主要目标是性能——然而，获得良好的性能需要深入了解这些概念及其高效应用方法，以及特定驱动程序实现的实…...

    编程日记 2026/5/9 2:29:17

    解决Django非ORM模型提示初始化request问题

    提问 Django在DRF时候自定义显示一些非model的字段提示TypeError: Field.__init__() got an unexpected keyword argument request 解答1 错误提示 TypeError: Field.__init__() got an unexpected keyword argument request 显示在创建序列化器实例时，传递了一个…...

    编程日记 2026/2/24 3:36:41

    MYSQL--一条SQL执行的流程,分析MYSQL的架构

    文章目录 第一步建立连接第二部解析 SQL第三步执行 sql预处理优化阶段执行阶段索引下推 执行一条select 语句中间会发生什么？ 这个是对 mysql 架构的深入理解。 select * from product where id 1;对于mysql的架构分层: mysql 架构分成了 Server 层和存储引擎层&a…...

    编程日记 2026/5/7 7:08:24

    C++解决输入空格字符串的三种方法

    一.gets和fgets char * gets ( char * str ); char * fgets ( char * str, int num, FILE * stream ); 1. gets 是从第⼀个字符开始读取，⼀直读取到 \n 停⽌，但是不会读取 \n ，也就是读取到的内容 中没有包含 \n ,但是会在读取到的内…...

    编程日记 2026/5/5 2:24:45

    多模态论文笔记——NaViT

    大家好，这里是好评笔记，公主号：Goodnote，专栏文章私信限时Free。本文详细解读多模态论文NaViT（Native Resolution ViT），将来自不同图像的多个patches打包成一个单一序列——称为Patch n’ Pack—…...

    编程日记 2026/5/7 8:16:16

    云中漫步：精工细作铸就免费公益刷步平台

    云中漫步，历经三年深度研发与优化，平台以高稳定性、零成本及公益属性为核心特色，依托前沿技术手段与多重安全防护机制，确保用户步数数据的精准修改与隐私安全。我们致力于提供无缝流畅的用户体验，让每一次步数更新都轻…...

    编程日记 2026/5/5 1:28:17

    neo4j入门

    文章目录 neo4j版本说明部署安装Mac部署docker部署 neo4j web工具使用数据结构图数据库VS关系数据库 neo4j neo4j官网Neo4j是用ava实现的开源NoSQL图数据库。Neo4作为图数据库中的代表产品，已经在众多的行业项目中进行了应用，如：网络管理&am…...

    编程日记 2026/4/29 18:41:26

    Leetcode::81. 搜索旋转排序数组 II

    81. 搜索旋转排序数组 II 已知存在一个按非降序排列的整数数组 nums &#xff0c;数组中的值不必互不相同。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转 &#xff0c;使数组变为 [nums[k], nu…...

    编程日记 2026/2/21 22:07:50

    【ts + java】古玩系统开发总结

    src别名的配置 开发中文件和文件的关系会比较复杂&#xff0c;我们需要给src文件夹一个别名吧 vite.config.js import { defineConfig } from vite import vue from vitejs/plugin-vue import path from path// https://vitejs.dev/config/ export default defineConfig({pl…...

    编程日记 2026/4/28 23:00:47

    【自学笔记】Web前端的重点知识点-持续更新

    提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 Web前端知识点一、HTML基础二、CSS样式三、JavaScript基础四、前端框架与库五、前端工具与构建六、前端性能优化七、响应式设计与适配八、前端安全 总结 Web前端知识…...

    编程日记 2026/5/3 13:59:57

    【Docker】快速部署 Nacos 注册中心

    【Docker】快速部署 Nacos 注册中心 引言 Nacos 注册中心是一个用于服务发现和配置管理的开源项目。提供了动态服务发现、服务健康检查、动态配置管理和服务管理等功能&#xff0c;帮助开发者更轻松地构建微服务架构。 仓库地址 https://github.com/alibaba/nacos 步骤 拉取…...

    编程日记 2026/4/28 23:00:44

    SpringCloud篇 微服务架构

    1. 工程架构介绍 1.1 两种工程架构模型的特征 1.1.1 单体架构 上面这张图展示了单体架构&#xff08;Monolithic Architecture&#xff09;的基本组成和工作原理。单体架构是一种传统的软件架构模式&#xff0c;其中所有的功能都被打包在一个单一的、紧密耦合的应用程序中。 …...

    编程日记 2026/5/2 17:53:09

    tf.Keras (tf-1.15)使用记录4-model.fit方法及其callbacks参数

    model.fit() 方法是 TensorFlow Keras 中用于训练模型的核心方法。 其中里面的callbacks参数是实现模型保存、监控、以及和tensorboard联动的重要API 1 model.fit() 方法的参数及使用 必需参数 x: 训练数据的输入。可以是 NumPy 数组、TensorFlow tf.data.Dataset、Python 生…...

    编程日记 2026/5/5 9:05:09

    Easy系列PLC尺寸测量功能块ST代码(激光微距仪应用)

    激光微距仪可以测量短距离内的产品尺寸，产品规格书的测量 精度可以到0.001mm。具体需要看不同的型号。 1、激光微距仪 2、尺寸测量应用 下面我们以测量高度为例子，设计一个高度测量功能块，同时给出测量数据和合格不合格指标。 3、高度测量功能块 4、复位完成信号 5、功能…...

    编程日记 2026/5/6 2:36:24

    996引擎 -地图-添加安全区

    996引擎 -地图-添加安全区 文件位置配置 cfg_startpoint.xls特效效果1345参考资料文件位置 文件位置服务端D:\996M2-lua\MirServer-lua\Mir200客户端D:\996M2-lua\996M2_debug\dev配置 cfg_startpoint.xls 服务端\Mir200\Envir\DATA\cfg_startpoint.xls 填歪了也有可能只画一…...

    编程日记 2026/5/2 15:24:18

    Node.js 全局对象

    Node.js 全局对象 引言 在Node.js中，全局对象是JavaScript环境中的一部分，它提供了对Node.js运行时环境的访问。全局对象在Node.js中扮演着重要的角色，它使得开发者能够访问和操作Node.js的许多核心功能。本文将详细介绍Node.js的全局对象，包括其特点、常用方法和应用场景…...

    编程日记 2026/4/14 2:33:40

    [Collection与数据结构] B树与B+树

    &#x1f338;个人主页:https://blog.csdn.net/2301_80050796?spm1000.2115.3001.5343 &#x1f3f5;️热门专栏: &#x1f9ca; Java基本语法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12615970.html?spm1001.2014.3001.5482 &#x1f355; Collection与…...

    编程日记 2026/5/2 15:59:40

    redex快速体验

    第一步&#xff1a; 2.回调函数在每次state发生变化时候自动执行...

    编程日记 2026/5/7 4:12:22

    【VM】VirtualBox安装CentOS8虚拟机

    阅读本文前&#xff0c;请先根据 VirtualBox软件安装教程 安装VirtualBox虚拟机软件。 1. 下载centos8系统iso镜像 可以去两个地方下载&#xff0c;推荐跟随本文的操作用阿里云的镜像 centos官网&#xff1a;https://www.centos.org/download/阿里云镜像&#xff1a;http://…...

    编程日记 2026/5/5 1:36:31

    电子电气架构 --- 汽车电子拓扑架构的演进过程

    我是穿拖鞋的汉子&#xff0c;魔都中坚持长期主义的汽车电子工程师。 老规矩&#xff0c;分享一段喜欢的文字&#xff0c;避免自己成为高知识低文化的工程师&#xff1a; 简单&#xff0c;单纯&#xff0c;喜欢独处&#xff0c;独来独往&#xff0c;不易合同频过着接地气的生活…...

    编程日记 2026/5/6 11:11:19

    自动驾驶---苏箐对智驾产品的思考

    1 前言 对于更高级别的自动驾驶&#xff0c;很多人都有不同的思考&#xff0c;方案也好&#xff0c;产品也罢。最近在圈内一位知名的自动驾驶专家苏箐发表了他自己对于自动驾驶未来的思考。 苏箐是地平线的副总裁兼首席架构师&#xff0c;同时也是高阶智能驾驶解决方案SuperDri…...

    编程日记 2026/5/5 2:46:34

    手写call函数、手写apply函数、手写bind函数

    文章目录 1 手写call函数2 手写apply函数3 手写bind函数 1 手写call函数 call函数的实现步骤&#xff1a; 判断调用对象是否为函数。判断传入上下文对象是否存在&#xff0c;如果不存在&#xff0c;则设置为window。处理传入的参数&#xff0c;截取第一个参数后的所有参数。将…...

    编程日记 2026/3/10 18:59:04

    Python | Pytorch | Tensor知识点总结

    如是我闻&#xff1a; Tensor 是我们接触Pytorch了解到的第一个概念&#xff0c;这里是一个关于 PyTorch Tensor 主题的知识点总结&#xff0c;涵盖了 Tensor 的基本概念、创建方式、运算操作、梯度计算和 GPU 加速等内容。 1. Tensor 基本概念 Tensor 是 PyTorch 的核心数据结…...

    编程日记 2026/4/19 1:18:01

    90，【6】攻防世界 WEB Web_php_unserialize

    进入靶场 进入靶场 <?php // 定义一个名为 Demo 的类 class Demo { // 定义一个私有属性 $file&#xff0c;默认值为 index.phpprivate $file index.php;// 构造函数&#xff0c;当创建类的实例时会自动调用// 接收一个参数 $file&#xff0c;用于初始化对象的 $file 属…...

    编程日记 2026/5/3 17:30:33

    快速提升网站收录：如何设置网站标签？

    本文转自&#xff1a;百万收录网 原文链接&#xff1a;https://www.baiwanshoulu.com/45.html 为了快速提升网站的收录&#xff0c;合理设置网站标签是至关重要的。网站标签主要包括标题标签&#xff08;TitleTag&#xff09;、描述标签&#xff08;DescriptionTag&#xff09…...

    编程日记 2026/5/4 20:35:58