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

【数据结构】算法的复杂度分析:让你拥有未卜先知的能力

在这里插入图片描述

  • 👑专栏内容:数据结构
  • ⛪个人主页:子夜的星的主页
  • 💕座右铭:日拱一卒,功不唐捐

文章目录

  • 一、前言
  • 二、时间复杂度
    • 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+2n+10
但是,我们计算复杂度的时候,不一定需要计算这么精确的执行次数,我们只需要计算出大概的执行次数就行了,所以这里我们应该使用大O的渐进表示法。那么什么是大O表示法呢?

2、大O的渐进表示法

大O符号(Big O notation):是用于描述函数渐进行为(趋向于特定值或无穷大)的数学符号。

上面函数一共执行的操作次数为:F(n)=n2+2∗n+10F(n)=n^2+2*n+10F(n)=n2+2n+10
学过极限的都知道,当nnn趋向于无穷的时候,n2+2∗n+10n^2+2*n+10n2+2n+10 中的2∗n2*n2n和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=nx=log2nx=log_2nx=log2n ,忽略掉底数2,则该时间复杂度为:O(logn)O(logn)O(logn)

在这里插入图片描述

为什么可以忽略掉底数?
高中学过的换底公式:logbn=logba∗loganlog_bn=log_ba*log_anlogbn=logbalogan
现在假设底数不是2是3,我们可以把log3nlog_3nlog3n写成log32∗log2nlog_32*log_2nlog32log2n,根据前面的规矩:如果最高阶项存在且不是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(mn)
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

在这里插入图片描述

相关文章:

【数据结构】算法的复杂度分析:让你拥有未卜先知的能力

&#x1f451;专栏内容&#xff1a;数据结构⛪个人主页&#xff1a;子夜的星的主页&#x1f495;座右铭&#xff1a;日拱一卒&#xff0c;功不唐捐 文章目录一、前言二、时间复杂度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 空间中无限延伸的二维表面。 这对于光标交互很有用&#xff0c;因此你可能需要了解如何设置此平面、将其可视化并根据需要进行调整。 推荐&#xff1a;使用 NSDT场景设计器 快速搭建 3D场景。 Three.js 的 Plane 文档很好而且准确&…...

在线预览PDF文件、图片,并且预览地址不显示文件或图片的真实路径。

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

Allegro如何设置导入Subdrawing可自由选择目录操作指导

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

SpirngMVC执行原理--自学版

DispatcherServlet表示前置控制器&#xff0c;是整个SpringMVC的控制中心&#xff0c;用户发出请求&#xff0c;DispatcherServlet接收请求并拦截请求HandlerMapper为处理器映射。DispatcherServlet调用。HandlerMapping根据请求url查找HandlerHandlerExecution表示具体的Handl…...

获取savemodel的输入输出节点

saved_model_cli show --dir savemodels --all 结果&#xff1a; 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日首发于掘金&#xff0c;现在同步到公众号。11. 前言大家好&#xff0c;我是若川。我倾力持续组织了一年多源码共读&#xff0c;感兴趣的可以加我微信 lxchuan12 参与。另外&#xff0c;想学源码&#xff0c;极力推荐关注我写的专栏《学习源码整体架构系列》&…...

MySQL的复制 二

复制是MySQL的一项功能&#xff0c;使服务器能够将更改从一个实例恢复到另一个实例 主服务器&#xff08;master&#xff09;将所有数据和结构更改记录到二进制日志中。二进制日志格式是基于语句的、基于行的和混合的。 从属服务器&#xff08;slave&#xff09;从主服务器请求…...

秒杀项目之秒杀商品展示及商品秒杀

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

教育行业需要什么样的数字产品?

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

Spring MVC

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

类与对象(上)

类与对象(上) 1.面向过程和面向对象初步认识 C语言是面向过程的&#xff0c;关注的是过程&#xff0c;分析出求解问题的步骤&#xff0c;通过函数调用逐步解决问题。 C是基于面向对象的&#xff0c;关注的是对象&#xff0c;将一件事情拆分成不同的对象&#xff0c;靠对象之间…...

正确安装 torch_geometric库

step1&#xff1a; 查看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&#xff…...

【Unity VR开发】结合VRTK4.0:自身移动(滑动)

语录&#xff1a; 依山傍水房树间&#xff0c;行也安然&#xff0c;住也安然&#xff1b; 一条耕牛半顷田&#xff0c;收也凭天&#xff0c;荒也凭天&#xff1b; 雨过天晴驾小船&#xff0c;鱼在一边&#xff0c;酒在一边&#xff1b; 夜晚妻子话灯前&#xff0c;今也谈谈…...

G1垃圾回收器详解

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

tws耳机哪个牌子音质好?tws耳机音质排行榜

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

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和所有端口。然后&#xff0c;根据报错信息提示的端口号来逐步放开直到能正常通信下载文件。 在服务器端屏蔽指定ip访问所有端口 #查看…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...