数据结构:时间复杂度/空间复杂度

     

目录

一、时间复杂度

定义

常见的时间复杂度

如何计算时间复杂度

计算方法

三、实例分析

二、空间复杂度

定义

重要性

常见的空间复杂度

二、空间复杂度

定义

重要性

常见的空间复杂度

计算方法

三、实例分析

大O的渐进表示法

最好情况(Best Case)6:00

平均情况(Average Case)6:10

最坏情况(Worst Case)6:20

例1:

例2:

例3:

例4

例5


   在计算机科学和算法分析中,时间复杂度和空间复杂度是评估算法效率的两个关键指标。它们帮助我们理解算法在处理数据时所需资源的多少,从而指导我们做出更优的选择。本文将深入浅出地介绍这两个概念,并通过实例加以说明。说白了你在工作当中要让代码的效率变得更好,就需要注意

一、时间复杂度

定义

时间复杂度,简而言之,是指执行算法所需要的计算工作量随着问题规模(通常是输入数据的大小)增长的变化趋势。它关注的是算法运行时间与输入数据规模之间的关系,通常用大O符号表示(O(n)),忽略掉常数项、低阶项以及最高阶的系数。

常见的时间复杂度

  1. O(1) - 常数时间复杂度:算法的执行时间不随输入数据规模变化,如数组访问某个元素。
  2. O(log n) - 对数时间复杂度:二分查找就是一个典型的例子,每一步都将问题规模减半。
  3. O(n) - 线性时间复杂度:遍历数组或列表中的每个元素。
  4. O(n log n) - 线性对数时间复杂度:快速排序、归并排序等高效排序算法。
  5. O(n^2) - 平方时间复杂度:冒泡排序、选择排序等简单排序算法。
  6. O(n^3)O(2^n)O(n!) - 随着问题规模的增长,所需时间急剧增加,分别对应立方、指数、阶乘复杂度。

如何计算时间复杂度

计算方法

空间复杂度的计算方法与时间复杂度相似,也是关注随着问题规模增长,算法所需最大额外空间的变化趋势。

三、实例分析

上面的这些都不能让大家看出复杂度

这里主要举时间复杂度例子

实例1

实例2

实例3

实例4

实例5

  • 找出基本操作:首先确定算法中的基本操作,即执行次数最多的操作。
  • 确定问题规模:用n表示输入数据的大小。
  • 计算增长数量级:分析基本操作的执行次数与n的关系,忽略低阶项和系数,只保留最高阶项。
  • 二、空间复杂度

    定义

    空间复杂度衡量的是算法在运行过程中临时占用存储空间大小的变化情况,同样与问题规模有关。这包括了算法本身占用的空间以及算法运行过程中需要的额外空间。

    重要性

    在内存资源有限的环境下,特别是嵌入式系统或大规模数据处理中,空间复杂度是一个不可忽视的因素。高效利用内存可以提升系统性能,减少资源消耗。

    常见的空间复杂度

  • O(1):算法使用的额外空间不随输入数据规模改变,如原地排序算法。
  • O(n):额外空间正比于输入数据规模,如某些动态规划问题中需要的数组。
  • O(n^2):随着输入规模增大,所需空间平方增长,例如某些矩阵运算。

二、空间复杂度

定义

空间复杂度衡量的是算法在运行过程中临时占用存储空间大小的变化情况,同样与问题规模有关。这包括了算法本身占用的空间以及算法运行过程中需要的额外空间。

重要性

在内存资源有限的环境下,特别是嵌入式系统或大规模数据处理中,空间复杂度是一个不可忽视的因素。高效利用内存可以提升系统性能,减少资源消耗。

常见的空间复杂度

  • O(1):算法使用的额外空间不随输入数据规模改变,如原地排序算法。
  • O(n):额外空间正比于输入数据规模,如某些动态规划问题中需要的数组。
  • O(n^2):随着输入规模增大,所需空间平方增长,例如某些矩阵运算。

计算方法

空间复杂度的计算方法与时间复杂度相似,也是关注随着问题规模增长,算法所需最大额外空间的变化趋势。

三、实例分析

