我知道有两种方法。第一个:文档是here
heapq.nlargest(n, iterable, key=None)
和第二种使用排序的传统方法
sorted(iterable, key=key, reverse=True)[:K]
文档中提到这两个是等价的。但是，我只想知道两者的复杂性是否相同，或者第一种方法的实现时间复杂度是否较低。
我记得在我的算法类(class)中，与对整个列表进行排序然后选择前 K 个元素相比，从列表中获取前 K 个元素可以以较少的操作顺序完成。 如果我错了请纠正我
编辑:哪些标准 python 库可以在 O(N) 操作中执行此任务，或者我们可以从 python 获得的最佳复杂度是多少？
最佳答案
我不是一个伟大的数学家，但我想这应该主要取决于两件事:
- K 与迭代器长度的关系
- 执行的 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
关于python - 讨论各种python方法从列表中获取N个最大元素的复杂性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45904437/