首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >算法中的时间复杂度

算法中的时间复杂度

作者头像
张云飞Vir
发布于 2020-03-23 08:03:06
发布于 2020-03-23 08:03:06
1.3K00
代码可运行
举报
文章被收录于专栏:写代码和思考写代码和思考
运行总次数:0
代码可运行

概述

程序员写代码过程中总要用到算法,而不同的算法有不同的效率,时间复杂度是用来评估的算法的效率的一种方式。

比如说对于一个功能,可以实现的方法很多种,我们在实现过程中选择效率最佳的方式来实现,它影响了我们在一定的场景下选择的数据结构和算法,比如何时选择使用ArrayList,何时用LinkedList。

本文结构:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
概念
    渐进时间复杂度
场景示例
    场景1
    场景2
    场景3
    场景4
推导出时间复杂度
     时间复杂度计算方式
     常数阶
     线性阶
     平方阶
     立方阶
     对数阶

概念

在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。 时间复杂度常用大O符号表述。 时间复杂度可被称为是渐近的,即考察输入值大小趋近无穷时的情况。

简单理解就是:

  • 用 “大O” 表示 “时间复杂度”,示例: O(n)
  • 用一个函数表达算法复杂度的值,格式:O( 具体不同的函数 )
  • 它定性的描述“运行时间”
  • 它是渐进的,趋向接近的。

渐进时间复杂度

为便于计算时间复杂度,通常会估计算法的操作单元数量,每个单元运行的时间都是相同的。因此,总运行时间和算法的操作单元数量最多相差一个常量系数。

简化的公式表示: 总运行时间 = 操作次数 * 固定时间的运行单元

而算法有很多种,很难直接比较。我们期望“操作次数”是一个常数,而实际它很难直接用常数表示。于是引入了 渐进时间复杂度,官方的定义如下:

渐进时间复杂度(asymptotic time complexity): 若存在函数 f(n),使得当n趋近于无穷大时,T(n)/ f(n)的极限值为不等于零的常数,则称 f(n)是T(n)的同数量级函数。记作 T(n)= O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

渐进时间复杂度用大写O来表示,所以也被称为大O表示法

场景示例

场景1:

一条长16寸的面包,每1天16寸,需要多少天呢?

太简单了,一天。 函数表示: T(n) = 1

场景2:

一条长16寸的面包,每5天吃掉面包剩余长度的一半,那么把面包吃得只剩下1寸,需要多少天呢?

就是数字16不断地除以2,直到等于1?这里要涉及到数学当中的对数,以2位底,16的对数,可以简写为log16。因此,需要 5 X log16 = 5 X 4 = 20 天。 函数表示: T(n) = 5logn。

场景3:

一条长10寸的面包,每3天吃掉1寸,那么吃掉整个面包需要几天?

很简单,即 函数表示: T(n) = 3n。

场景4:

一条长10寸的面包,吃掉第一个一寸需要1天时间,吃掉第二个一寸需要2天时间,吃掉第三个一寸需要3天时间.....每多吃一寸,所花的时间也多一天。那么小吃掉整个面包需要多少天呢?

答案是从1累加到10的总和,也就是55天。即 1+2+3+......+ n-1 + n = (1+n)*n/2 = 0.5n^2 + 0.5n。 函数表示: T(n) = 0.5n^2 + 0.5n。

推导出时间复杂度

推导出时间复杂度呢?有如下几个原则:

(1) 如果运行时间是常数量级,用常数1表示; (2) 只保留时间函数中的最高阶项; (3) 如果最高阶项存在,则省去最高阶项前面的系数。

场景1: T(n) = 1 最高阶项为3n,省去系数3,转化后为:T(n) = O(1)

场景2: T(n) = 5logn 最高阶项为5logn,省去系数5,转化后为:T(n) = O(logn)

场景3: T(n) = 3n 最高阶项为3n,省去系数3,转化后为:T(n) = O(n)

场景4: T(n) = 0.5n^2 + 0.5n 最高阶项为0.5n^2,省去系数0.5,转化后为:T(n) = O(n^2) 备注:^ 符号表示 平方,n^2表示 n的平方

这四种时间复杂度究竟谁用时更长,谁节省时间呢?稍微思考一下就可以得出结论:

O(1)< O(logn)< O(n)< O(n^2)

其实这四种对应的时间复杂度是: 常数阶,对数阶,线性阶,立方阶。

