Python算法的时间复杂度和空间复杂度(实例解析)
作者:Sch01aR# 发布时间:2022-09-26 03:07:06
算法复杂度分为时间复杂度和空间复杂度。
其作用:
时间复杂度是指执行算法所需要的计算工作量;
而空间复杂度是指执行这个算法所需要的内存空间。
(算法的复杂性体现在运行该算法时的计算机所需资源的多少上,计算机资源最重要的是时间和空间(即寄存器)资源,因此复杂度分为时间和空间复杂度)。
简单来说,时间复杂度指的是语句执行次数,空间复杂度指的是算法所占的存储空间
计算时间复杂度的方法:
用常数1代替运行时间中的所有加法常数
修改后的运行次数函数中,只保留最高阶项
去除最高阶项的系数
时间复杂度
算法的时间复杂度是一个函数,它定量描述了该算法的运行时间,时间复杂度常用“O”表述,使用这种方式时,时间复杂度可被称为是渐近的,它考察当输入值大小趋近无穷时的情况
时间复杂度是用来估计算法运行时间的一个式子(单位),一般来说,时间复杂度高的算法比复杂度低的算法慢
print('Hello world') # O(1)
# O(1)
print('Hello World')
print('Hello Python')
print('Hello Algorithm')
for i in range(n): # O(n)
print('Hello world')
for i in range(n): # O(n^2)
for j in range(n):
print('Hello world')
for i in range(n): # O(n^2)
print('Hello World')
for j in range(n):
print('Hello World')
for i in range(n): # O(n^2)
for j in range(i):
print('Hello World')
for i in range(n):
for j in range(n):
for k in range(n):
print('Hello World') # O(n^3)
几次循环就是n的几次方的时间复杂度
n = 64
while n > 1:
print(n)
n = n // 2
26 = 64,log264 = 6,所以循环减半的时间复杂度为O(log2n),即O(logn)
如果是循环减半的过程,时间复杂度为O(logn)或O(log2n)
常见的时间复杂度高低排序:O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)
空间复杂度
空间复杂度:用来评估算法内存占用大小的一个式子
a = 'Python' # 空间复杂度为1
# 空间复杂度为1
a = 'Python'
b = 'PHP'
c = 'Java'
num = [1, 2, 3, 4, 5] # 空间复杂度为5
num = [[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]] # 空间复杂度为5*4
num = [[[1, 2], [1, 2]], [[1, 2], [1, 2]] , [[1, 2], [1, 2]]] # 空间复杂度为3*2*2
定义一个或多个变量,空间复杂度都是为1,列表的空间复杂度为列表的长度
总结
以上所述是小编给大家介绍的Python算法的时间复杂度和空间复杂度网站的支持!
如果你觉得本文对你有帮助,欢迎转载,烦请注明出处,谢谢!
来源:https://www.cnblogs.com/sch01ar/p/8552295.html
猜你喜欢
- 新建图像文件后选Channels面板,新建Alpha1通道:输入文字; &nbs
- python的文件和路径操作函数基本上位于os和os.path模块中。os.listdir(dirname):列出dirname下的目录和文
- 前段时间嗷嗷有发过"好玩的放大镜效果",今天看了下,发现还有简单的方法也能够实现,即利用内外补丁的调整。有兴趣的可以在琢
- TensorFlow是一个采用数据流图(data flow graphs),用于数值计算的开源软件库。节点(Nodes)在图中表示数学操作,
- 在很多企业会使用闲置的 Windows 机器作为临时服务器,有时候我们想远程调用里面的程序或查看日志文件Windows 内置的服务
- MySQL由于它本身的小巧和操作的高效, 在数据库应用中越来越多的被采用.我在开发一个P2P应用的时候曾经使用MySQL来保存P2P节点,由
- 语法df.drop_duplicates(subset = None,
- 一. 访问WEB数据库的多种方案目前在WINDOWS环境下有多种访问WEB数据库的技术,主要有:1.公共网关接口CGI(Commo
- SQL中的单记录函数1.ASCII返回与指定的字符对应的十进制数;SQL> select ascii('A') A,a
- <?phphighlight_file(__FILE__);error_reporting(0);$content = $_POST[
- 今天突然想起这个问题, 就好好搜索整理一下,不过在开始归纳之前,请先来一起做做这个小实验:忽略一切实际的外在情况, 你看了下面的按钮,第一本
- 1. 引言在某些场景下,我们不仅需要进行实时人脸检测追踪,还要进行再加工;这里进行摄像头实时人脸检测,并对于实时检测的人脸进行初步提取;单个
- 第一次碰到这个问题的时候,确实不知道该怎么办,后来请教了一个大神,加上自己的理解,才了解是什么意思,这个东西写python的会经常用到,而且
- Python单元测试unittest中提供了一下四种装饰器实现测试跳过和预期故障。(使用Python 2.7.13)请查考Python手册中
- 本文实例为大家分享了python实现年会抽奖程序的具体代码,供大家参考,具体内容如下发一下自己写的公司抽奖程序。需求:公司年会要一个抽奖程序
- 前言上篇文章记录了2种分割验证码的方法,此外还有一种叫做”滴水算法”(Drop Fall Algorithm)的方法,但本人智商原因看这个算
- jquery基本入门 第一天:选择器相关 1.html()与.text() .html()取得第一个匹配元素的html内容。会带有标签,.t
- 最近在刚从tensorflow转入pytorch,对于自定义的nn.Module 碰到了个问题,即使把模组 modle=Model().cu
- (1) 我们先用arange函数创建一个数组并改变其维度,使之变成一个三维数组:>>> a = np.arange(24)
- 本篇文章以文件上传为例,聊聊 Jmeter 并发执行 Python 脚本的完整流程1. 前言大家好,我是安果!最近有小伙伴后台给我