1回答

liuyubobobo

2021-07-14

1 shiftDown 是 O(logn) 的。

2 这个问题我以前回答过一次，在这个课程找了半天没有找到，再回答一次。

==========

首先，需要明确一点：由于大O是指上界。所以，对于heapify的过程，你说复杂度是O(NlogN)的，从严格的数学定义的角度，是没有问题。从严格数学的角度，说快排是O(n^2)的，是没有问题的。只不过，我们一般说复杂度，更愿意说那个最紧的上界。对于快排来说，虽然O(n^2)也对，但是说O(nlogn)，这个上界比O(n^2)更紧，更能描述出快排的性能特征。同理，对于heapify的这个过程来说，O(N) 是一个比O(NlogN)更紧的上界。

如果简单直观理解的话，我们可以看出来，heapify的过程首先忽略了所有的叶子节点，所以近一半的节点没有考虑。对于考虑的所有结节（非叶子结点），也并不是每一个节点都需要logN次操作。最下面一排非叶子结点只需要1次操作；倒数第二层非叶子结点只需要2次操作，以此类推...，只有最后的根节点，需要logN次操作。所以整体远远小于N个节点需要操作，大多数需要操作的节点，操作数也远远小于logN次。

注意：这个过程不能证明heapify的时间复杂度要比O(NlogN)低，只是一个感性的理解：）

如果要严格的数学证明，会比较复杂。我在这个课程中提到过，由于严格的数学证明超出了这个课程的范畴了，所以大家根据这个感性的理解，记住：heapify的时间复杂度其实是O(N)的，是小于O(NlogN)的，就可以了：）比如在这个课程中，对于快排的时间复杂度是O(NlogN)如何理解，也是采用这种“直观”但不严谨的方式讲解的。具体也可以参考这个问答：https://coding.imooc.com/learn/questiondetail/15858.html 其中我也解释了为什么我要这么讲解：）

==========

不过既然你问到了，在这里简单相对严谨的推导一下。因为这个结论的推导，是比推导快排的时间复杂度简单的，毕竟，快排是一个随机算法：）

首先，我们需要推导出，倒数第h层的节点有多少个？答案是 n / 2^(h + 1) 这个级别的。这个结论很好验证，对于叶子节点，也就是倒数第0层，大致有n/2个；叶子节点的父亲节点，大致有n/4个，以此类推...

上面的解释，我也说了，倒数第1层，只需要1次操作；倒数第2层，只需要两次操作；当然，叶子节点是倒数第0层，不需要任何操作，也就需要0次操作。推而广之，倒数第h层，需要h次操作。

整体，所有倒数第h层节点需要的时间复杂度就是：（n / 2^(h + 1)）*O(h)；我们的heapify的过程，就是对这个式子，对所有的h求和。h的取值范围是从0到lgn。所以，我们heapify的过程的时间复杂度可以表达成下面的式子：

简单变形：

由于我们的大O考虑的是n趋于无穷的情况。我们这个式子中的求和，其实就是一个无穷数列的求和。数列的每一项为 h / 2^h。这是一个标准的几何数列求和公式微分后的形式，也有些学校可能在高数学习中会直接给出如下的公式：

我们要求的，是x = 1/2的情况下的结果，带入，就有：

综合，我们原始的复杂度表示，就有了：

我们推导出了，对于heapify的过程，时间复杂度是可以被O(n)限制住的。也就是O(n)是一个更紧的上界：）

继续加油！：）

2

1

慕无忌8153145

好的好的，谢谢老师的详尽证明！~~

2021-07-15

共1条回复