Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >理解算法的复杂度

理解算法的复杂度

作者头像
我是攻城师
发布于 2018-09-30 03:35:34
发布于 2018-09-30 03:35:34
9120
举报
文章被收录于专栏:我是攻城师我是攻城师

关于时间复杂度

在计算机科学中,算法的时间复杂度是一个函数,它定性描述该算法的运行时间,时间复杂度常用大O符号表示,不包括这个函数的低阶和首项系数,使用这种方式时,时间的复杂度可被成为是渐近的(asymptotic analysis),渐近是指在数学分析中是一种描述函数在极限附近的行为的方法,有多个科学领域应用此方法。

(1)在计算机科学中,算法分析考虑给定算法在输入非常大的数据集时候的性能。

(2)当实体系统的规模变得非常大的时候,分析它的行为。

举个简单的例子:函数f(n)=3n^2+3n ,当n变得非常大的时候,函数的第二项3n要远比第一项n^2影响小,所以我们对于这个函数的复杂度描述可以近似认为是O( n^2 ),注意到大O符号里隐藏着一个常数C,所以f(n)里一般不加系数,简单的来说,我们在评估时间复杂度影响的时候,为了简化表示,只看对其影响最大的主要路径,其他的细枝末叶都可以忽略。

算法时间复杂度分析是一个很重要的问题,任何一个程序员都应该熟练掌握其概念和基本方法,而且要善于从数学层面上探寻其本质,才能准确理解其内涵。

常见的算法时间复杂度由大到小如下:

常见的算法时间复杂度由小到大依次为:

Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n^2)<Ο( n^3 )<Ο(2^n)<Ο(n!) 随着问题规模 n的不断增大,时间复杂度不断增大,算法的执行效率越低。

序号

名称

运行时间

举例

1

常数阶

O(1)

数组按下标访问

2

对数阶

O(log2 n)

二分搜索

3

线性阶

Ο(n)

无序数组的搜索

4

线性对数阶

Ο(nlog2n)

快速排序算法

5

平方阶

Ο(n^2)

冒泡排序和插入排序算法

6

立方阶

Ο(n^3)

矩阵乘法的基本实现

7

指数阶

Ο(2^n)或O( k^n )

使用动态规划解决旅行推销员问题

8

阶乘阶

O(n!)

通过暴力搜索解决旅行推销员问题

看下面一个图,从直观上感受一下他们的曲线走势:

根据经验值,在上面表格中只有前4个的时间复杂度是比较快的,一般可以在秒级别返回比如一些排序算法,但稍微大一些的n就会令这些算法不能动了,当n=10万的时候,平方阶一般需要几分钟才能计算完毕,而立方阶则需要200多天,至于更后面的复杂度得需要几年才能运算完毕。如果大于10万,则更加糟糕,所以在设计程序的时候我们得注意相关算法的时间复杂度。

关于空间复杂度

算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了,因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

分析一个算法所占用的存储空间要从各方面综合考虑。如对于递归算法来说,一般都比较简短,算法本身所占用的存储空间较少,但运行时需要一个附加堆栈,从而占用较多的临时工作单元;若写成非递归算法,一般可能比较长,算法本身占用的存储空间较多,但运行时将可能需要较少的存储单元。

对于一个算法,其 时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间;反之,当追求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。另外,算法的所有性能之间都存在着或多或少的相互影响。因此,当设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能,算法的使用频率,算法处理的数据量的大小,算法描述语言的特性,算法运行的机器系统环境等各方面因素,才能够设计出比较好的算法。算法的时间复杂度和空间复杂度合称为算法的复杂度。

总结

