python - 遍历反向(列表)是否会增加我的函数的时间复杂度？

Question

简短而简单的问题。我一直在研究编码面试的时间复杂度，但找不到简明的答案。我知道这个问题存在于 SO 上。 What is the time complexity of Python List Reverse? .

Python 有两种循环遍历列表的方法。您可以循环遍历 list.reverse() 以时间复杂度 O(n) 将列表反转到位，也可以循环遍历 reversed(list)。我的问题是:使用 reversed(list) 是否也有 O(n) 的复杂性？

我可以想象两个可能的答案，要么它实际上颠倒了列表(在这种情况下我会说:是的，它确实添加了 O(n))或者它只是从另一边循环遍历列表(在这种情况下我会说，不:它没有)。谁能给我一个明确的答案？

Answer 1

与 Python 3 中的许多其他内置函数一样，reversed 内置函数返回一个迭代器，因此不会花费额外的 n 迭代。在处理大 O 符号时，这无关紧要，但您对因子感兴趣，所以不，

for i in reversed(my_list): 

恰好通过列表一次。这正是这些类型的辅助函数的意义所在。

注意你可以使用

for i in my_list[::-1]:

这是一种常见的迭代方式，但使用切片已经返回一个列表 - 与 my_list.reverse 非常相似，还有一个额外的 n。