首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >我们常说的算法时间复杂度和空间复杂度到底是什么?

我们常说的算法时间复杂度和空间复杂度到底是什么?

原创
作者头像
编程三昧
修改于 2021-07-01 02:16:37
修改于 2021-07-01 02:16:37
9100
举报
文章被收录于专栏:编程三昧编程三昧
iShot2021-06-30 20.45.18
iShot2021-06-30 20.45.18

前言

针对某一类问题的解决,我们可能需要借助算法来实现,实现的手段也可能是各式各样的。虽然最终都解决了问题,但是各个解决手段,也就是算法还是存在优劣之分的。

既然存在比较,那肯定就有一个标准供来参考,那么我们在评价一个算法的优劣时参考的标准是什么呢?

算法的优劣主要从它执行时所占用的「时间」和「空间」两个方面来进行评定,也就是我们常听到的「时间复杂度」和「空间复杂度」。

  • 时间复杂度:执行算法所需要的计算工作量,可以估算出程序对处理器的使用程度。
  • 空间复杂度:执行当前算法所需要的内存空间,可以估算出程序对处理器的使用程度。

时间复杂度

谈到是时间复杂度,我们很多人的第一反应就是将算法执行一遍,打印出其执行的时间就是它所消耗的时间,其实这样是不可行的,因为:

  • 解决一个问题的算法可能有很多种,一一实现的工作量无疑是巨大的,得不偿失;
  • 不同计算机的软、硬件环境不同,即便使用同一台计算机,不同时间段其系统环境也不相同,程序的运行时间很可能会受影响,严重时甚至会导致误判。

实际场景中,我们更喜欢用一个估值来表示算法所编程序的运行时间。所谓估值,即估计的、并不准确的值。注意,虽然估值无法准确的表示算法所编程序的运行时间,但它的得来并非凭空揣测,需要经过缜密的计算后才能得出。

表示一个算法所编程序运行时间的多少,用的并不是准确值(事实上也无法得出),而是根据合理方法得到的预估值。

我们一般用“大 O 符号表示法”来表示时间复杂度:T(n) = O(f(n))

  • n 是影响复杂度变化的因子
  • f(n) 是复杂度具体的算法
  • O 表示正比例关系

这个公式的全称是:算法的渐进时间复杂度

大 O 符号表示法并不是用于来真实代表算法的执行时间的,它是用来表示代码执行时间的增长变化趋势的。

我们来看一个常见的例子:

代码语言:txt
AI代码解释
复制
for(let index = 0; index < n; index++){
	console.log(index);
}

可以看到,这段程序中仅有 2 行代码,其中:

  • for 循环从 index 的值为 0 一直逐增至 n(注意,循环退出的时候 index 值为 n),因此 for 循环语句执行了 n+1 次;
  • 而循环内部仅有一条语句,index 的值每增 1 该语句就执行一次,一直到 index 的值为 n-1,因此,打印语句一共执行了 n 次。

因此,整段代码中所有语句共执行了 (n+1)+n 次,即 2n+1 次。数据结构中,每条语句的执行次数,又被称为该语句的频度。整段代码的总执行次数,即整段代码的频度。

常见的时间复杂度量级

  • 常数阶O(1)
  • 对数阶O(logN)
  • 线性阶O(n)
  • 平方阶O(n^2)
  • 立方阶O(n^3)
  • K次方阶O(n^k)
  • 指数阶(2^n)

这里仅介绍了以最坏情况下的频度作为时间复杂度,而在某些实际场景中,还可以用最好情况下的频度和最坏情况下的频度的平均值来作为算法的时间复杂度。

空间复杂度

和时间复杂度类似,一个算法的空间复杂度,也常用大 O 记法表示。空间复杂度比较常用的有:

  • O(1)
  • O(n)
  • O(n²)

要知道每一个算法所编写的程序,运行过程中都需要占用大小不等的存储空间,例如:

  • 程序代码本身所占用的存储空间;
  • 程序中如果需要输入输出数据,也会占用一定的存储空间;
  • 程序在运行过程中,可能还需要临时申请更多的存储空间。

首先,程序自身所占用的存储空间取决于其包含的代码量,如果要压缩这部分存储空间,就要求我们在实现功能的同时,尽可能编写足够短的代码。

程序运行过程中输入输出的数据,往往由要解决的问题而定,即便所用算法不同,程序输入输出所占用的存储空间也是相近的。

事实上,对算法的空间复杂度影响最大的,往往是程序运行过程中所申请的临时存储空间。不同的算法所编写出的程序,其运行时申请的临时存储空间通常会有较大不同。

如果程序所占用的存储空间和输入值无关,则该程序的空间复杂度就为 O(1);反之,如果有关,则需要进一步判断它们之间的关系:

  • 如果随着输入值 n 的增大,程序申请的临时空间成线性增长,则程序的空间复杂度用 O(n) 表示;
  • 如果随着输入值 n 的增大,程序申请的临时空间成 n2 关系增长,则程序的空间复杂度用 O(n2) 表示;
  • 如果随着输入值 n 的增大,程序申请的临时空间成 n3 关系增长,则程序的空间复杂度用 O(n3) 表示;

