确定合并排序的调用（激活）次数
Determining number of calls (activations) to mergesort
我正在准备 CS 125 期末考试，并且（简要地）涵盖了大 O 表示法。
鉴于：
- Mergesort 具有 运行 时间复杂度 O(N lg(N)) 的最佳情况和 运行 时间复杂度 O(N lg (N)) 的时间最坏情况
- 有 32 个浮点值，最初以随机顺序存储在双精度数组中
如果要对数组进行排序，总共会调用（激活）多少次归并排序？假设基本情况对单个值进行排序。
我会继续说简单地插入 32 到最坏的情况或最好的情况（因为合并排序保证 O(N lg (N))。
这没有给我正确的解决方案（显然是 31）。有人可以提供一些指示或解释吗？我就是没看到。
因为32是25，递归树就是一棵满二叉树。然后我们对 mergesort 进行 1 + 2 + 4 + 8 + 16 + 32 = 63 次调用。我不清楚为什么答案是 31，当他们说基本情况是长度 1 时。显然他们不计算最后一级递归（或者他们假设当长度为 1 时你不递归）。
在您最初的尝试中，您将 运行 时间与递归调用混淆了。 Mergesort 的 O(n log n) 是算法进行的元素 之间比较次数的上限。因为我们想要计算递归调用的次数，所以知道这个界限对我们没有任何好处（尽管知道算法 工作原理 是如何工作的）。
因此，mergeSort 方法执行拆分工作，merge 方法执行征服工作。
对于 32 的列表大小，我认为有 63 次 mergeSort 调用，即 2 * 32 - 1 = 63。并且有 31 次合并调用，即 32 - 1 = 31。
我正在准备 CS 125 期末考试，并且（简要地）涵盖了大 O 表示法。
鉴于：
- Mergesort 具有 运行 时间复杂度 O(N lg(N)) 的最佳情况和 运行 时间复杂度 O(N lg (N)) 的时间最坏情况
- 有 32 个浮点值，最初以随机顺序存储在双精度数组中
如果要对数组进行排序，总共会调用（激活）多少次归并排序？假设基本情况对单个值进行排序。
我会继续说简单地插入 32 到最坏的情况或最好的情况（因为合并排序保证 O(N lg (N))。
这没有给我正确的解决方案（显然是 31）。有人可以提供一些指示或解释吗？我就是没看到。
因为32是25，递归树就是一棵满二叉树。然后我们对 mergesort 进行 1 + 2 + 4 + 8 + 16 + 32 = 63 次调用。我不清楚为什么答案是 31，当他们说基本情况是长度 1 时。显然他们不计算最后一级递归（或者他们假设当长度为 1 时你不递归）。
在您最初的尝试中，您将 运行 时间与递归调用混淆了。 Mergesort 的 O(n log n) 是算法进行的元素 之间比较次数的上限。因为我们想要计算递归调用的次数，所以知道这个界限对我们没有任何好处（尽管知道算法 工作原理 是如何工作的）。
因此，mergeSort 方法执行拆分工作，merge 方法执行征服工作。
对于 32 的列表大小，我认为有 63 次 mergeSort 调用，即 2 * 32 - 1 = 63。并且有 31 次合并调用，即 32 - 1 = 31。