为什么通过插入比使用heapify更糟糕的元素来构建堆的运行时？
一生一世0521 发布于 2023-01-30 15:09在CLRS书中,通过自上而下的堆化构建堆具有复杂度O(n).也可以通过重复调用插入来构建堆,在最坏的情况下,插入具有复杂性nlg(n).
我的问题是:是否有任何见解为什么后一种方法的性能更差？
我问了这个问题,因为我觉得数学背后有简单的见解.例如,
quicksort,merge sort和heapsort都基于减少不必要的比较,但使用不同的方法.快速排序:平衡分区,无需将左子集与右子集进行比较.merge sort:简单地比较两个子数组中的两个最小元素.heapsort:如果A的值大于B,则A的值大于B的后代,无需与它们进行比较.
-
两者之间的主要区别在于它们的工作方向:向上(O(n log n)算法)或向下(O(n))算法.
在通过进行n次插入完成的O(n log n)算法中,每次插入都可能从(当前)堆的底部一直向上冒泡到一个元素.所以想象你已经构建了除最后一个完整层之外的所有堆.想象一下,每次在该层中插入时,插入的值都是最小的整体值.在这种情况下,您必须将新元素一直冒泡到堆顶部.在此期间,堆具有高度(大致)log n - 1,因此您必须执行的交换总数(大致)n log n/2 - n/2,给出运行时间Θ(n log) n)在最坏的情况下.
在通过一次构建堆完成的O(n)算法中,新元素被插入到各种较小堆的顶部,然后向下冒泡.直观地说,堆中的元素越来越少,越来越高,因此大部分工作都花在叶子上,这些叶子比较高的元素要低.
运行时间的主要区别与方向有关.在O(n log n)版本中,由于元素被冒泡,运行时受到从每个节点到树根的路径长度之和的限制,即Θ(n log n).在O(n)版本中,运行时受到从每个节点到树叶的路径长度的限制,这要低得多(O(n)),因此运行时间更好.
希望这可以帮助!
2023-01-30 15:12 回答
嘿嘿可爱无罪
京公网安备 11010802041100号