Python heapify()时间复杂度
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)？
回答 1
Stack Overflow用户
发布于 2018-08-08 05:35:56
它需要更仔细的分析，比如你将使用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)呢？这是免费的！一个只有一个元素的树已经是一个堆了--没有什么可做的。
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)当然也是如此。
https://stackoverflow.com/questions/51735692
复制相似问题
腾讯云开发者
