python - 在 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(要返回的项目数)，以及 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，否则问题就不那么有趣了，因为解决方案或多或少地简化为排序)。

---

值得指出的是 l inear-time algorithms为了解决这个问题，所以如果你的数据集非常大，值得检查一下。