【数据结构篇】时间复杂度
一.数据结构前言
1.1 数据结构的概念
数据结构(Data Structure)是计算机存储、组织数据的⽅式,指相互之间存在⼀种或多种特定关系的数 据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤,所以我们要学各式各样的数据结构, 如:线性表、树、图、哈希等
1.2 算法
算法(Algorithm):就是定义良好的计算过程,他取⼀个或⼀组的值为输⼊,并产⽣出⼀个或⼀组值作为输出。简单来说算法就是⼀系列的计算步骤,⽤来将输⼊数据转化成输出结果
二.时间复杂度
2.1 复杂度的概念
2.2 时间复杂度的定义
在计算机科学中,算法的时间复杂度是⼀个函数式T(N),它定量描述了该算法的运⾏时间(实际上,时间复杂度的本质是,随着输入规模的不断增大,算法运行速度的变化趋势),时间复杂度是描述程序的时间效率,那么为什么不去计算程序的运行时间那?
1. 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系,⽐如同⼀个算法程序,⽤⼀个⽼编译器进⾏编译和新编译器编译,在同样机器下运⾏时间不同。
2. 同⼀个算法程序,⽤⼀个⽼低配置机器和新⾼配置机器,运⾏时间也不同。
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
为啥关注算法的最坏情况,你可以这样理解:某一天你和女朋友约好下班后去约会看晚上 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)是计算机存储、组织数据的⽅式,指相互之间存在⼀种或多种特定关系的数 据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤,所以我们要学各式各样的数据结构, 如:…...
linux 环境安装 dlib 的 gpu 版本
默认使用 pip 安装的 dlib 是不使用 gpu 的 在国内社区用百度查如何安装 gpu 版本的 dlib 感觉信息都不太对,都是说要源码编译还有点复杂 还需要自己安装 cuda 相关的包啥的,看着就头大 于是想到这个因该 conda 自己就支持了吧,然后查了一下…...

springboot集成钉钉,发送钉钉日报
目录 1.说明 2.示例 3.总结 1.说明 学习地图 - 钉钉开放平台 在钉钉开放文档中可以查看有关日志相关的api,主要用到以下几个api: ①获取模板详情 ②获取用户发送日志的概要信息 ③获取日志接收人员列表 ④创建日志 发送日志时需要根据模板规定日志…...
【机器学习】自定义数据集 使用scikit-learn中svm的包实现svm分类
一、支持向量机(support vector machines. ,SVM)概念 1. SVM 绪论 支持向量机(SVM)的核心思想是找到一个最优的超平面,将不同类别的数据点分开。SVM 的关键特点包括: ① 分类与回归: SVM 可以用于分类&a…...
快速提升网站收录:利用网站历史数据
本文转自:百万收录网 原文链接:https://www.baiwanshoulu.com/38.html 利用网站历史数据可以有效提升网站的收录速度,以下是一些具体的策略和方法: 一、理解网站历史数据的重要性 网站历史数据记录了网站过去的运营情况、用户行…...

【Git】初识Git Git基本操作详解
文章目录 学习目标Ⅰ. 初始 Git💥注意事项 Ⅱ. Git 安装Linux-centos安装Git Ⅲ. Git基本操作一、创建git本地仓库 -- git init二、配置 Git -- git config三、认识工作区、暂存区、版本库① 工作区② 暂存区③ 版本库④ 三者的关系 四、添加、提交更改、查看提交日…...

Python NumPy(11):NumPy 排序、条件筛选函数
1 NumPy 排序、条件筛选函数 NumPy 提供了多种排序的方法。 这些排序函数实现不同的排序算法,每个排序算法的特征在于执行速度,最坏情况性能,所需的工作空间和算法的稳定性。 下表显示了三种排序算法的比较。 种类速度最坏情况工作空间稳定性…...

AJAX综合案例——图书管理
黑马程序员视频地址: AJAX-Day02-10.案例_图书管理AJAX-Day02-10.案例_图书管理_总结_V1.0是黑马程序员前端AJAX入门到实战全套教程,包含学前端框架必会的(ajaxnode.jswebpackgit),一套全覆盖的第25集视频,…...

JDK自带工具解析与生产问题定位指南(一)
1. 引言 Java开发工具包(JDK)内置了强大的诊断工具集,用于监控、分析和调试Java应用程序。这些工具涵盖了从进程管理、内存分析到性能监控的各个方面。本文将介绍一些最常用的Java开发工具,包括jps、jmap、jstat、jcmd、jstack、…...