//请计算一下Func1中++count语句总共执行了多少次?
void Funcl(int N)
{
int count =0;
for(int i=0;i<N;++i)
{for(int j=0;j<N;++j){++count;}
}for (int k=0;k<2*N;++k){++count;}int M=10;
while(M--)
{++count;
}printf("%d\n",count);
}

这个代码的时间复杂度是多少嘞?

这边我们看一下我们有一个嵌套循环,外循环执行一次,内循环就要执行N次,所以我们得出了N的平方,再看我们的第二个循环循环的是2*N,下面的while循环10次,由这些依据我们得到一个公式

F(N) = N^2+2*N+10

我们计算时间复杂度有一个大O的渐进表示法来表示,来看个例子:

               精确值                      估算值

N=10      F(N)=130                   100

N=100    F(N)=10210               10000

N=1000  F(N)=1002010           1000000

 实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这 里我们使用大O的渐进表示法。

大O的渐进表示法

由于我们得计算机,运算很快

这个也要看我们的电脑配置

大O渐进表示法,简单来说,是一种衡量算法随着输入数据量增加时,其执行时间或所需资源如何增长的方法。它不关注具体的计算时间,而是关心增长的趋势和速度。

想象一下,你正在研究两个不同的背包打包算法。一个算法检查每件物品与背包内所有可能位置的组合(这可能会导致检查的数量呈指数级增长),而另一个算法则采用更聪明的方法,比如按物品价值和重量预先排序(这样可能最多只需检查每个物品一次)。为了比较这两个算法哪个在面对大量物品时表现更好,我们就需要用到大O表示法。

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数。

举个例子吧,假如你今天在看我的博客,但是你女朋友给你发消息说晚上出来玩,然后叫你定个时间,于是就出来三种情况

最好情况(Best Case)6:00
  • 描述:博客非常短,你几乎立刻就读完了。
  • 算法复杂度:在这种情况下,无论博客多长,你都能瞬间完成阅读并回复消息。这类似于一个常数时间操作,可以用O(1)表示,意味着操作时间不随输入大小变化。
平均情况(Average Case)6:10
  • 描述:博客的长度中等,既不太长也不太短,你需要花一些合理的时间阅读。
  • 算法复杂度:如果大多数时候博客的长度在一个可预期的范围内,且阅读时间与博客长度成正比,那么这可以视为线性时间复杂度,即O(n),其中n代表博客的字数。这意味着阅读时间随博客长度线性增长。
最坏情况(Worst Case)6:20
  • 描述:博客异常长,需要很长时间才能读完。
  • 算法复杂度:在这种情况下,如果阅读时间直接与博客的长度成正比(忽略可能的加载时间等其他因素),复杂度仍然是O(n)。但如果考虑到随着博客越来越长,你的注意力可能会分散,导致阅读每个额外字词所需时间轻微增加,这种情况下虽然仍是线性关系,但强调了在极端条件下的体验。

这三种情况,你选哪一个最保险?才能不让你的女朋友等你嘞?所以我们有时候不要把预期拉的太高,做事要想好最坏的打算

通过这些我们回到上面的代码我们就可以得出他的时间复杂度是O(n^2),因为他影响最大,也是最坏的那个

接下来我们看几个例子来练习一下

例1:
//计算Func3的时间复杂度?
void Func3(int N,int M)
{
int count =0;
for (int k=0;k<M;++k)
{
++count;
}
}
for (int k=0;k<N;++k)
{
++count;
}
printf("%d\n",count);

F(M+N)

这里没有明确说明N远大于M还是M远大于N,都没有明确说明,那就是对执行次数影响是同等的,谁都不能舍去,所以结果为O(N)=N+M。

例2:
//计算Func4的时间复杂度?
void Func4(int N)
{
int count =0;
for (int k =0;k<100;++k)
{
++count;
}
printf("%d\n",count);
}

大家看一下这个时间复杂度是多少?

