algorithm - 确定合并排序的调用(激活)次数

Question

我正在准备 CS 125 期末考试，其中(简要地)介绍了 Big O Notation。

鉴于:

• Mergesort 的最佳运行时间为 O(N lg(N))，最坏运行时间为 O(N lg (N))
• 有32个浮点值，初始顺序随机，存储在double数组中

如果要对数组进行排序，总共会有多少次合并排序调用(激活)？假设基本情况对单个值进行排序。

我会继续说简单地插入 32 到最坏的情况或最好的情况(因为合并排序保证 O(N lg (N))。

这没有给我正确的解决方案(显然是 31)。有人可以提供一些指示或解释吗？我只是看不到它。

Answer 1

由于 32 是 2⁵，因此递归树将是一个完整的二叉树。然后我们对 mergesort 进行 1 + 2 + 4 + 8 + 16 + 32 = 63 次调用。我不清楚为什么答案会是 31，当他们说基本情况是长度 1 时。显然他们不计算最后一级递归(或者他们假设当长度为 1 时你不递归)。

在您最初的尝试中，您将运行时间与递归调用混淆了。 Mergesort 的 O(n log n) 是算法进行的元素之间比较次数的上限。因为我们想要计算递归调用的次数，所以知道这个界限对我们没有任何好处(尽管知道算法如何工作)。