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

怎样计算一个算法的复杂度?

分析一个算法主要看这个算法的执行需要多少机器资源。在各种机器资源中,时间和空间是两个最主要的方面。因此,在进行算法分析时,人们最关心的就是运行算法所要花费的时间和算法中使用的各种数据所占用的空间资源。算法所花费的时间通常称为时间复杂度,使用的空间资源称为空间复杂度。接下来学习如何计算一个算法的时间复杂度和空间复杂度。

1.时间复杂度

在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,然后分析T(n)随n的变化。

1653989744854_41.png

这样用大写的O来标记算法的时间复杂度,称之为大O(Order的简写)标记法。一般随着n的增长,T(n)也会随之增长,其中T(n
)增长最慢者就是时间性能最优的算法。

在计算时间复杂度的时候,根据T(n)与n的最高阶数关系,我们给这些算法的复杂度进行了归类,如表1所示。
1653991095252_42.png

当然还会有一些其他阶数关系,这里只是列出了几种较常见的关系。算法的执行次数可能会与规模n呈现出这些关系,那么这些关系又是如何推导出来的呢?下面给出大O阶的推导方法:

(1)用常数1取代运行中的所有加法常数。

(2)在修改后的运行次数函数中,只保留最高阶项。

(3)如果最高阶项存在,且不是1,则除去其常系数,得到的结果就是大O阶。

接下来通过分析几段程序的执行过程来推导出其时间复杂度,程序段1代码如下所示:

int a=100;              //执行一次int b=200;              //执行一次int sum=a+b;            //执行一次printf("&d\n",sum);      //执行一次

上述程序段有4行代码,每一行执行1次,加起来一共执行了4次,f(n)=4,即T(n)=O(4)。根据推导方法中的第一条,将常数项以1代替。在保留其最高阶项时,发现其没有最高阶项,因此该算法的时间复杂度为O(1),为常数阶。程序段2代码如下所示:

void func()
{int i,sum=0;                         //执行一次for (i=0;i<=100;i++){sum +=i;                              //执行n次}printf("sd\n",sum);               //执行一次
}

该程序段的执行次数为1+n+1,则f(n)=n+2,即T(n)=O(n+2)。然后将常数项以1替换,且只保留最高阶项,则得出T(n)=O(n),因此该算法的时间复杂度为O(n),为线性阶。

程序段3代码如下所示:

void func()
{int i=l;do{i*=2}while (i<n);
}

在这个程序段中,当i<n时,循环结束。如果循环了f(n)次,则2(fn)=n,即f(n)=log2n,T(n)=O(log2n)。然后消除常系数,保留最高阶项,最后得出T(n)=O(logn),为对数阶。

用大O阶来推导算法的复杂度并不难,读者在以后的学习中设计算法,就可以用此法来估测算法的优劣。

2.空间复杂度

空间复杂度是对一个算法在运行过程中所占存储空间大小的度量,一般也作为问题规模n的函数,以数量级形式给出,格式如下所示:

1653992397625_43.png

一个算法的存储量包括输入数据所占空间、程序本身所占空间和辅助变量所占空间。在对算法进行分析时,只考虑辅助变量所占空间。若所需辅助空间相对于输入数据量来说是常数,则称此算法为原地工作。若所用空间量依赖于特定的输入,则除了有特殊说明外,均按最坏情况考虑。

有时候,在写代码时可以用空间来换取时间,例如,写一个算法来判断某年是否是闰年,这样每输入一个年份都要调用算法去判断一下,在时间上就有点复杂。为了提高效率,可以用空间来换取时间,即建立一个大小合适的数据,编号从0到n,如果是闰年,则存入数据1,否则存入数据0。这样只要通过判断年份编号上存储的是0还是1就知道该年份是否是闰年了。

用空间换取时间可以将运算最小化,但这两种情况哪种更好,要结合具体情况而定。一般情况下,都是用时间复杂度来度量算法,当不加限定地使用“复杂度”这一术语时,都是指时间复杂度。

相关文章:

怎样计算一个算法的复杂度?

