在 Python 中找到第 K 个最大元素的总体复杂度

Question

我正在解决这个 leetcode 问题 link，并使用 heapq 模块找到了一个惊人的解决方案，这个函数的运行时间非常少。这是下面的程序：

from itertools import islice
import heapq

def nlargest(n, iterable):
    """Find the n largest elements in a dataset.

    Equivalent to:  sorted(iterable, reverse=True)[:n]
    """
    if n < 0:
        return []
    it = iter(iterable)
    result = list(islice(it, n))
    if not result:
        return result
    heapq.heapify(result)
    _heappushpop = heapq.heappushpop
    for elem in it:
        _heappushpop(result, elem)
    result.sort(reverse=True)
    return result

print nlargest(5, [10, 122, 2, 3, 3, 4, 5, 5, 10, 12, 23, 18, 17, 15, 100, 101])

这个算法真的很聪明，你也可以在这里形象化LINK

但是我很难理解整个算法的时间复杂度。以上是我的分析，如有错误请指正！

时间复杂度：

result = list(islice(it, n)) - > O(n)

heapq.heapify(result) -> O(len(result)) 

for elem in it:
        _heappushpop(result, elem)  -> I am confused at this part

result.sort(reverse=True) -> O(len(result)*log(len(result)))

谁能帮我理解算法的整体时间复杂度。

Answer 1

所以这里有两个相关参数：n（return 的项目数），以及 M（数据集中的项目数）。

islice(it, n) -- O(n)
heapify(result) -- O(n), because len(result)=n
for elem in it: _heappushpop(result, elem) -- performing M-N times an operation of O(logn), because len(result) remains n, i.e. (M-N)*logn
result.sort(reverse=True) -- O(n*logn)

总体：

n + n + (M-n)*logn + n*logn

结果为 O(M*logn)。可以很容易看出占主导地位的部分是heappushpop循环（假设M>>n，否则这个问题就没那么有趣了，因为解决方案或多或少都简化为排序）。

值得指出的是，有 linear-time algorithms 可以解决这个问题，所以如果你的数据集很大，值得一试。

在 Python 中找到第 K 个最大元素的总体复杂度

Overall complexity of finding Kth Largest element in Python

python

algorithm

heap

time-complexity

heapsort