【数据结构】算法的复杂度分析:让你拥有未卜先知的能力
- 👑专栏内容:数据结构
- ⛪个人主页:子夜的星的主页
- 💕座右铭:日拱一卒,功不唐捐
文章目录
- 一、前言
- 二、时间复杂度
- 1、定义
- 2、大O的渐进表示法
- 3、常见的时间复杂度
- 三、空间复杂度
- 1、定义
- 2、常见的空间复杂度
一、前言
一个程序能用很多不同的算法来实现,那么到底那种算法是效率最高的呢?
对此我们有两种方法:
第一种是事后统计法,既在编写之后,通过计时,比较不同算法编写的程序的运行时间,以此确定算法效率的高低。但是该方法的缺陷很大,会受到测试环境、数据规模的影响。
第二种是事前分析法,即在编写之前,依据一些统计方法对算法进行粗略估算,大致的估算出该算法的时间复杂度和空间复杂度,通过对比复杂度来评判那种算法的效率更高。
可以说,学会了如何分析一个算法的复杂度,就拥有了未卜先知的能力,即在这个算法被写出来之前,就能大致评判出这个算法的好坏。
二、时间复杂度
1、定义
维基百科:在计算机科学中,算法的时间复杂度(time complexity)是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。
额…具体来举个例子吧。
void Func1(int N)
{
int count = 0;
// n*n次
for (int i = 0; i < N ; ++ i)
{for (int j = 0; j < N ; ++ j){++count;}
}
// 2*n次
for (int k = 0; k < 2 * N ; ++ k)
{++count;
}
// 10次
int M = 10;
while (M--)
{++count;
}
printf("%d\n", count);
}
这个函数一共执行的基本操作次数为:F(n)=n2+2∗n+10F(n)=n^2+2*n+10F(n)=n2+2∗n+10
但是,我们计算复杂度的时候,不一定需要计算这么精确的执行次数,我们只需要计算出大概的执行次数就行了,所以这里我们应该使用大O的渐进表示法。那么什么是大O表示法呢?
2、大O的渐进表示法
大O符号(Big O notation):是用于描述函数渐进行为(趋向于特定值或无穷大)的数学符号。
上面函数一共执行的操作次数为:F(n)=n2+2∗n+10F(n)=n^2+2*n+10F(n)=n2+2∗n+10
学过极限的都知道,当nnn趋向于无穷的时候,n2+2∗n+10n^2+2*n+10n2+2∗n+10 中的2∗n2*n2∗n和10可以忽略不记。
所以用大O的渐进表示法,上面函数的时间复杂度应该为:O(n2)O(n^2)O(n2)
这里我们可以简单的总结一下方法:
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中,只保留最高阶项。
3、嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。
4、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。
3、常见的时间复杂度
- O(1)O(1)O(1)型
一般情况下,要算法的执行时间不随问题规模 n 的增加而增大,那么就是O(1)O(1)O(1)的时间复杂度
void Func(int n)
{int count = 0;for (int k = 0; k < 100; ++ k){++count;}printf("%d\n", count);
}
以上代码看似存在循环,但是仔细看,当循环到第十次的时候,这个循环就停止了。
所以上面的时间复杂度为 O(1)O(1)O(1)
- O(logn)O(logn)O(logn)型
类似于二分查找、幂运算都是O(logn)O(logn)O(logn)的时间复杂度
void Func(int n)
{int i=1;while (i <= n) {i = i * 2;}
}
以上代码,变量 i 从 1 开始,每循环一次就乘以 2。当大于n时,循环结束。所以,假设一共循环了xxx次,那么我们就可以得到:2x=n2^x=n2x=n 即x=log2nx=log_2nx=log2n ,忽略掉底数2,则该时间复杂度为:O(logn)O(logn)O(logn)
为什么可以忽略掉底数?
高中学过的换底公式:logbn=logba∗loganlog_bn=log_ba*log_anlogbn=logba∗logan
现在假设底数不是2是3,我们可以把log3nlog_3nlog3n写成log32∗log2nlog_32*log_2nlog32∗log2n,根据前面的规矩:如果最高阶项存在且不是1,则去除与这个项目相乘的常数。 而这里的log32log_32log32是个常数,可以直接去除。所以兜兜转转,最后的时间复杂度还是O(logn)O(logn)O(logn)
- O(nlogn)O(nlogn)O(nlogn)型
void Func(int n)
{for (int i = 1; i <= n; i++){int j = 1;while (j <= n){j = j * 2;}}
}
根据上面可以知道,这个循环里面的循环的复杂度是O(logn)O(logn)O(logn),而这个循环又要执行n次,所以算下来,它的时间复杂度是O(nlogn)O(nlogn)O(nlogn)
- O(n)O(n)O(n)型
void Func(int n)
{for (int i = 1; i <= n; i++){printf("我一共执行了n次哦!");}
}
- O(n2)O(n^2)O(n2)型
循环套循环,每个循环都是n次
void Func(int n)
{for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){printf("我一共执行了n*n次哦!");}}
}
- O(m∗n)O(m*n)O(m∗n)型
void Func(int n,int m)
{for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){printf("看的出来我有那些不一样吗?");}}
}
确实还有其他很多不同的时间复杂度,比如,O(2n)、O(n!)O(2^n)、O(n!)O(2n)、O(n!)…但是这些时间复杂度都太高了,以至于高到很多计算机都承受不了,所以比较少见。
三、空间复杂度
1、定义
维基百科:在计算机科学中,一个算法或程序的空间复杂度定性地描述该算法或程序运行所需要的存储空间大小。空间复杂度是相应计算问题的输入值的长度的函数,它表示一个算法完全执行所需要的存储空间大小。和时间复杂度类似,空间复杂度通常也使用大O记号来渐进地表示例如O(n)、O(nlogn)O(n)、O(nlogn)O(n)、O(nlogn)其中n用来表示输入的长度,该值可以影响算法的空间复杂度。
就像时间复杂度的计算不考虑算法所使用的空间大小一样,空间复杂度也不考虑算法运行需要的时间长短。
注意:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
2、常见的空间复杂度
- O(1)型O(1)型O(1)型
无论 n 的值如何变化,代码在执行过程中开辟的内存空间是固定的
void Func(int n)
{int i = 0; int sum = 0;for (i = 1; i < n; i++){sum = sum + i;}
}
这段代码之开辟了sum和i两个int类型的空间,大小是固定的。
所以这段代码的空间复杂度为O(1)O(1)O(1)
- O(n)型O(n)型O(n)型
随着n的值的增大,开辟的空间也逐渐增大
long long Fac(size_t N)
{if(N == 0)return 1;return Fac(N-1)*N;
}
这段代码递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间。
所以这段代码的空间复杂度为O(N)O(N)O(N)
- O(n2)型O(n^2)型O(n2)型
int** fun(int n) {int ** s = (int **)malloc(n * sizeof(int *));while(n--)s[n] = (int *)malloc(n * sizeof(int));return s;}
此处开辟的是一个二维数组,数组有n行,每行分别有1,2,3,…n列,所以是n(n+1)/2n(n + 1)/2n(n+1)/2个元素空间,空间复杂度为n2n^2n2
相关文章:

【数据结构】算法的复杂度分析:让你拥有未卜先知的能力
👑专栏内容:数据结构⛪个人主页:子夜的星的主页💕座右铭:日拱一卒,功不唐捐 文章目录一、前言二、时间复杂度1、定义2、大O的渐进表示法3、常见的时间复杂度三、空间复杂度1、定义2、常见的空间复杂度一、前…...

Linux根文件系统移植
目录 一、根文件系统 1.1根文件系统 1.2根文件系统内容 二、根文件系统移植 2.1BusyBox 2.2BusyBox的获取 2.3BusyBox的使用 2.4make menuconfig 2.5编译和安装 2.6修改根文件系统 一、根文件系统 1.1根文件系统 根文件系统是内核启动后挂载的第一个文件系统系统引…...

Three.js 无限平面快速教程【Plane】
Three.js 提供了 Plane 概念来表示在 3d 空间中无限延伸的二维表面。 这对于光标交互很有用,因此你可能需要了解如何设置此平面、将其可视化并根据需要进行调整。 推荐:使用 NSDT场景设计器 快速搭建 3D场景。 Three.js 的 Plane 文档很好而且准确&…...

在线预览PDF文件、图片,并且预览地址不显示文件或图片的真实路径。
实现在线预览PDF文件、图片,并且预览地址不显示文件或图片的真实路径。1、vue使用blob流在线预览PDF、图片(包括jpg、png等格式)。1、按钮的方法:2、方法详细:(此方法可以在发起请求时携带token,…...

Allegro如何设置导入Subdrawing可自由选择目录操作指导
Allegro如何设置导入Subdrawing可自由选择目录操作指导 用Allgro做PCB设计的时候,导入Subdrawing是非常常用的功能,在导入Subdrawing的时候,通常需要把Subdrawing文件放在需要导入PCB的相同目录下,不能自由选择,如下图 但是Allegro是支持自由选择目录的,只需按照下方的步…...

SpirngMVC执行原理--自学版
DispatcherServlet表示前置控制器,是整个SpringMVC的控制中心,用户发出请求,DispatcherServlet接收请求并拦截请求HandlerMapper为处理器映射。DispatcherServlet调用。HandlerMapping根据请求url查找HandlerHandlerExecution表示具体的Handl…...
获取savemodel的输入输出节点
saved_model_cli show --dir savemodels --all 结果: MetaGraphDef with tag-set: ‘serve’ contains the following SignatureDefs: signature_def[‘translation_signature’]: The given SavedModel SignatureDef contains the following input(s): inputs[‘i…...

《Learning to Reconstruct Botanical Trees from Single Images》学习从单幅图像重建植物树
读书报告下载https://download.csdn.net/download/weixin_43042683/87448211论文原文https://dl.acm.org/doi/10.1145/3478513.3480525论文视频https://www.bilibili.com/video/BV1cb4y127Vp/?fromseopage&vd_source5212838c127b01db69dcc8b2d27ca5171引言植物存在在室外与…...

vant 4 正式发布,支持暗黑主题,那么是如何实现的呢
2022年10月25日首发于掘金,现在同步到公众号。11. 前言大家好,我是若川。我倾力持续组织了一年多源码共读,感兴趣的可以加我微信 lxchuan12 参与。另外,想学源码,极力推荐关注我写的专栏《学习源码整体架构系列》&…...
MySQL的复制 二
复制是MySQL的一项功能,使服务器能够将更改从一个实例恢复到另一个实例 主服务器(master)将所有数据和结构更改记录到二进制日志中。二进制日志格式是基于语句的、基于行的和混合的。 从属服务器(slave)从主服务器请求…...

秒杀项目之秒杀商品展示及商品秒杀
目录前言一、登录方式调整二、生成秒杀订单2.1 绑定秒杀商品2.2 查看秒杀商品2.3 订单秒杀2.3.1 移除seata相关(方便测压)2.3.2 生成秒杀订单2.3.3 前端页面秒杀测试注意前言 博主博客用到的资源都会同步分享到资源包中 一、登录方式调整 第1步…...

教育行业需要什么样的数字产品?
数字化转型的浪潮已经席卷了各行各业,不仅出现在互联网、电商、建筑等行业,还应用在了教育行业。数字化的教育ERP软件能够在满足学校需求的基础上,帮助学校完善各类工作流程,提高工作效率。 对于一个拥有多个校区,上万…...

Spring MVC
一、Spring MVC介绍 a. Spring MVC是一个Web框架 b. Spring MVC是基于Servlet API构成的 MVC 是 Model View Controller 的缩写。 MVC 是⼀种思想,⽽ Spring MVC 是对 MVC 思想的具体实现。 学习Spring MVC目标: a.连接功能:将用户ÿ…...

类与对象(上)
类与对象(上) 1.面向过程和面向对象初步认识 C语言是面向过程的,关注的是过程,分析出求解问题的步骤,通过函数调用逐步解决问题。 C是基于面向对象的,关注的是对象,将一件事情拆分成不同的对象,靠对象之间…...
正确安装 torch_geometric库
step1: 查看pytorchcuda 版本 torch-scatter torch-sparse torch-cluster torch-spline-conv 这些关联包要与torch版本匹配。 import torch print(torch.__version__) print(torch.cuda.is_available()) torch.version.cuda或者 pip list查看版本 step2ÿ…...

【Unity VR开发】结合VRTK4.0:自身移动(滑动)
语录: 依山傍水房树间,行也安然,住也安然; 一条耕牛半顷田,收也凭天,荒也凭天; 雨过天晴驾小船,鱼在一边,酒在一边; 夜晚妻子话灯前,今也谈谈…...

G1垃圾回收器详解
文章目录前言一、思考问题二、官方文档三、基本介绍四、G1的内存模型五、G1的标记过程六、G1的垃圾回收1、G1过程梳理2、Young GC3、Mixed GC4、Full GC七、参数介绍八、典型问题1、疏散失败(Evacuation Failure)2、大对象分配(Humongous All…...

tws耳机哪个牌子音质好?tws耳机音质排行榜
随着蓝牙耳机市场的不断发展,使用蓝牙耳机的人也逐渐增多,近年来更是超越有线耳机成为最火爆的数码产品之一。那么,tws耳机哪个牌子音质好?下面,我来给大家推荐几款音质好的tws耳机,可以当个参考。 一、南…...

TIA博途中DB数据块清零的具体方法示例
TIA博途中DB数据块清零的具体方法示例 TIA中数据块如何实现清零? 在TIA指令集内有多个移动指令可对DB块内数据进行清零处理。对于S7-1500 CPU或ET200SP CPU来说,可使用BLKMOV、FILL以及SCL的POKE_BLK指令。但是这些指令对DB块清零时,要求DB块必需为非优化DB。 对于优化的DB…...

iptables防火墙屏蔽指定ip的端口
因为需要测试客户端程序与hadoop服务器之间正常通信需要开通的端口, 所以在hadoop各服务器上使用iptables防火墙屏蔽了测试客户端程序的ip和所有端口。然后,根据报错信息提示的端口号来逐步放开直到能正常通信下载文件。 在服务器端屏蔽指定ip访问所有端口 #查看…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...

ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...

跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...

无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文通过代码驱动的方式,系统讲解PyTorch核心概念和实战技巧,涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...
前端调试HTTP状态码
1xx(信息类状态码) 这类状态码表示临时响应,需要客户端继续处理请求。 100 Continue 服务器已收到请求的初始部分,客户端应继续发送剩余部分。 2xx(成功类状态码) 表示请求已成功被服务器接收、理解并处…...

【版本控制】GitHub Desktop 入门教程与开源协作全流程解析
目录 0 引言1 GitHub Desktop 入门教程1.1 安装与基础配置1.2 核心功能使用指南仓库管理日常开发流程分支管理 2 GitHub 开源协作流程详解2.1 Fork & Pull Request 模型2.2 完整协作流程步骤步骤 1: Fork(创建个人副本)步骤 2: Clone(克隆…...