比如:

代码语言:txt
AI代码解释
复制
let m = 0;
for(let index = 0; index < 9999; index++){
	m++;
}

虽然 m 的值随着 index 的增加在一直变化,可是并未产生新的变量,即程序所占用的空间并未发生变化,所以,它的空间复杂度为 O(1)。

总结

  1. 时间复杂度和空间复杂度都是一种经过严谨推算得出的预估值,并不能代表实际情况。
  2. 时间复杂度和空间复杂度代表的是一种趋势。
  3. 我们一般情况下所说的时间复杂度和空间复杂度,都是最坏情况下的执行趋势,实际情况可能比预估的要好。
  4. 多数业务场景下,一个好的算法往往更注重的是时间复杂度的比较,而空间复杂度只要在一个合理的范围内就可以。

~

~ 本文完,感谢阅读!

~

学习有趣的知识,结识有趣的朋友,塑造有趣的灵魂!

大家好,我是〖编程三昧〗的作者 隐逸王,我的公众号是『编程三昧』,欢迎关注,希望大家多多指教!

你来,怀揣期望,我有墨香相迎! 你归,无论得失,唯以余韵相赠!

知识与技能并重,内力和外功兼修,理论和实践两手都要抓、两手都要硬!

自由职业者, 工作空间, Coworking, 办公桌, 办公室, 计算机, 技术, 财经, 市场营销, 工作
自由职业者, 工作空间, Coworking, 办公桌, 办公室, 计算机, 技术, 财经, 市场营销, 工作

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
数据结构与算法 - 时间复杂度与空间复杂度
时间复杂度:时间复杂度的计算并不是计算程序具体运行的时间,而是算法执行语句的最大次数。 空间复杂度:类似于时间复杂度的讨论,一个算法的空间复杂度为该算法所耗费的存储空间。往往跟为最大创建次数。
進无尽
2018/12/19
2.3K0
数据结构初阶必修:——时间复杂度和空间复杂度
实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这 里我们使用大O的渐进表示法。
用户11290664
2024/09/25
1070
数据结构初阶必修:——时间复杂度和空间复杂度
So easy 10分钟搞懂时间复杂度和空间复杂度!
温馨提醒: 本文适用于所有开发者人群、无论你是小白、初学者还是已经工作的"社会人"。
IT学习日记
2022/09/13
3530
So easy 10分钟搞懂时间复杂度和空间复杂度!
算法的时间复杂度和空间复杂度计算
在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n)= O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度,是一种“渐进表示法”。其中f(n)是问题规模n的某个函数。
全栈程序员站长
2022/08/28
3.6K0
算法的时间复杂度和空间复杂度计算
【数据结构与算法】时间复杂度与空间复杂度
早期,计算机刚被发明出来,内存空间并不是很大,所以不仅追求程序运行时的时间效率,还追求空间效率,但发展到今天,已经不太追求空间效率了,时间效率的追求是不变的。
aosei
2024/01/23
1360
【数据结构与算法】时间复杂度与空间复杂度
时间复杂度与空间复杂度
在计算机程序编写前,依据统计方法对算法进行估算,经过总结,我们发现一个高级语言编写的程序程序在计算机上运行所消耗的时间取决于下列因素:
Rochester
2020/09/01
6740
算法的时间复杂度和空间复杂度-总结[通俗易懂]
通常,对于一个给定的算法,我们要做 两项分析。第一是从数学上证明算法的正确性,这一步主要用到形式化证明的方法及相关推理模式,如循环不变式、数学归纳法等。而在证明算法是正确的基础上,第二部就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级,在很大程度上能很好反映出算法的优劣与否。因此,作为程序员,掌握基本的算法时间复杂度分析方法是很有必要的。 算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法。
全栈程序员站长
2022/08/27
1.6K0
数据结构01 算法的时间复杂度和空间复杂度
1、算法的概念: 算法 (Algorithm),是对特定问题求解步骤的一种描述。 解决一个问题往往有不止一种方法,算法也是如此。那么解决特定问题的多个算法之间如何衡量它们的优劣呢?有如下的指标: 2、衡量算法的指标: (1)时间复杂度:执行这个算法需要消耗多少时间。 (2)空间复杂度:这个算法需要占用多少内存空间。   同一个问题可以用不同的算法解决,而一个算法的优劣将影响到算法乃至程序的效率。算法分析的目的在于为特定的问题选择合适算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。   算法在时间的高
nnngu
2018/03/15
1.3K0
算法的时间复杂度和空间复杂度笔记
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
蛮三刀酱
2019/09/10
1.2K0
算法的时间复杂度和空间复杂度笔记
数据结构入门(2)时间复杂度与空间复杂度
下面一串代码是关于如何实现斐波那契数列,代码非常简洁,其实编程是非常灵活的,一个功能可以有不同的实现方法,通常我们需要找到效率最高的,同时代码量非常可观,简洁的理想代码。
对编程一片赤诚的小吴
2024/02/11
1360
【进阶之路】算法的时间复杂度与空间复杂度
.markdown-body{word-break:break-word;line-height:1.75;font-weight:400;font-size:15px;overflow-x:hidden;color:#333}.markdown-body h1,.markdown-body h2,.markdown-body h3,.markdown-body h4,.markdown-body h5,.markdown-body h6{line-height:1.5;margin-top:35px;margin-bottom:10px;padding-bottom:5px}.markdown-body h1{font-size:30px;margin-bottom:5px}.markdown-body h2{padding-bottom:12px;font-size:24px;border-bottom:1px solid #ececec}.markdown-body h3{font-size:18px;padding-bottom:0}.markdown-body h4{font-size:16px}.markdown-body h5{font-size:15px}.markdown-body h6{margin-top:5px}.markdown-body p{line-height:inherit;margin-top:22px;margin-bottom:22px}.markdown-body img{max-width:100%}.markdown-body hr{border:none;border-top:1px solid #ddd;margin-top:32px;margin-bottom:32px}.markdown-body code{word-break:break-word;border-radius:2px;overflow-x:auto;background-color:#fff5f5;color:#ff502c;font-size:.87em;padding:.065em .4em}.markdown-body code,.markdown-body pre{font-family:Menlo,Monaco,Consolas,Courier New,monospace}.markdown-body pre{overflow:auto;position:relative;line-height:1.75}.markdown-body pre>code{font-size:12px;padding:15px 12px;margin:0;word-break:normal;display:block;overflow-x:auto;color:#333;background:#f8f8f8}.markdown-body a{text-decoration:none;color:#0269c8;border-bottom:1px solid #d1e9ff}.markdown-body a:active,.markdown-body a:hover{color:#275b8c}.markdown-body table{display:inline-block!important;font-size:12px;width:auto;max-width:100%;overflow:auto;border:1px solid #f6f6f6}.markdown-body thead{background:#f6f6f6;color:#000;text-align:left}.markdown-body tr:nth-child(2n){background-color:#fcfcfc}.markdown-body td,.markdown-body th{padding:12px 7px;line-height:24px}.markdown-body td{min-width:120px}.markdown-body blockquote{color:#666;padding:1px 23px;margin:22px 0;border-left:4px solid #cbcbcb;background-color:#f8f8f8}.markdown-body blockquote:after{display:block;content:""}.markdown-body blockquote>p{margin:10px 0}.markdown-body ol,.markdown-body ul{padding-left:28px}.markdown-body ol li,.markdown-body
南橘
2021/04/02
9050
【进阶之路】算法的时间复杂度与空间复杂度
时间复杂度和空间复杂度
这个算法的运行次数函数是f (n) =3。 根据我们推导大0阶的方法,第一步就是把常数项3 改为1。在保留最高阶项时发现,它根本没有最高阶项,所以这个算法的时间复杂度为0(1)。
周三不加班
2019/09/04
1.2K0
时间和空间复杂度
时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间。
秦jh
2024/01/19
1580
时间和空间复杂度
时间复杂度和空间复杂度 如何计算出来_代码时间复杂度和空间复杂度
在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n}=0(f(n))。它表示随问题规模n的增大,算法执行时间的埔长率和 f(n)的埔长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中f( n)是问题规横n的某个函数。
全栈程序员站长
2022/11/17
7060
时间复杂度和空间复杂度 如何计算出来_代码时间复杂度和空间复杂度
LeetCode0:学习算法必备知识:时间复杂度与空间复杂度的计算
算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。算法是大厂、外企面试的必备项,也是每个高级程序员的必备技能。针对同一问题,可以有很多种算法来解决,但不同的算法在效率和占用存储空间上的区别可能会很大。
程序新视界
2021/01/06
18.5K2
保姆级教学!带你玩转时间复杂度和空间复杂度!
数据结构与算法,作为编程界从入门到劝退的王者,是很多初学者心中神圣而想侵犯的村花儿,化身舔狗,费尽心思,舔到最后,我命油我不油天。
编程文青李狗蛋
2022/01/05
3150
DS:时间复杂度和空间复杂度
算法(Algorithm):就是定义良好的计算过程,他取一个或一组的值为输入,并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤,用来将输入数据转化成输出结果。
小陈在拼命
2024/02/17
2860
DS:时间复杂度和空间复杂度
时间复杂度和空间复杂度详解 原
(1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
wuweixiang
2018/08/14
7880
算法的时间复杂度和空间复杂度
        这个算法看起来十分简洁,但是它的效率是很差劲的,算50以上就会算算很久,那么它的效率就很差,效率的好坏不能只是看代码是否简洁。 
2024/04/30
2920
Algorithms_入门基础_时间复杂度&空间复杂度
举个例子 ,如何测试我们的程序性能? 性能测试之类的对吧-----> 主机的性能不同,数据的准确性和数据量等等 ,都会对我们的结果产生影响。
小小工匠
2021/08/17
5450
推荐阅读
相关推荐
数据结构与算法 - 时间复杂度与空间复杂度
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档