python - 在条件 : O(n) or O(n^2)? 中调用 max 的列表理解的 Big-O

Question

问。编写一个算法，返回数组中第二大的数

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

我正在尝试弄清楚这个算法是如何工作的，以及 python 的内部魔法是否会使它像编写线性算法一样高效，该算法只在列表 a 上循环一次并存储最高值和第二高的值。

如果我错了请纠正我:

• 调用 max(a) 的时间复杂度为 O(n)

• [x for x in a] 也是 O(n)

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

然后最后的 max([listcomp]) 将是另一个 O(n)，但这只会在理解完成后运行一次，因此最终算法将是 O(n^ 2)?

内部是否有任何奇特的业务可以缓存 max(a) 值并导致该算法比 O(n^2) 更快地运行？

Answer 1

找出答案的简单方法是计时。考虑这个时间代码:

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

17.6 µs ± 178 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
698 µs ± 14.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
61.6 ms ± 340 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
6.31 s ± 167 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Each time it multiplied the number of elements by 10 the runtime increased by 100. That's almost certainly O(n**2). For an O(n) algorithm the runtime would increase linearly with the number of elements:

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)

But I'm not certain the algorithm really does what is asked. Consider the list a=[1,3,3] even the heapq module tells me that the second largest element is 3 (not 1 - what your algorithm returns):

import heapq

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