Python heapify() 时间复杂度

Question

def heapify(A):
    for root in xrange(len(A)//2-1, -1, -1):
        rootVal = A[root]
        child = 2*root+1
        while child < len(A):
            if child+1 < len(A) and A[child] > A[child+1]:
                child += 1
            if rootVal <= A[child]:
                break
            A[child], A[(child-1)//2] = A[(child-1)//2], A[child]
            child = child *2 + 1

这是 python heapq.heapify() 的类似实现。在文档中说这个函数在 O(n) 中运行。但它看起来像 n/2 元素，它执行 log(n) 操作。为什么是 O(n)？

Answer 1

这需要更仔细的分析，例如您会 find here。基本的认识是只有堆的根实际上有深度log2(len(a))。在叶子上方的节点向下 - 一半的节点存在 - 在第一次内循环迭代时命中叶子。

"Exact"推导

挥挥手，当算法查看具有 N 个元素的子树的根节点时，每个子树中大约有 N/2 个元素，然后它需要按比例工作到 log(N) 将根和那些子堆合并为一个堆。所以总共需要的时间T(N)大约是

T(N) = 2*T(N/2) + O(log(N))

这是一种罕见的复发。但是 Akra–Bazzi method 可以用来推断它是 O(N)。

我认为从头开始推导出一个精确的解决方案能提供更多信息，当然也更令人满意。为此，我将只讨论完整的二叉树：在每一层都尽可能完整。那么一共有2**N - 1个元素，所有的子树也是完全二叉树。这回避了关于在事情不完全平衡时如何进行的大量毫无意义的细节。

当我们查看具有 2**k - 1 个元素的子树时，它的两个子树各有 2**(k-1) - 1 个元素，并且有 k 个级别。例如，对于具有 7 个元素的树，根部有 1 个元素，第二层有 2 个元素，第三层有 4 个元素。在子树堆化之后，根必须移动到位，将其向下移动 0、1 或 2 层。这需要在级别 0 和级别 1 之间进行比较，并且可能还需要在级别 1 和级别 2 之间进行比较（如果根需要向下移动），但仅此而已：所需的工作与 k-1 成正比。总而言之，

T(2**k - 1) = 2 * T(2**(k-1) - 1) + (k - 1)*C

对于某个常量 C 界定在一对相邻级别比较元素的最坏情况。

那T(1)呢？那是免费的！只有 1 个元素的树已经是堆 - 无事可做。

T(1) = 0

在树叶之上一层，树有 3 个元素。将最小的（对于最小堆；最大的对于最大堆）移动到顶部的成本（不超过）C。

T(3) = C

树的上一层有 7 个元素。堆化每个子树的成本 T(3)，然后将根移动到位的成本不超过 2*C：

T(7) = 2*C + 2*C = 4*C

以同样的方式继续：

T(15) = 2* 4*C + 3*C = 11*C
T(31) = 2*11*C + 4*C = 26*C
T(63) = 2*26*C + 5*C = 57*C
...
T(2**k - 1) = (2**k - k - 1)*C

最后一行是对一般形式的猜测。您可以针对它之前的所有特定行验证"it works"，然后通过归纳法证明它很简单。

所以，N = 2**k - 1，

T(N) = (N - log2(N+1)) * C

这表明 T(N) 受 C*N 的约束，因此 O(N) 也是如此。

Python heapify() 时间复杂度

Python heapify() time complexity

python

python-3.x

python-2.7

heap

heapq

"Exact"推导