这两种列表遍历方法之间是否存在时间复杂度差异

Question

时间复杂度有差异吗？还是它们是一样的？我不知道该怎么说。

list_of_dict = [{'name':'alan', 'age':5}, {'name':'alice', 'age':6}]
# first method
names = []
ages  = []
for i in range(len(list_of_dict)):
    names.append(list_of_dict[i]['name'])
    ages.append(list_of_dict[i]['age'])
# second method
names = [x['name'] for x in list_of_dict]
ages  = [x['age'] for x in list_of_dict]

如能就此问题提供任何协助或建议，将不胜感激。

Answer 1

就渐近时间复杂度而言，它们是相同的。

对于列表中的每个元素，这两种方法都需要恒定的字典访问（平均是恒定时间），因此两者都O(n)。

但是，如果您关心常量，则很难分辨，并且可能因不同的解释器而异，这可能会优化不同的东西。

Answer 2

除了理论复杂性之外，如果需要，您可以使用ipython来计时，或者使用来使用%timeit

第一种方法：10 loops, best of 3: 58.2 ms per loop

第二种方法：10 loops, best of 3: 56.3 ms per loop

它们非常接近，需要用更大的数据集进行检查。