在 python 中的线性时间 O(n) 中既没有 for 也没有 while 循环运行

Question

我测量了 python 中 for 和 while 循环的运行时间，并用 matplotlib 绘制了它们。令我惊讶的是，这些图看起来并不那么线性，尤其是 for 循环中的那个。循环遍历 600k 个数字所花的时间也比循环遍历 700k 个数字所花的时间更长。

我做错了什么，还是只是 python 做事方式不同？

import time
import matplotlib.pyplot as plt

time_while=[]
time_for=[]
for i in range(200000, 1000000+1, 100000):
    t1 = time.time()
    n = 0
    while n < i:
        n += 1
    t2 = time.time()
    time_while.append(round(t2-t1,5))

    t1 = time.time()
    for n in range(i):
       n=n
    t2 = time.time()
    time_for.append(round(t2-t1,5))

x=["200k","300k","400k","500k","600k","700k","800k","900k","1Mio",]
plt.plot(x, time_while,label="while")
plt.plot(x, time_for,label="for")
plt.legend()
plt.show()

Answer 1

通过稍微修改您的代码，在每个循环中添加一个小的求和，我延长了计算时间，并且就您的核心可用容量的小波动而言，结果将更加稳定。通过这种方法，您可以清楚地看到预期的线性度。

剧情是这样的

你可以看到下面使用的代码

import time
import matplotlib.pyplot as plt

time_while=[]
time_for=[]
for i in range(200000, 1000000+1, 100000):
    t1 = time.time()
    n = 0
    while n < i:
        sum(k for k in range(10))
        n += 1
    t2 = time.time()
    time_while.append(round(t2-t1,5))

    t1 = time.time()
    for n in range(i):
        sum(k for k in range(10))
        n=n
    t2 = time.time()
    time_for.append(round(t2-t1,5))

x=["200k","300k","400k","500k","600k","700k","800k","900k","1Mio",]
plt.plot(x, time_while,label="while")
plt.plot(x, time_for,label="for")
plt.legend()
plt.show()

在 python 中的线性时间 O(n) 中既没有 for 也没有 while 循环运行

Neither for nor while loop run in linear time O(n) in python

python

loops

for-loop

runtime

while-loop

在 python 中的线性时间 O(n) 中既没有 for 也没有 while 循环 运行

Neither for nor while loop run in linear time O(n) in python

python

loops

for-loop

runtime

while-loop

在 python 中的线性时间 O(n) 中既没有 for 也没有 while 循环运行