这个循环一共执行了100次,这个100是一个常数,所以我们这里的空间复杂度是O(1)(就是我们可以看出来的次数,执行次数不是未知数

例3:

例4

这个就要根据逻辑理解这个O(2^N)

例5

空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟实践复杂度类似,也使用大O渐进表示法。

注意:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因 此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/318617.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Java进阶-JINQ详解与使用

本文详细介绍了JINQ&#xff08;Java Integrated Query&#xff09;&#xff0c;一种强化Java中数据查询能力的库&#xff0c;提供类SQL的查询语法和类型安全的操作。文章首先解释了JINQ的基本功能和应用&#xff0c;随后通过具体示例展示了如何使用JINQ进行数据过滤、投影、连…

【竞技宝】意甲:退出齐尔克泽争夺战!国米免签伊朗神锋!

博洛尼亚中锋齐尔克泽成为了意甲当红炸子鸡,不少豪门球队都希望可以签下他,目前对球员有意向的俱乐部包括AC米兰、尤文图斯、阿森纳、国际米兰和曼联,看到自家球员如此有市场,博洛尼亚方面咬死5000万欧元的价格不松口,想要得到他必须要拿出真金白银。不过意甲霸主国际米兰率先退…

408数据结构-二叉树的概念、性质与存储结构 自学知识点整理

前置知识&#xff1a;树的基本概念与性质 二叉树的定义 二叉树是一种特殊的树形结构&#xff0c;其特点是每个结点至多只有两棵子树&#xff08;即二叉树中不存在度大于 2 2 2的结点&#xff09;&#xff0c;并且二叉树是有序树&#xff0c;左右子树不能互换。 与树类似&#…

笔试强训week3

day1 Q1 难度⭐ 牛牛冲钻五_牛客小白月赛38 (nowcoder.com) 题目&#xff1a; 牛牛最近在玩炉石传说&#xff0c;这是一款一对一对战的卡牌游戏&#xff0c;牛牛打算努力冲上钻五分段&#xff0c;获得丰厚的天梯奖励。 炉石传说的段位可以用星数来表示&#xff0c;具体规则…

【linuxC语言】空洞文件

文章目录 前言一、空洞文件1.1 空洞文件的介绍1.2 用途 二、示例代码总结 前言 在 Linux 系统编程中&#xff0c;空洞文件是一种特殊类型的文件&#xff0c;它包含了逻辑上的空洞&#xff0c;也就是说文件中的某些部分并没有实际写入数据。尽管文件在逻辑上可能非常大&#xf…

webpack 常用插件

clean-webpack-plugin 这个插件的主要作用是清除构建目录中的旧文件&#xff0c;以确保每次构建时都能得到一个干净的环境。 var { CleanWebpackPlugin } require("clean-webpack-plugin") const path require("path");module.exports {mode: "de…

Springboot+mybatis升级版(Postman测试)

一、项目结构 1.导入依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apach…

12_Scala_package

文章目录 Scaal面向对象编程1.回顾Java2.package可以多次声明3.设置作用域&#xff0c;设置上下级4.包可以当作对象使用5.import6.Scala用_取代Java *7.导入多个包8.屏蔽类9.类起别名10.import的规则11.有些包无需导入 Scaal面向对象编程 Scala是一门完全面向对象语言&#xf…

Linux的权限管理

文章目录 文件权限文件类型文件访问者的分类文件权限的类型 文件访问权限的设置目录的权限 文件权限 对于每个LInux文件&#xff0c;如果用ll指令查看的话&#xff0c;可以发现每个文件前面都有一串类似的字符&#xff1a; 这里总共有十个字符&#xff0c;其中第一个字符表示…

QT httpServer多线程后台服务器的例子实现

1.需求 1.1 用户需要其他平台&#xff08;web端&#xff09;调用Qt平台的接口&#xff0c;获取想要的数据并实时显示在网页里&#xff0c;比如实时的温湿度&#xff0c;用户数据等 1.2 用户需要在其他平台&#xff08;web端&#xff09;调用Qt平台的接口&#xff0c;下发数据…

贝叶斯统计实战:Python引领的现代数据分析之旅

贝叶斯统计这个名字取自长老会牧师兼业余数学家托马斯贝叶斯(Thomas Bayes&#xff0c;1702—1761)&#xff0c;他最先推导出了贝叶斯定理&#xff0c;该定理于其逝世后的1763年发表。但真正开发贝叶斯方法的第一人是Pierre-Simon Laplace(1749—1827)&#xff0c;因此将其称为…

Copilot Venture Studio創始合伙人楊林苑確認出席“邊緣智能2024 - AI開發者峰會”

隨著AI技術的迅猛發展&#xff0c;全球正逐步進入邊緣計算智能化與分布式AI深度融合的新時代&#xff0c;共同書寫著分布式智能創新應用的壯麗篇章。邊緣智能&#xff0c;作為融合邊緣計算和智能技術的新興領域&#xff0c;正逐漸成為推動AI發展的關鍵力量。借助分布式和去中心…

Messari 报告摘要 :Covalent Network(CQT)2024 年第一季度表现

摘要&#xff1a; 尽管 CQT 代币流通供应量增加了 20%&#xff08;新增 1.04 亿枚 CQT&#xff09;&#xff0c;但 CQT 的质押百分比仅从 2023 年第一季度的 22% 增长到了 2024 年第一季度的 29%。 CQT 的市值季度环比增长了 28%&#xff0c;多次达到 2.75 亿美元&#xff0c…

分享三款可以给pdf做批注的软件

PDF文件不像Word一样可以直接编辑更改&#xff0c;想要在PDF文件上进行编辑批注需要用到一些专业的软件&#xff0c;我自己常用的有三款&#xff0c;全都是官方专业正版的软件&#xff0c;功能丰富强大&#xff0c;使用起来非常方便&#xff01; 1.edge浏览器 这个浏览器不仅可…

van-cascader(vant2)异步加载的bug

问题描述&#xff1a;由于一次性返回所有的级联数据的话&#xff0c;数据量太大&#xff0c;接口响应时间太久&#xff0c;因此采用了异步加载的方案&#xff0c;看了vant的官方示例代码&#xff0c;照着改了下&#xff0c;很轻松地实现了功能。正当我感叹世界如此美好的时候&a…

2.2 Java全栈开发前端+后端(全栈工程师进阶之路)-前端框架VUE3-基础-Vue基本语法

文本渲染指令 文本渲染指令-v-html与v-text Vue使用了基于HTML的模板语法&#xff0c;允许开发者声明式地将DOM绑定至底层Vue实例的数据。所有Vue的模板都是 合法的HTML&#xff0c;所以能被遵循规范的浏览器和HTML解析器解析。 在前面&#xff0c;我们一直使用的是字符串插…

Flutter - 折叠面板

demo 地址: https://github.com/iotjin/jh_flutter_demo 代码不定时更新&#xff0c;请前往github查看最新代码 flutter 自定义折叠组件 支持三种类型和两种展示效果可自定义title和被折叠的内容 效果图 示例 import package:flutter/material.dart; import /jh_common/widge…

springboot+websocket开发简单的在线群聊聊天web版本

springbootwebsocket开发简单的在线群聊聊天web版本&#xff01;近期在测试websocket插件的群聊功能。下面是一个简单的demo。分享给大家&#xff0c;亲测可以使用的。 1&#xff1a;首先是一个chat.html页面。代码如下&#xff1a; <!DOCTYPE html> <html lang"…

Linux的Shell脚本详解

本文目录 一、什么是 Shell 脚本文件 &#xff1f;二、编写Shell脚本1. 基本规则2. shell 变量&#xff08;1&#xff09;创建变量&#xff08;2&#xff09;引用变量&#xff08;3&#xff09;删除变量&#xff08;4&#xff09;从键盘读取变量&#xff08;5&#xff09;特殊变…

VMware安装ubuntun虚拟机使用桥接模式无法上网问题解决

问题&#xff1a;最近准备使用VMware虚拟机搭建k8s集群服务&#xff0c;因为需要在同一个网段下&#xff0c;我使用桥接的方式&#xff0c;我发现主机在使用有线连接时虚拟机网络连接正常&#xff0c;但是使用无线网就显示连接不上网络。 解决方法 一、查看网络连接&#xff…