本文主要介绍了算法的时间复杂度和空间复杂度的概念和定义,一个好的算法往往能大幅度提升程序的性能,一个坏的算法往往会拖慢整个程序的运行,因此了解算法的复杂度对我们日常开发和写代码则很有指导意义,在掌握本篇文章的知识之后,我们就可以学以致用,对于一些常见的数据结构试着去分析一下其复杂度,比如数组,链表,Hash表,二叉树等。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-09-08,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 我是攻城师 微信公众号,前往查看

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

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
时间复杂度与空间复杂度
算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源和时间却会有很大的区别。那么我们应该如何去衡量不同算法之间的优劣呢?
LittlePanger
2020/04/14
9500
数据结构01 算法的时间复杂度和空间复杂度
1、算法的概念: 算法 (Algorithm),是对特定问题求解步骤的一种描述。 解决一个问题往往有不止一种方法,算法也是如此。那么解决特定问题的多个算法之间如何衡量它们的优劣呢?有如下的指标: 2、衡量算法的指标: (1)时间复杂度:执行这个算法需要消耗多少时间。 (2)空间复杂度:这个算法需要占用多少内存空间。   同一个问题可以用不同的算法解决,而一个算法的优劣将影响到算法乃至程序的效率。算法分析的目的在于为特定的问题选择合适算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。   算法在时间的高
nnngu
2018/03/15
1.3K0
【进阶之路】算法的时间复杂度与空间复杂度
.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
算法的时间复杂度和空间复杂度-总结[通俗易懂]
通常,对于一个给定的算法,我们要做 两项分析。第一是从数学上证明算法的正确性,这一步主要用到形式化证明的方法及相关推理模式,如循环不变式、数学归纳法等。而在证明算法是正确的基础上,第二部就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级,在很大程度上能很好反映出算法的优劣与否。因此,作为程序员,掌握基本的算法时间复杂度分析方法是很有必要的。 算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法。
全栈程序员站长
2022/08/27
1.6K0
时间复杂度和空间复杂度详解 原
(1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
wuweixiang
2018/08/14
7880
数据结构与算法系列之时间复杂度
上一篇《数据结构和算法》中我介绍了数据结构的基本概念,也介绍了数据结构一般可以分为逻辑结构和物理结构。逻辑结构分为集合结构、线性结构、树形结构和图形结构。物理结构分为顺序存储结构和链式存储结构。并且也介绍了这些结构的特点。然后,又介绍了算法的概念和算法的5个基本特性,分别是输入、输出、有穷性、确定性和可行性。最后说阐述了一个好的算法需要遵守正确性、可读性、健壮性、时间效率高和存储量低。其实,实现效率和存储量就是时间复杂度和空间复杂度。本篇我们就围绕这两个"复杂度"展开说明。在真正的开发中,时间复杂度尤为重要,空间复杂度我们不做太多说明。
VV木公子
2018/06/05
5.6K0
数据结构与算法系列之时间复杂度
常见算法时间复杂度
同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。
全栈程序员站长
2022/08/28
6430
Algorithms_入门基础_时间复杂度&空间复杂度
举个例子 ,如何测试我们的程序性能? 性能测试之类的对吧-----> 主机的性能不同,数据的准确性和数据量等等 ,都会对我们的结果产生影响。
小小工匠
2021/08/17
5450
排序算法
排序也称排序算法(Sort Algorithm),排序是将一组数据,依指定的顺序进行排列的过程。
用户9615083
2022/12/30
3010
排序算法
数据结构与算法 - 时间复杂度
目录 一、数据结构概要 二、算法概要 三、时间复杂度简介 四、求解时间复杂度 一、数据结构 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在各类实际应用问题中,数据元素之间总是存在着各种关系,描述数据元素之间关系的方法称为结构。通常,可根据数据元素之间所存在的关系的不同特征,用4类基本结构予以描述: (1)集合:指结构中的数据元素之间只存在“同属一个集合”的关系。 间 (2)线性结构:指结构中的数据元素之间存在“一个对一个”的关系。 数 (3)树形结构:指结构中的数据元素
且行且珍惜_iOS
2018/12/24
7250
数据结构与算法 - 时间复杂度与空间复杂度
时间复杂度:时间复杂度的计算并不是计算程序具体运行的时间,而是算法执行语句的最大次数。 空间复杂度:类似于时间复杂度的讨论,一个算法的空间复杂度为该算法所耗费的存储空间。往往跟为最大创建次数。
進无尽
2018/12/19
2.3K0
排序算法第一篇-排序算法介绍
在面试中,现在无论大小公司都会有算法的。其中排序算法也是一种很常见的面试题。比如冒泡,快排等。这些,排序算法自己看了一次又一次,可是过一段时间,又忘掉了。所以,这次就把算法是怎么推导出来的,详细记录下来。看看这次多久还会忘记。
凯哥Java
2021/06/20
4510
排序算法第一篇-排序算法介绍
算法的时间复杂度和空间复杂度
        这个算法看起来十分简洁,但是它的效率是很差劲的,算50以上就会算算很久,那么它的效率就很差,效率的好坏不能只是看代码是否简洁。 
2024/04/30
2900
【时间复杂度空间复杂度】
当文件没有进行保存时,这个文件保留在内存中,一旦断电,文件将无法保存,因此为了避免这种情况的发生,,处理文件之后,应该及时的ctrl+s保存到磁盘当中去。
每天都要进步呀
2023/03/28
1.7K0
【时间复杂度空间复杂度】
递归算法时间复杂度分析[通俗易懂]
一般情况下,算法中基本操作重复的次数就是问题规模n的某个函数f(n),进而分析f(n)随n的变化情况并确定T(n)的数量级。这里用‘o’来表示数量级,给出算法时间复杂度。 T(n)=o(f(n)); 它表示随问题规模n的增大,算法的执行时间增长率和f(n)增长率成正比,这称作算法的渐进时间复杂度。而我们一般情况下讨论的最坏的时间复杂度。 空间复杂度: 算法的空间复杂度并不是实际占用的空间,而是计算整个算法空间辅助空间单元的个数,与问题的规模没有关系。算法的空间复杂度S(n)定义为该算法所耗费空间的数量级。 S(n)=o(f(n)) 若算法执行所需要的辅助空间相对于输入数据n而言是一个常数,则称这个算法空间复杂度辅助空间为o(1); 递归算法空间复杂度:递归深度n*每次递归所要的辅助空间,如果每次递归所需要的辅助空间为常数,则递归空间复杂度o(n)。
全栈程序员站长
2022/08/27
3K0
递归算法时间复杂度分析[通俗易懂]
算法设计的艺术:探索时间复杂度和空间复杂度的计算方法
可以看到,第二种算法非常高效。第一种算法需要执行n次,而第二种算法只需要执行1次。
Lion 莱恩呀
2024/11/08
1660
算法设计的艺术:探索时间复杂度和空间复杂度的计算方法
用 PHP 的方式实现的各类算法合集
项目地址: https://github.com/PuShaoWei/arithmetic-php About 如果说各种编程语言是程序员的招式,那么数据结构和算法就相当于程序员的内功。 简易结构 ├──Package │ ├── Sort 排序篇 │ │ ├── BubbleSort.php 冒泡排序 │ │ ├── QuickSort.php 快速排序 │ │ ├── ShellSort.php 希尔排序 │
前端教程
2018/03/27
1.1K0
一文搞懂算法的时间复杂度与空间复杂度
本文介绍了算法的时间复杂度和空间复杂度,包括基本概念、计算方法以及常见的时间和空间复杂度。同时,对于复杂情况,还分析了其时间复杂度和空间复杂度。
码科智能
2018/01/03
6.6K0
LeetCode0:学习算法必备知识:时间复杂度与空间复杂度的计算
算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。算法是大厂、外企面试的必备项,也是每个高级程序员的必备技能。针对同一问题,可以有很多种算法来解决,但不同的算法在效率和占用存储空间上的区别可能会很大。
程序新视界
2021/01/06
18.5K2
推荐阅读
相关推荐
时间复杂度与空间复杂度
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档