常见时间复杂度还有:常数阶、线性阶、平方阶、立方阶、对数阶、nlog2n阶、指数阶 效率:O(1) > O(log2n)> o(n)> o(nlog2n) > o(n^2) > o(n^3) > o(2^n) > o(n!) > o(n^n)

代码中的时间复杂度

时间复杂度计算方式

举例:计算1+2+3+....+n的和

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
$sum=0

for($i=1;$i<=$n;$i++){
   $sum+=$i
}

可以看到循环了n次,所以时间复杂度就是O(n)

常数阶 O(1)

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
function test($n){
    echo $n;
    echo $n;
    echo $n;
}

执行了三次 echo,运行次数很固定,是个常数。那么时间复杂度就是O(3),取为O(1)

线性阶 O(n)

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
for($i=1;$i<=$n;$i++){
    $sum+=$i
}

执行n 次,时间复杂度就是O(n)

平方阶:o(n2)/o(n3)

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
$sum=0;
for($i=1;$i<=$n;$i++){
    for($j=1;$j<$n;$j++){
    $sum+=$j
    }
}

两次循环,里面循环执行了n次,外层循环也执行了n次,所以时间复杂度为O(n^2)

立方阶

与上面类似,就是 三个 for 循环

对数阶:O(log2n)

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
while($n>=1){
    $n=$n/2;
}

即不断除以2,

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
n          n/2        n/2/2      n/2/2/2    n/2/2/...

规律:n/(2^m)=1;我们需要算出m, 转换成n=2^m,得出m=log2n,所以时间复杂度为O(logn)

