Python算法中的时间复杂度问题
作者:软件测试开发技术栈 发布时间:2021-03-20 04:52:50
在实现算法的时候,通常会从两方面考虑算法的复杂度,即时间复杂度和空间复杂度。顾名思义,时间复杂度用于度量算法的计算工作量,空间复杂度用于度量算法占用的内存空间。
本文将从时间复杂度的概念出发,结合实际代码示例分析算法的时间复杂度。
渐进时间复杂度
时间复杂度是算法运算所消耗的时间,因为不同大小的输入数据,算法处理所要消耗的时间是不同的,因此评估一个算运行时间是比较困难的,所以通常关注的是时间频度,即算法运行计算操作的次数,记为T(n),其中n称为问题的规模。
同样,因为n是一个变量,n发生变化时,时间频度T(n) 也在发生变化,我们称时间复杂度的极限情形称为算法的渐近时间复杂度,记为O(n),不包含函数的低阶和首项系数。
我们以如下 例子来解释一下:
如上例子中,我们根据代码上执行的平均时间假设,计算 run_time(n) 函数的时间复杂度,如下:
上述时间复杂度计算公式T(n) ,是我们对函数 run_time(n) 进行的时间复杂度的估算。当n 值非常大的时候,T(n)函数中常数项 time0 以及n的系数 (time1+time2+time3+time4) 对n的影响也可以忽略不计了,因此这里函数run_time(n) 的时间复杂度我们可以表示为 O(n)。
因为我们计算的是极限状态下(如,n非常大)的时间复杂度,因此其中存在以下两种特性:
低阶项相对于高阶项产生的影响很小,可以忽略不计。 最高项系数对最高项的影响也很小,可以忽略不计。
根据上述两种特性,时间复杂度的计算方法:
1.只取最高阶项,去掉低阶项。
2.去掉最高项的系数。
3.针对常数阶,取时间复杂度为O(1)。
我们通过下面例子理解一下常见的时间复杂度,如下:
时间复杂度:常数阶 O(1)
时间复杂度:线性阶 O(n)
时间复杂度:线性阶 O(n)
时间复杂度:平方阶 O(n^2)
时间复杂度:平方阶 O(n^2)
时间复杂度:平方阶 O(n^2)
时间复杂度:立方阶 O(n^3)
时间复杂度:对数阶 O(logn)
随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低,时间复杂度排序如下:
练习一下
如下count_sort 函数实现了计数排序,列表中的数范围都在0到100之间,列表长度大约为100万。
如上count_sort 函数的 空间复杂度为 O(n),公式如下:
总结
以上所述是小编给大家介绍的Python算法中的时间复杂度问题网站的支持!
如果你觉得本文对你有帮助,欢迎转载,烦请注明出处,谢谢!
来源:https://developer.51cto.com/art/201911/606148.htm
猜你喜欢
- 前言上篇文章讲的进阶一些的PHP特性不知道大家吸收的怎么样了,今天作为本PHP特性函数的最后一篇,我也会重点介绍一些有趣的PHP特性以及利用
- 用python的matplotlib画图时,往往需要加图例说明。如果不设置任何参数,默认是加到图像的内侧的最佳位置。import matpl
- 如何在生产上部署Django?Django的部署可以有很多方式,采用nginx+uwsgi的方式是其中比较常见的一种方式。uwsgi介绍uW
- 一、前言大多数编译型语言,变量在使用前必须先声明,其中C语言更加苛刻:变量声明必须位于代码块最开始,且在任何其他语句之前。其他语言,想C++
- 为了使一个MySQL系统安全,强烈要求你考虑下列建议……当你连接一个MySQL服务器时,你通常应
- 本文主要涉及图形验证码的相关功能,主要包括,图形验证码获取、验证码文字存储、验证码生成等。图形验证码接口设计和定义 验证码获取接口
- 这是一家游戏公司,他面试通过后 擅长的机试却没答出来,不过还是被录用了。这道题内容大概这样有条蛇它长度不固定,蛇头朝北顺时针盘旋着,请打印出
- 1 实验标准因为训练使用的框架是Pytorch,因此读取的实验标准如下:1、读取分辨率都为1920x1080的5张图片
- 简介如何简单的使用python来实现将一部视频转换为字符画视频的效果。 其实,大家都知道视频就是一帧一帧的图片构成的。  
- 有2种方法:一、 QML中定义一个信号,连接Python里的函数;这里的函数不用特意指明为槽函数,普通函数即可。QML的信号连接Python
- var obj=document.getElementById("id");得到的是dom对象,对该对象进行操作的时候使
- 导航标签彼此互斥、完全穷尽。导航标签其实就是一种文字表达形式,我们用标签来代表网站上的各种分类信息。比如“联系我们”这个标签,代表的内容通常
- 就算我们每天在叫嚷着创新经济,设计救国,我们在生活中也无处不在的看到各种设计庸俗、制作粗劣的海报、店面、户外广告、大胸美女和肌肉 * 交相辉映
- 第一节:WAP的潜能 这些日子,我们常听到WAP技术,一种手机上网的技术。从技术上讲,移动电话不可能和PC来竞争,移动电话的屏幕只能容下很少
- 这个javascript农历日历,万年历代码网上看到的,很不错,功能齐全,值得收藏!功能介绍:动态显示当前世界各国各时区时间,显示当前农历,
- 像素误差看自己设计好上线的网站,偶尔会发觉像素行间出现了弹性空间,总在不经意间蹦出一定的差距。有些页面很难发现,比如活动类页面,这类页面多呈
- 在本教程中,我们将学习如何创建一个使用Django作为后端的天气应用程序。Django提供了一个基于Python Web框架的Web框架,允
- 在当今用户的显示器越来越大的今天,之前的1024*768固宽布局有点越来越不合时宜,对大屏幕的用户而言,两侧空空的留白给人第一眼的印象是严重
- 一、设置开启SMTP服务并获取授权码可以参考第一篇文章,这里不再赘述:【一】https://www.jb51.net/article/142
- 大部分情况下,这种动态生成的sql查询语句写法如下: 代码如下:select A表.字段1,A表.字段2,B表.字段返回,C表.字段返回 f