分析一个算法主要看这个算法的执行需要多少机器资源。在各种机器资源中&#xff0c;时间和空间是两个最主要的方面。因此&#xff0c;在进行算法分析时&#xff0c;人们最关心的就是运行算法所要花费的时间和算法中使用的各种数据所占用的空间资源。算法所花费的时间通常称为时…...

【问题记录】Ubuntu 22.04 环境下,打开 VS Code 老是访问密钥环该怎么解决?

目录 环境 问题情况 解决方法 环境 VMware Workstation 16 Pro &#xff08;版本&#xff1a;16.1.2 build-17966106&#xff09;ubuntu-22.04.2-desktop-amd64 问题情况 在Ubuntu下&#xff0c;每次运行 VS Code时&#xff0c;老是提示要输入密钥密码来解锁保存在密钥环&am…...

format格式化输出语法详解

hello&#xff0c;这里是Token_w的文章&#xff0c;主要讲解python的基础学习&#xff0c;希望对大家有所帮助 整理不易&#xff0c;感觉还不错的可以点赞收藏评论支持&#xff0c;感谢&#xff01; 使用 % 操作符对各种类型的数据进行格式化输出&#xff0c;这是早期 Python提…...

RocketMQ教程-(5)-功能特性-事务消息

事务消息为 Apache RocketMQ 中的高级特性消息&#xff0c;本文为您介绍事务消息的应用场景、功能原理、使用限制、使用方法和使用建议。 事务消息为 Apache RocketMQ 中的高级特性消息&#xff0c;本文为您介绍事务消息的应用场景、功能原理、使用限制、使用方法和使用建议。…...

HANA学习笔记

1、安装 准备安装介质&#xff0c;我这儿用的是HANA2.00.059.00&#xff0c;注意会用到三个lib包和saptune&#xff0c;提前准备好。 执行./hdblcm开启数据库安装&#xff0c;过程中会涉及到需要用户设置一些参数&#xff0c;按照自己需求设置即可。 安装完成会生成一个安装日…...

VMware虚拟机无法上网的解决办法

&#xff08;1&#xff09;1、在虚拟机右下角的网络适配器上面观察该图标是否是有绿色的灯在闪烁&#xff0c;如果网络适配器是灰色的证明虚拟机的网络没有打开&#xff0c;而是被禁用了&#xff0c;在适配器上点击鼠标右键&#xff0c;打开【设置】&#xff0c;在【已连接】、…...

PLC-Recorder的高速采集有多快?0.5ms算快吗?看控制器能力了!

大家知道&#xff0c;PLC-Recorder有一个高速采集的功能&#xff0c;基于TCP连接或UDP报文&#xff0c;速度取决于发送端的能力。对于西门子PLC&#xff0c;能做到1-2ms的采集速度&#xff0c;但是&#xff0c;我在前面的文章里提到了0.5ms的高速采集&#xff0c;哪个控制器能这…...

KMP算法总结

KMP算法总结 BF算法引导BF算法步骤&#xff08;图片演示&#xff09;代码演示 KMP算法推next数组代码演示 BF算法引导 BF算法是一个暴力的字符串匹配算法&#xff0c;时间复杂度是o&#xff08;m*n&#xff09; 假设主串和子串分别为 我们想要找到子串在主串的位置 BF算法核…...

消息中间件ActiveMQ介绍

一、消息中间件的介绍 介绍 ​ 消息队列 是指利用 高效可靠 的 消息传递机制 进行与平台无关的 数据交流&#xff0c;并基于 数据通信 来进行分布式系统的集成。 特点(作用) 应用解耦 异步通信 流量削峰 (海量)日志处理 消息通讯 …... 应用场景 根据消息队列的特点&a…...

【100天精通python】Day9:数据结构_字典、集合

目录 目录 1 字典 1.1 字典的基本操作示例 1.2 字典推导式 2 集合 2.1 集合的常用操作示例 3 列表、元组、字典、集合的区别 1 字典 在Python中&#xff0c;字典&#xff08;Dictionary&#xff09;是一种无序的数据结构&#xff0c;用于存储键值对的集合。每个…...

上海VR全景展示,快速了解VR全景拍摄

