当我测量应该为 O(n) = n 的算法的运行时间时，我得到 O(n) = 1。我做错了什么？

Question

我正在自学数据结构，我正在尝试衡量将追加方法实现到数组数据结构的高效和低效方式之间的时间复杂度差异。也就是说，根据我在纸上做的一些数学计算，低效的方式应该是 O(n) = n^2，而有效的方式应该是 O(n) = n.

问题是，当我运行模拟并将两种情况绘制在图表上时，低效方式按预期执行，但高效方式执行 O(n) = 1。我在做什么吗错了？

import datetime
import time
import random
import matplotlib.pyplot as plt
import numpy as np

# Inefficient append
class PyListInef:
   
   
   def __init__(self):
       self.items = []
   
   def append(self, item):
       # Inefficient append -> appending n items to the list causes a O(n) = n^2, since for each i for i in 1, 2, 3...n 
       # we need i * k operations in order to append every element to the new list. Then, by weak induction we prove 
       # that the number of required operations is n(n+1)/2 which implies O(n) = n^2
       self.items = self.items + [item]
       
   # Using magic method for our PyList to be an iterable object.
   def __iter__(self):
       for c in self.items:
           yield c
           
# Efficient append:

class PyList:
   def __init__(self):
       self.items = []
   
   def append(self, item):
       self.items.append(item)
   
   def __iter__(self):
       for c in self.items:
           yield c

# The inefficient append running time

lst = PyListInef()

time_dict_inef = dict()
time_dict_ef = dict()

series = np.linspace(1, 301, 300)

   
time.sleep(2)
   
for i in range(300):
   starttime = time.time()
   for j in range(i):
       lst.append(series[j])
       
   elapsed_time = time.time() - starttime
   time_dict_inef[i] = elapsed_time * 100000
   
# The efficient append running time

lst = PyList()

time.sleep(2)

for i in range(300):
   starttime = time.time()
   for j in range(i):
       lst.append(series[j])
       
   elapsed_time = time.time() - starttime
   time_dict_ef[i] = elapsed_time * 100000

plt.figure(figsize = (14,7))
plt.plot(time_dict_inef.keys(), time_dict_inef.values())
plt.plot(time_dict_ef.keys(), time_dict_ef.values())
plt.xlabel('Number of elements to append')
plt.ylabel('Elapsed time (microseconds)')
plt.title('Comparison between efficient appending vs inefficient appending in a list data structure')
plt.show()

你能帮我指出我做错了什么吗？

Answer 1

time.time() 分辨率有限。您的“有效追加”时间足够快，通常在 time.time() 分辨率的单个滴答声之前完成。请注意两次在黄色图表中的准确显示方式：0 个跳动点和 1 个跳动点。图表右侧的 1-tick 时间更频繁，因为即使时间比单个 tick 短，更长的时间意味着 tick 在运行时发生的可能性更高。如果你运行有更大的输入，你最终会看到 2-tick 时间或更高。（另请注意，100000 中没有足够的 0，因此您的计时误差为 10 倍。）

当我测量应该为 O(n) = n 的算法的运行时间时，我得到 O(n) = 1。我做错了什么？

When i measure the running time of an algorithm that should be of O(n) = n, i am getting O(n) = 1. What am i doing wrong?

python

arrays

algorithm

big-o

data-structures

当我测量应该为 O(n) = n 的算法的 运行 时间时，我得到 O(n) = 1。我做错了什么？

When i measure the running time of an algorithm that should be of O(n) = n, i am getting O(n) = 1. What am i doing wrong?

python

arrays

algorithm

big-o

data-structures

当我测量应该为 O(n) = n 的算法的运行时间时，我得到 O(n) = 1。我做错了什么？