【数据结构篇】时间复杂度
一.数据结构前言
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…...

ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...

Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

c++第七天 继承与派生2
这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分:派生类构造函数与析构函数 当创建一个派生类对象时,基类成员是如何初始化的? 1.当派生类对象创建的时候,基类成员的初始化顺序 …...

【LeetCode】算法详解#6 ---除自身以外数组的乘积
1.题目介绍 给定一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O…...

Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...

保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!
目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...

第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10pip3.10) 一:前言二:安装编译依赖二:安装Python3.10三:安装PIP3.10四:安装Paddlepaddle基础框架4.1…...

Mysql故障排插与环境优化
前置知识点 最上层是一些客户端和连接服务,包含本 sock 通信和大多数jiyukehuduan/服务端工具实现的TCP/IP通信。主要完成一些简介处理、授权认证、及相关的安全方案等。在该层上引入了线程池的概念,为通过安全认证接入的客户端提供线程。同样在该层上可…...
Java并发编程实战 Day 11:并发设计模式
【Java并发编程实战 Day 11】并发设计模式 开篇 这是"Java并发编程实战"系列的第11天,今天我们聚焦于并发设计模式。并发设计模式是解决多线程环境下常见问题的经典解决方案,它们不仅提供了优雅的设计思路,还能显著提升系统的性能…...