Python中的列表推导是否以内存高效的方式缩减？

Question

我刚开始学习Python，这是我第一次发帖，所以请多多包涵 :). 最近我在玩Python，想知道像下面这样的代码

max([x for x in range(25)]) 

会不会导致Python先创建一个包含所有元素的列表，然后再找出最大值，这样的时间复杂度是O(2n)？还是说它在遍历的时候就一直记录最大值，这样的时间复杂度是Θ(n)？另外，Python3中的range和Python2中的不同（因为它是一个可迭代对象），这会不会影响结果呢？

Answer 1

列表推导式总是会生成一个列表（除非出现错误）。在大多数情况下，建议使用生成器表达式来代替。

max(x for x in xrange(25))

Answer 2

你的例子会导致Python先把整个列表都构建出来。如果你想避免这个情况，可以使用生成器表达式来代替：

max((x for x in range(25)))

或者简单地：

max(x for x in range(25))

当然（在Python 2中），range本身会构建一个完整的列表，所以在这种情况下你真正想要的是：

max(x for x in xrange(25))

不过，关于所需的时间，这些表达式的复杂度都是一样的。重要的区别在于最后一个需要的空间是O(1)，而其他的需要O(n)的空间。