END

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

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

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

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
漫画:什么是时间复杂度?
场景1. 给小灰一条长10寸的面包,小灰每3天吃掉1寸,那么吃掉整个面包需要几天?
用户1564362
2019/07/04
4320
算法复杂度(二)
[ 来自360百科 ]算法在编写成可执行程序后,运行时所需要的资源,资源包括时间资源和内存资源。应用于数学和计算机导论。同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。下面就时间复杂度和空间复杂度做出解释。
花狗Fdog
2020/10/28
6130
算法复杂度(二)
【数据结构和算法的概述】-01
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
跟着飞哥学编程
2023/04/03
7430
【数据结构和算法的概述】-01
数据结构与算法(一)| 时间复杂度与空间复杂度
外层每执行一次,内层执行100次。总的执行次数为 100 * 100。即 n 的平方。此时 大O 为 O(n^2)
Mervyn
2020/07/21
3770
算法(一)时间复杂度
前言 算法很重要,但是一般情况下做移动开发并不经常用到,所以很多同学早就将算法打了个大礼包送还给了老师了,况且很多同学并没有学习过算法。这个系列就让对算法头疼的同学能快速的掌握基本的算法。过年放假阶段玩了会游戏NBA2K17的生涯模式,没有比赛的日子也都是训练,而且这些训练都是自发的,没有人逼你,从早上练到晚上,属性也不涨,但是如果日积月累,不训练和训练的人的属性值就会产生较大差距。这个突然让我意识到了现实世界,要想成为一个球星(技术大牛)那就需要日积月累的刻意训练,索性放下游戏,接着写文章吧。 1.算法的
用户1269200
2018/02/01
8780
算法(一)时间复杂度
解惑3:时间频度,算法时间复杂度[通俗易懂]
要理解时间复杂度,需要先理解时间频度,而时间频度简单的说,就是算法中语句的执行次数。
全栈程序员站长
2022/09/23
8670
解惑3:时间频度,算法时间复杂度[通俗易懂]
算法—时间复杂度[通俗易懂]
时间和空间都是计算机资源的重要体现,而算法的复杂性就是体现在运行该算法时的计算机所需的资源多少;
全栈程序员站长
2022/08/27
3.3K0
算法—时间复杂度[通俗易懂]
时间复杂度
很多人包括我自己都有一个疑问,就是现在的计算机的硬件性能已经很强大了,所以对于性能或者说时间复杂度上还用关心吗,答案是需要的。 比如有这样一个例子,在一台很久的机器和一台处理性能高100倍的新机器,旧机器执行算法A时间复杂度为O(n),新机器执行算法B的时间复杂度为O(n2)。下面表格做下对比,因为性能差100倍,所以旧机器时间*100
OPice
2021/09/07
6630
算法时间复杂度计算方式
【对于一个给定的算法,通常要评估其正确性和运行效率的高低。算法的正确性评估不在本文范围之内,本文主要讨论从算法的时间复杂度特性去评估算法的优劣。】
全栈程序员站长
2022/08/28
5470
算法时间复杂度计算方式
数据结构与算法系列之时间复杂度
上一篇《数据结构和算法》中我介绍了数据结构的基本概念,也介绍了数据结构一般可以分为逻辑结构和物理结构。逻辑结构分为集合结构、线性结构、树形结构和图形结构。物理结构分为顺序存储结构和链式存储结构。并且也介绍了这些结构的特点。然后,又介绍了算法的概念和算法的5个基本特性,分别是输入、输出、有穷性、确定性和可行性。最后说阐述了一个好的算法需要遵守正确性、可读性、健壮性、时间效率高和存储量低。其实,实现效率和存储量就是时间复杂度和空间复杂度。本篇我们就围绕这两个"复杂度"展开说明。在真正的开发中,时间复杂度尤为重要,空间复杂度我们不做太多说明。
VV木公子
2018/06/05
5.6K0
数据结构与算法系列之时间复杂度
【久远讲算法①】什么是时间复杂度
小学数学课上,你是不是可以用 3+3+3 或者 3*3 来解决三个三相加这个问题,虽然算的结果都是9,但是中间我们用的方法是不一样的。
AI悦创
2021/10/10
3660
【久远讲算法①】什么是时间复杂度
排序算法
排序也称排序算法(Sort Algorithm),排序是将一组数据,依指定的顺序进行排列的过程。
用户9615083
2022/12/30
3010
排序算法
【数据结构】算法的时间复杂度
上一小节我们讲到,比较两个算法的优劣最重要的比较方式就是拿算法的时间复杂度来做比较.这节我们就来系统的学习一下算法的时间复杂度:
修修修也
2024/04/01
1860
【数据结构】算法的时间复杂度
算法时间复杂度
很多程序员,做了很长时间的编程工作却始终都弄不明白算法的时间复杂度的估算,这是很可悲的一件事情。因为弄不清楚,所以也就从不深究自己写的代码是否效率底下,是不是可以通过优化,让计算机更加快速高效。所以在我最近自学看完算法的时间复杂度这个章节之后,我决定写一篇文章回顾,加深记忆,帮助理解。
Originalee
2018/08/30
9020
算法的时间复杂度和空间复杂度-总结[通俗易懂]
通常,对于一个给定的算法,我们要做 两项分析。第一是从数学上证明算法的正确性,这一步主要用到形式化证明的方法及相关推理模式,如循环不变式、数学归纳法等。而在证明算法是正确的基础上,第二部就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级,在很大程度上能很好反映出算法的优劣与否。因此,作为程序员,掌握基本的算法时间复杂度分析方法是很有必要的。 算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法。
全栈程序员站长
2022/08/27
1.6K0
时间复杂度和空间复杂度 如何计算出来_代码时间复杂度和空间复杂度
在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n}=0(f(n))。它表示随问题规模n的增大,算法执行时间的埔长率和 f(n)的埔长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中f( n)是问题规横n的某个函数。
全栈程序员站长
2022/11/17
7060
时间复杂度和空间复杂度 如何计算出来_代码时间复杂度和空间复杂度
【进阶之路】算法的时间复杂度与空间复杂度
.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
【进阶之路】算法的时间复杂度与空间复杂度
数据结构算法的时间复杂度_数据结构中排序的时间复杂度
大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说数据结构算法的时间复杂度_数据结构中排序的时间复杂度,希望能够帮助大家进步!!!
Java架构师必看
2022/08/14
1.2K0
数据结构算法的时间复杂度_数据结构中排序的时间复杂度
数据结构之时间复杂度和空间复杂度
我们都知道算法是处理数据的方法,那么如何衡量一个算法的好坏呢?(即,判断该算法的效率如何) 由于算法在编写成可执行程序后,运行会消耗时间资源和空间(内存)资源,因此衡量一个算法的好坏一般通过时间和空间两个维度进行衡量。即,时间复杂度和空间复杂度。
摘星
2023/04/28
3120
数据结构之时间复杂度和空间复杂度
常见算法时间复杂度
同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。
全栈程序员站长
2022/08/28
6440
推荐阅读
相关推荐
漫画:什么是时间复杂度?
更多 >
交个朋友
加入腾讯云技术交流站
洞悉AI新动向 Get大咖技术交流群
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验