在条件中调用max的列表理解的大O:O(n)还是O(n ^ 2)？

Question

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

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

我试图弄清楚这个算法是如何工作的,以及pythons内部魔术是否会使它像写一个线性算法一样高效,这个算法只是在列表上循环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)

每次将元素数乘以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