FPGA 使用 CLOCK_DEDICATED_ROUTE 约束
使用 CLOCK_DEDICATED_ROUTE 约束 CLOCK_DEDICATED_ROUTE 约束通常在从一个时钟区域中的时钟缓存驱动到另一个时钟区域中的 MMCM 或 PLL 时使 用。默认情况下, CLOCK_DEDICATED_ROUTE 约束设置为 TRUE ,并且缓存 /MMCM 或 PLL 对必须布局在相同…...
《解锁AI黑科技:数据分类聚类与可视化》
在当今数字化时代,数据如潮水般涌来,如何从海量数据中提取有价值的信息,成为了众多领域面临的关键挑战。人工智能(AI)技术的崛起,为解决这一难题提供了强大的工具。其中,能够实现数据分类与聚类…...
Java小白入门教程:Object
目录 一、定义 二、作用 三、使用场景 四、语法以及示例 1、创建Object类型的对象 2、使用 toString()方法 3、使用 equals()方法 4、使用 hashCode()方法 5、使用 getClass()方法 6、使用 clone()方法 7、使用 finalize()方法 一、定义 在Java中, object…...

记6(人工神经网络
目录 1、M-P神经元2、感知机3、Delta法则4、前馈型神经网络(Feedforward Neural Networks)5、鸢尾花数据集——单层前馈型神经网络:6、多层神经网络:增加隐含层7、实现异或运算(01、10为1,00、11为0)8、线性…...

stm32硬件实现与w25qxx通信
使用的型号为stm32f103c8t6与w25q64。 STM32CubeMX配置与引脚衔接 根据stm32f103c8t6引脚手册,采用B12-B15四个引脚与W25Q64连接,实现SPI通信。 W25Q64SCK(CLK)PB13MOSI(DI)PB15MISO(DO)PB14CS(…...

编程题-最接近的三数之和
题目: 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。 返回这三个数的和。 假定每组输入只存在恰好一个解。 解法一(排序双指针): 题目要求找…...

索引的底层数据结构、B+树的结构、为什么InnoDB使用B+树而不是B树呢
索引的底层数据结构 MySQL中常用的是Hash索引和B树索引 Hash索引:基于哈希表实现的,查找速度非常快,但是由于哈希表的特性,不支持范围查找和排序,在MySQL中支持的哈希索引是自适应的,不能手动创建 B树的…...

【工欲善其事】利用 DeepSeek 实现复杂 Git 操作:从原项目剥离出子版本树并同步到新的代码库中
文章目录 利用 DeepSeek 实现复杂 Git 操作1 背景介绍2 需求描述3 思路分析4 实现过程4.1 第一次需求确认4.2 第二次需求确认4.3 第三次需求确认4.4 V3 模型:中间结果的处理4.5 方案验证,首战告捷 5 总结复盘 利用 DeepSeek 实现复杂 Git 操作 1 背景介绍…...

网络编程套接字(中)
文章目录 🍏简单的TCP网络程序服务端创建套接字服务端绑定服务端监听服务端获取连接服务端处理请求客户端创建套接字客户端连接服务器客户端发起请求服务器测试单执行流服务器的弊端 🍐多进程版的TCP网络程序捕捉SIGCHLD信号让孙子进程提供服务 …...
前端学习-事件委托(三十)
目录 前言 课前思考 for循环注册事件 语法 事件委托 1.事件委托的好处是什么? 2.事件委托是委托给了谁,父元素还是子元素 3.如何找到真正触发的元素 示例代码 总结 前言 才子佳人,自是白衣卿相 课前思考 1.如果同时给多个元素注册事件&…...

线程池以及在QT中的接口使用
文章目录 前言线程池架构组成**一、任务队列(Task Queue)****二、工作线程组(Worker Threads)****三、管理者线程(Manager Thread)** 系统协作流程图解 一、QRunnable二、QThreadPool三、线程池的应用场景W…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...

RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...

CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...

定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...

基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...

深度学习习题2
1.如果增加神经网络的宽度,精确度会增加到一个特定阈值后,便开始降低。造成这一现象的可能原因是什么? A、即使增加卷积核的数量,只有少部分的核会被用作预测 B、当卷积核数量增加时,神经网络的预测能力会降低 C、当卷…...

佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...