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
标签:python,算法,空间复杂度,时间复杂度
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
mysql update语句的用法详解
2024-01-22 13:12:46
python筛选出两个文件中重复行的方法
2021-02-16 12:53:04
mysql 8.0.22 zip压缩包版(免安装)下载、安装配置步骤详解
2024-01-15 21:19:16
![](https://img.aspxhome.com/file/2023/7/97437_0s.jpg)
asp网上考试设计思路是怎样的?
2010-07-14 21:09:00
prototype-1.4.0注释版源代码下载
2007-09-30 14:06:00
JavaScript面向对象中的封装和继承你了解吗
2024-06-07 16:00:16
![](https://img.aspxhome.com/file/2023/5/122145_0s.png)
python opencv检测目标颜色的实例讲解
2021-09-02 01:05:33
![](https://img.aspxhome.com/file/2023/1/103761_0s.jpg)
python删除特定文件的方法
2023-07-13 23:29:36
PHP简单系统查询模块代码打包下载
2024-05-11 09:48:03
asp检测文件编码方法
2007-10-03 14:27:00
Python工程师必考的6个经典面试题
2021-07-01 02:55:32
Python如何优雅获取本机IP方法
2021-03-07 15:46:16
提高python代码可读性利器pycodestyle使用详解
2023-09-04 11:22:04
![](https://img.aspxhome.com/file/2023/0/120280_0s.png)
详解duck typing鸭子类型程序设计与Python的实现示例
2022-12-26 07:12:19
python实现列表的排序方法分享
2022-10-06 07:56:01
![](https://img.aspxhome.com/file/2023/0/95760_0s.png)
Python无损音乐搜索引擎实现代码
2021-01-28 19:19:02
![](https://img.aspxhome.com/file/2023/5/67325_0s.jpg)
超详细,教你用python语言实现QQ机器人制作教程
2023-10-05 10:12:53
![](https://img.aspxhome.com/file/2023/9/82639_0s.png)
Python+Pygame实现代码雨动画效果
2023-12-03 18:43:57
![](https://img.aspxhome.com/file/2023/2/94092_0s.png)
Python 京东云无线宝消息推送功能
2021-08-19 09:45:57
python实现银行账户系统
2023-05-27 17:49:08
![](https://img.aspxhome.com/file/2023/0/103340_0s.jpg)