在条件为O（n）或O（n^2）时调用max的列表理解BigO？

Question

写一个返回数组中第二大数的算法

a = [1, 2, 3, 4, 5]
print(max([x for x in a if x != max(a)]))
>> 4

我试图弄清楚这个算法是如何工作的，以及pythons的内部魔力是否能使其与编写一个线性算法一样高效，该算法只在列表上循环一次，并存储最高值和第二高值。

如果我错了请纠正我：

• 对max(a)的调用将是O（n）

• [x for x in a]也将是O（n）

python是否足够聪明来缓存max(a)的值，或者这意味着算法的列表理解部分是O（n^2）？

最后一个max([listcomp])将是另一个O（n），但它只在理解完成后运行一次，所以最终的算法是O（n2）？

内部是否有什么奇特的业务会缓存max(a)值，并导致该算法比O（n^2）更快地运行？

Answer 1

Would python be smart enough to cache the value of max(a) or would this mean that the list comprehension part the algorithm is O(n^2)?

不，因为正如MSeifert在评论中所说的，python不会对a进行假设，因此也不会缓存每次重新计算的max(a)的值。在

您可能需要考虑一个实现，它在一个过程中跟踪最大的两个项目。您需要编写一个显式的for循环并执行它。这里有一个来自^{}的有用链接（我推荐这个）。在

或者，您可以考虑复杂度仍然是线性的多个遍历。在

In [1782]: a = [1, 2, 3, 4, 5]

In [1783]: max(set(a) - {max(a)}) # 3 linear traversals
Out[1783]: 4

这里还有改进的余地，但是正如我所说，没有什么比显式的for循环方法更好的了。在

Answer 2

最简单的方法就是计时。考虑一下这个时间码：

for i in range(1, 5):
    a = list(range(10**i))
    %timeit max([x for x in a if x != max(a)])

^{pr2}$

每次将元素数乘以10，运行时就会增加100。几乎可以肯定O(n**2)。对于O(n)算法，运行时将随元素数线性增加：

for i in range(1, 6):
    a = list(range(10**i))
    max_ = max(a)
    %timeit max([x for x in a if x != max_])

4.82 µs ± 27.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
29 µs ± 161 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
262 µs ± 3.89 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
2.42 ms ± 13 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
24.9 ms ± 231 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

但我不确定算法是否真的能满足要求。考虑列表a=[1,3,3]，甚至heapq模块告诉我第二大元素是3（而不是1——算法返回的值）：

import heapq

>>> heapq.nlargest(2, [1,3,3])[0]
3