Python算法中的时间复杂度问题

yipeiwu_com6年前Python基础

在实现算法的时候,通常会从两方面考虑算法的复杂度,即时间复杂度和空间复杂度。顾名思义,时间复杂度用于度量算法的计算工作量,空间复杂度用于度量算法占用的内存空间。

本文将从时间复杂度的概念出发,结合实际代码示例分析算法的时间复杂度。

渐进时间复杂度

时间复杂度是算法运算所消耗的时间,因为不同大小的输入数据,算法处理所要消耗的时间是不同的,因此评估一个算运行时间是比较困难的,所以通常关注的是时间频度,即算法运行计算操作的次数,记为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算法中的时间复杂度问题,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对【听图阁-专注于Python设计】网站的支持!
如果你觉得本文对你有帮助,欢迎转载,烦请注明出处,谢谢!

相关文章

pycharm修改界面主题颜色的方法

pycharm修改界面主题颜色的方法

如下所示: 以上这篇pycharm修改界面主题颜色的方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持【听图阁-专注于Python设计】。...

Go/Python/Erlang编程语言对比分析及示例代码

Go/Python/Erlang编程语言对比分析及示例代码

本文主要是介绍Go,从语言对比分析的角度切入。之所以选择与Python、Erlang对比,是因为做为高级语言,它们语言特性上有较大的相似性,不过最主要的原因是这几个我比较熟悉。 Go的很...

使用Python中的tkinter模块作图的方法

使用Python中的tkinter模块作图的方法

python简述: Python是一种解释型、面向对象、动态数据类型的高级程序设计语言。自从20世纪90年代初Python语言诞生至今,它逐渐被广泛应用于处理系统管理任务和Web编程。P...

python中使用smtplib和email模块发送邮件实例

SMTP模块这么多已定义的类中,我们最常用的的还是smtplib.SMTP类,就具体看看该类的用法:smtp实例封装一个smtp连接,它支持所有的SMTP和ESMTP操作指令,如果hos...

在Python中使用defaultdict初始化字典以及应用方法

Python中可以使用collections中的defaultdict类实现创建进行统一初始化的字典。这里总结两种常用一点的初始化方式,分别是初始化为list和int。 初始化为list...