导语&#xff1a; 随着科技的不断进步&#xff0c;虚拟现实技术的应用日益广泛。在这其中&#xff0c;VR全景图片作为一种数字化助力的全景拍摄方式&#xff0c;正逐渐成为人们关注的焦点。通过数字化技术&#xff0c;VR全景图片能够以360度全方位的视角呈现真实的场景&#x…...

VScode远程不用再输入密码操作

安装插件remote development 1.先检查自己电脑上有没有生成一对公钥和私钥。&#xff08;一般会在这个目录&#xff09; 如果没有的话就自己生成一下。 打开命令行输入以下命令 ssh-keygen -t rsa2.在虚拟机中先看一下有没有公钥和私钥。如果没有的话就自己生成一下。 打开…...

MyBatis基本用法-@TableId

TableId 注解是 MyBatis Plus 框架中用于标识实体类中的主键字段的注解&#xff0c;它有一些可选的配置项。下面是详细说明&#xff1a; 首先&#xff0c;需要在项目中添加 MyBatis Plus 的依赖。可以在项目的 pom.xml 文件中添加以下代码&#xff1a; <dependency><…...

React AntDesign写一个导出数据的提示语 上面有跳转的路径,或者点击知道了,关闭该弹层

效果如下&#xff1a; 代码如下&#xff1a; ForwardDataCenterModal(_blank);export const ForwardDataCenterModal (target?: string) > {let contentBefore React.createElement(span, null, 数据正在处理中&#xff0c;请稍后前往);let contentAfter React.creat…...

小红书课程发光社群知识库,点亮哥专为超级个体设计解决方案

小红书课程点亮哥知识库 开创了学习小红书教育培训先河 针对超级个体轻创业的学习需求场景 创新推出了“知识库全新学习方式”。 一个人如何做好小红书? 超级个体轻创业,如何做好小红书? 通过打造个人IP、或者塑造老板个人品牌,来实现互联网变现,如何做好小红书? 就像挑…...

基于SpringBoot+Vue的摄影跟拍预定管理系统设计与实现(源码+lw+部署文档等)

博主介绍&#xff1a; 大家好&#xff0c;我是一名在Java圈混迹十余年的程序员&#xff0c;精通Java编程语言&#xff0c;同时也熟练掌握微信小程序、Python和Android等技术&#xff0c;能够为大家提供全方位的技术支持和交流。 我擅长在JavaWeb、SSH、SSM、SpringBoot等框架…...

HCIA 第二课总结

配置网络设备的明文密钥实验组网 实验拓扑 将一个路由器使用配置口进行连接 sys #进入系统视图模式 sysname RTA #给设备命名 user-interface console 0 #进入用户接口配置界面 authentication-mode password #配置认证模式为密钥认证 set authentication password ciphe…...

linux-------联网下载文件和配置

1.Wget Wget是一个十分常用命令行下载工具&#xff0c;多数Linux发行版本都默认包含这个工具。如果没有安装可在http://www.gnu.org/software/wget/wget.html下载最新版本&#xff0c;并使用如下命令编译安装&#xff1a; 1.#tar zxvf wget-1.9.1.tar.gz #cd wget-1.9.1 #./c…...

字典树Trie

Trie树又称字典树&#xff0c;前缀树。是一种可以高效查询前缀字符串的树&#xff0c;典型应用是用于统计&#xff0c;排序和保存大量的字符串&#xff08;但不仅限于字符串&#xff09;&#xff0c;所以经常被搜索引擎系统用于文本词频统计。 它的优点是&#xff1a;利用字符串…...

算法之桶排序算法

桶排序的基本思想是&#xff1a; 把数组 arr 划分为 n 个大小相同子区间&#xff08;桶&#xff09;&#xff0c;每个子区间各自排序&#xff0c;最 后合并 。计数排序是桶排序的一种特殊情况&#xff0c;可以把计数排序当成每个桶里只有一个元素的情况。 1.找出待排序数组中的…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

PH热榜 | 2025-06-08

1. Thiings 标语&#xff1a;一套超过1900个免费AI生成的3D图标集合 介绍&#xff1a;Thiings是一个不断扩展的免费AI生成3D图标库&#xff0c;目前已有超过1900个图标。你可以按照主题浏览&#xff0c;生成自己的图标&#xff0c;或者下载整个图标集。所有图标都可以在个人或…...