我一直在阅读Sedgewick&Wayne撰写的“Algorithms,4th Ed”,并且一直在实现JavaScript中讨论的算法。
我最近使用了本书中提供的mergesort示例来比较自上而下和自下而上的方法...但是我发现自下而上的运行速度更快(我认为)。在博客上查看我的分析。
-http://www.akawebdesign.com/2012/04/13/javascript-mergesort-top-down-vs-bottom-up/
我还没有找到任何讨论说合并排序的一种方法应该比另一种更快。我的实现(或分析)有缺陷吗?
注意:我的分析只测量算法的迭代循环,而不严格地是数组比较/移动。也许这是有缺陷的还是无关紧要的?
编辑:我的分析实际上并未计时速度,因此我对它运行“更快”的说法有点误导。 我正在通过递归方法(自上而下)和for循环(自下而上)跟踪“迭代”-自下而上似乎使用的迭代次数更少。
最佳答案
如果更快意味着您的“迭代次数”减少,那么可以。如果您想知道执行时间。
原因是这21,513次迭代中的某些迭代比22,527次迭代做得更多。
从源头上看,似乎图中的某些叶节点不是一起单独排序的,因此合并和排序的次数减少了,但花费的时间更长。