Mergesort - 递归调用的最大数量
Mergesort - maximum number of recursive calls
在中有一个计算长度为 32 的数组的合并排序递归调用次数的示例（最坏情况）：1 + 2 + 4 + 8 + 16 + 32 = 63。
很容易想象为什么会这样——在树的每一层我们都有 2 的幂节点并且我们总是进入下一层直到最后一层。
我想知道如何计算任意长度数组的这个数字（递归调用的最大次数）n？实际上，这个数字似乎是 2*n-1 但我不明白为什么。有人可以解释一下背后的逻辑吗？
让我们看看模式。
如果n = 1只有一个电话（与此无关）。
如果 n 为真，那么对于 2n，我们的第一个调用将其分为 n 和 n，我们分别在 [=15= 中排序] 呼吁 4n-2 更多。所以我们需要 1 + 4n-2 = 4n - 1 = 2*(2n)-1 并且结果成立。
如果 n 和 n+1 为真，那么 2n+1 我们的第一个调用将其分为 n 和 n+1。我们用另一个 2n-1 和 2(n+1)-1 = 2n+1 调用对它们进行排序。进行 1 + 2n-1 + 2n+1 = 4n + 1 = 2*(2n+1) - 1 次通话。
所以因为 1 为真，所以 2 为真。因为 1 和 2 为真，所以 3 为真。因为 2 为真，所以 4 为真。因为它为2 和 3 对 5 也是如此。依此类推。
你可以很容易地把它转过来，用强归纳法把它变成形式化的证明。
在
很容易想象为什么会这样——在树的每一层我们都有 2 的幂节点并且我们总是进入下一层直到最后一层。
我想知道如何计算任意长度数组的这个数字（递归调用的最大次数）n？实际上，这个数字似乎是 2*n-1 但我不明白为什么。有人可以解释一下背后的逻辑吗？
让我们看看模式。
如果n = 1只有一个电话（与此无关）。
如果 n 为真，那么对于 2n，我们的第一个调用将其分为 n 和 n，我们分别在 [=15= 中排序] 呼吁 4n-2 更多。所以我们需要 1 + 4n-2 = 4n - 1 = 2*(2n)-1 并且结果成立。
如果 n 和 n+1 为真，那么 2n+1 我们的第一个调用将其分为 n 和 n+1。我们用另一个 2n-1 和 2(n+1)-1 = 2n+1 调用对它们进行排序。进行 1 + 2n-1 + 2n+1 = 4n + 1 = 2*(2n+1) - 1 次通话。
所以因为 1 为真，所以 2 为真。因为 1 和 2 为真，所以 3 为真。因为 2 为真，所以 4 为真。因为它为2 和 3 对 5 也是如此。依此类推。
你可以很容易地把它转过来，用强归纳法把它变成形式化的证明。