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))。在叶子上方的节点向下 - 一半的节点存在 - 叶子在第一次内循环迭代中被击中。

“精确”推导

挥挥手，当算法正在查看具有 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

最后一行是对一般形式的猜测。您可以验证它之前的所有特定行是否“有效”，然后可以直接通过归纳来证明它。

因此，N = 2**k - 1，

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

这表明 T(N) 受 C*N 限制，所以 O(N) 也是如此。