这些Python函数没有预期的运行时间
ankush981
（我不确定这个问题是否属于这里或CS论坛。我将其保留在这里，因为它具有特定于Python的代码。请根据需要进行迁移！）这些天，我正在研究算法，使用Python作为我的首选工具。今天，我想绘制一个简单问题的三种变化的运行时间：计算给定序列（列表）的前缀平均值。
这是三个变体：
import timeit
seq = [20, 45, 45, 40, 12, 48, 67, 90, 0, 56, 12, 45, 67, 45, 34, 32, 20]
# Quadratic running time
def quad (S):
n = len(S)
A = [0] * n
for j in range(n):
total = 0
for i in range(j+1):
total += S[i]
A[j] = total / (j+1)
return A
# Use prev result
def prev (S):
n = len(S)
A = [0] * n
for j in range(n):
if j == 0:
A[j] = S[j]
else:
A[j] = (A[j-1]*j + S[j]) / (j+1)
return A
# Use Python's sum method
def summ (S):
n = len(S)
A = [0] * n
for j in range(n):
A[j] = sum(S[0:j+1])/(j+1)
return A
def plot_func (name):
for i in range(0, 1000000, 100000):
t = timeit.Timer('{}(seq)'.format(name), 'from __main__ import {}, seq'.format(name))
print(i, ',', t.timeit(number=i))
plot_func('quad')
plot_func('prev')
plot_func('summ')
因此，我正在收集三种算法的运行时间并绘制它们。我的最终数据如下所示：
Input size Quadratic Prev Summ
(x100000)
1 4.92E-007 7.78E-007 3.47E-007
2 1.582717351 0.603501161 0.750457885
3 3.205707528 1.176623609 1.508853766
4 4.796092943 1.76059924 2.295842737
5 6.457349465 2.34945291 3.112500982
6 8.057410897 2.947556047 3.882303307
7 9.59740446 3.520847787 4.654968896
8 11.36328988 4.122617632 5.412608518
9 12.776150393 4.703240974 6.181500295
10 14.704703677 5.282404892 6.882074295
绘制时，这些数字导致：
现在，根据我遵循的教科书，这些函数quad和summ应该在二次时间prev内运行，而在线性时间内运行。我可以看到它prev的速度明显快于quad速度summ，但对我来说却有些快，但是对我来说，所有这些看起来都像是线性函数！而且，summ和之间的差距很小prev。
有人可以解释怎么了吗？
f
算法的渐近复杂性意味着它依赖于输入长度。在这里，您无需更改运行之间的输入大小，而只需更改运行每种算法的次数（作为的参数timeit()）：
for i in range(0, 1000000, 100000):
t = timeit.Timer('{}(seq)'.format(name), 'from __main__ import {}, seq'.format(name))
print(i, ',', t.timeit(number=i))
为了获得正确的比较，请更改两次运行之间的序列长度。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
相关文章
Related 相关文章
- 1
计算给定函数python的运行时间
- 2
有两个线程的运行时间与一个线程的运行时间没有改善
- 3
循环函数的运行时间
- 4
计算函数的运行时间
- 5
为什么这些方法没有在运行时由define_method动态定义？
- 6
为什么这些方法没有在运行时由define_method动态定义？
- 7
对这些渐近符号及其运行时间感到困惑
- 8
复制构造函数和移动构造函数具有相同的运行时间并且没有调用移动构造函数
- 9
有运行时间限制吗？
- 10
Manim：动画的运行时间不符合预期
- 11
有没有办法查看Azure Functions运行时的更新时间？
- 12
Spark中有没有办法保持每个阶段的运行时间？
- 13
算法的实验运行时间与理论运行时间函数的比较
- 14
如果没有正确关闭，如何检查最后一次正常运行时间？
- 15
具有两个输入的递归函数的运行时间
- 16
了解具有嵌套循环的函数的理论运行时间
- 17
具有三个嵌套 for 循环的函数运行时间的渐近增长
- 18
优化运行时间：更改igraph中边缘的权重需要很长时间。有没有优化的方法？
- 19
Python的低层性能与高层性能（回文函数的运行时间分析）
- 20
我的Javascript函数运行时，我的A框架没有呈现。如何才能同时渲染？
- 21
递归函数的Big-O运行时间
- 22
试图弄清楚我的函数的运行时间
- 23
递归函数的Big-O运行时间
- 24
如果运行时间太长，则中止函数执行
- 25
脚本中的函数运行时的时间戳
- 26
如何使用clock()函数获取运行时间
- 27
确定多个函数调用的运行时间
- 28
从Python中的日期/时间计算正常运行时间
- 29
在cron作业中运行时，Python脚本引发错误，但在其他时间没有其他错误
我来说两句