讨论从列表中获取N个最大元素的各种python方法的复杂度

Question

我知道有两种方法。第一个：文档在这里

heapq.nlargest(n, iterable, key=None)

以及使用 sorted 的第二种传统方法

sorted(iterable, key=key, reverse=True)[:K]

文档提到这两个是等效的。但是，我只是想知道两者的复杂度是否相同，或者第一种方法是否以较小的时间复杂度实现。

我记得在我的算法课程中，与对整个列表进行排序然后选择顶部 K 相比，从列表中获取前 K 个元素可以以较少的操作顺序完成。如果我错了，请纠正我

编辑：哪些标准 python 库可以在 O(N) 操作中执行此任务，或者我们可以从 python 中获得的最佳复杂度是多少？

Answer 1

我不是一个伟大的数学家，但我想这主要取决于两件事：

1. K 和可迭代长度之间的关系
2. 执行的 python 和 cpython 代码量之间的关系。

一般来说，你是对的，快速测试显示了数字上的差异：

>>> timeit(stmt='sorted(i)[-100:]', setup='from random import seed,random;seed(666);i=[random() for _ in range(10000)]', number=1000)
2.086820379132405
>>> timeit(stmt='heapq.nlargest(n, i)', setup='from random import seed,random;import heapq;seed(666);n=100;i=[random() for _ in range(10000)]', number=1000)
0.5397011679597199