Python算法中时间复杂度问题的示例分析-创新互联
这篇文章主要介绍了Python算法中时间复杂度问题的示例分析,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。
创新互联是一家集成都做网站、成都网站制作、网站页面设计、网站优化SEO优化为一体的专业网站制作公司,已为成都等多地近百家企业提供网站建设服务。追求良好的浏览体验,以探求精品塑造与理念升华,设计最适合用户的网站页面。 合作只是第一步,服务才是根本,我们始终坚持讲诚信,负责任的原则,为您进行细心、贴心、认真的服务,与众多客户在蓬勃发展的市场环境中,互促共生。在实现算法的时候,通常会从两方面考虑算法的复杂度,即时间复杂度和空间复杂度。顾名思义,时间复杂度用于度量算法的计算工作量,空间复杂度用于度量算法占用的内存空间。
本文将从时间复杂度的概念出发,结合实际代码示例分析算法的时间复杂度。
渐进时间复杂度
时间复杂度是算法运算所消耗的时间,因为不同大小的输入数据,算法处理所要消耗的时间是不同的,因此评估一个算运行时间是比较困难的,所以通常关注的是时间频度,即算法运行计算操作的次数,记为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算法中时间复杂度问题的示例分析-创新互联
当前地址:http://scyanting.com/article/dpoico.html