首页 > 搜索 > 怎么比较算法的复杂度,计算方法

怎么比较算法的复杂度,计算方法

互联网 2020-10-20 16:18:57
在线算命,八字测算命理

我认为这个主题有几个问题:

你如何实现buildHeap所以它在O(n)时间运行?如何正确实现buildHeap在O(n)时间运行?为什么同样的逻辑不能使堆排序在O(n)时间而不是O(n log n)中运行?

通常,这些问题的答案集中在buildHeap和siftDown之间的区别。在buildHeap和siftDown之间做出正确的选择对于获得siftDown的O(n)性能至关重要,但无助于理解siftUp和heapSort之间的区别。 实际上,buildHeap和heapSort的正确实现仅使用siftDown.仅需要siftUp操作来执行对现有堆的插入,因此它将用于使用二进制堆实现优先级队列。

我写这篇文章来描述最大堆如何工作。 这是通常用于堆排序或优先级队列的堆类型,其中较高的值表示较高的优先级。 最小堆也很有用; 例如,当按升序检索具有整数键的项目或按字母顺序检索字符串时。 原则完全一样; 只需切换排序顺序即可。

heap属性指定二进制堆中的每个节点必须至少与其两个子节点一样大。 特别是,这意味着堆中的最大项目位于根。 向下筛选和筛选在相反方向上基本上是相同的操作:移动违规节点直到它满足堆属性:

buildHeap交换一个太小而其最大子节点(从而将其向下移动)的节点,直到它至少与它下面的两个节点一样大。buildHeap交换一个与其父级太大的节点(从而将其向上移动),直到它不大于其上方的节点。

buildHeap和siftDown所需的操作数与节点可能必须移动的距离成比例。 对于buildHeap,它是从树的底部开始的距离,因此siftDown对于树顶部的节点来说是昂贵的。 对于siftDown,工作与树顶部的距离成比例,因此siftUp对于树底部的节点来说是昂贵的。 虽然在最坏的情况下两个操作都是O(log n),但在堆中,只有一个节点位于顶部,而一半节点位于底层。 因此,如果我们必须对每个节点应用操作,我们更愿意buildHeap而不是siftDown。

buildHeap函数接受一组未排序的项并移动它们直到它们都满足堆属性,从而生成一个有效的堆。 使用我们描述的buildHeap和siftDown操作,siftDown可能采用两种方法。

从堆的顶部开始(数组的开头)并在每个项目上调用buildHeap。 在每一步中,先前筛选的项(数组中当前项之前的项)形成有效堆,并筛选下一项将其置于堆中的有效位置。 筛选每个节点后,所有项都满足堆属性。

或者,向相反方向前进:从阵列末端开始向前移动。 在每次迭代中,您将一个项目向下筛选,直到它位于正确的位置。

这两种解决方案都将产生有效的堆。 问题是:buildHeap的哪个实现效率更高? 不出所料,这是使用siftDown的第二个操作。

设h = log n表示堆的高度。 buildHeap方法所需的工作由总和给出

(0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (h * 1).

总和中的每个项具有给定高度处的节点必须移动的最大距离(底层为零,根为h)乘以该高度处的节点数。 相反,每个节点上调用buildHeap的总和是

(h * n/2) + ((h-1) * n/4) + ((h-2)*n/8) + ... + (0 * 1).

应该清楚的是,第二笔金额更大。 单独的第一项是hn / 2 = 1/2 n log n,因此该方法最多具有复杂度O(n log n)。 但是我们如何证明buildHeap方法的总和确实是O(n)? 一种方法(还有其他分析也有效)是将有限和转换为无限级数,然后使用泰勒级数。 我们可能会忽略第一项,即零:

Taylor series for buildHeap complexity

如果您不确定为什么每个步骤都有效,那么这个过程的理由是:

这些术语都是正数,因此有限和必须小于无限和。该系列等于在x = 1/2时评估的幂级数。对于f(x)= 1 /(1-x),该幂级数等于(恒定次数)泰勒级数的导数。x = 1/2在该泰勒级数的收敛区间内。因此,我们可以用1 /(1-x)代替泰勒级数,进行微分,并评估找到无穷级数的值。

由于无限和正好是n,我们得出结论有限和不大,因此是O(n)。

接下来的问题是:如果能够以线性时间运行buildHeap,为什么堆排序需要O(n log n)时间? 堆排序包括两个阶段。 首先,我们在阵列上调用siftDown,如果实现最佳,则需要O(n)时间。 下一步是重复删除堆中最大的项并将其放在数组的末尾。 因为我们从堆中删除了一个项目,所以在堆的末尾之后总是存在一个开放点,我们可以存储该项目。 因此,堆排序通过连续删除下一个最大项并将其放入从最后位置开始并向前移动的数组来实现排序顺序。 最后一部分的复杂性在堆排序中占主导地位。 循环看起来像这样:

for (i = n - 1; i > 0; i--) {arr[i] = deleteMax();}

显然,循环运行O(n)次(n-1确切地说,最后一项已经到位)。堆的buildHeap的复杂性为O(log n)。它通常通过删除根(堆中剩余的最大项)并将其替换为堆中的最后一项(即叶子)来实现,因此将其替换为最小项之一。这个新的root几乎肯定会违反堆属性,所以你必须调用siftDown,直到你将它移回到一个可接受的位置。这也具有将下一个最大项目移动到根目录的效果。请注意,与buildHeap相反,对于我们从树的底部调用siftDown的大多数节点,我们现在在每次迭代时从树的顶部调用siftDown!虽然树正在缩小,但它的收缩速度不够快:树的高度保持不变,直到您移除了节点的前半部分(当您完全清除底层时)。然后在下一季度,高度是h-1.所以第二阶段的总工作是

h*n/2 + (h-1)*n/4 + ... + 0 * 1.

注意开关:现在零工作情况对应于单个节点,h工作情况对应于节点的一半。 这个总和是O(n log n),就像使用siftUp实现的buildHeap的低效版本一样。 但在这种情况下,我们别无选择,因为我们正在尝试排序,我们要求下一个最大的项目被删除。

总之,堆排序的工作是两个阶段的总和:buildHeap的O(n)时间和O(n log n)按顺序删除每个节点,因此复杂度为O(n log n)。 您可以证明(使用信息理论中的一些想法),对于基于比较的排序,O(n log n)是您可能希望的最佳方式,因此没有理由对此感到失望或期望堆排序实现 O(n)时间限制为buildHeap。

免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多