如何使用数学归纳法证明合并有效？

Question

这是我 homework 的 link。

我只想帮助解决合并的第一个问题，我会自己做第二部分。我知道归纳的第一部分是证明算法对于最小情况是正确的，即如果 X 为空，另一个是如果 Y 为空，但我不完全理解如何证明第二步归纳：显示合并对于输入大小 k + 1 是正确的。

我以前在方程式上做过归纳，从来没有在算法上做过。

谢谢！

Answer 1

第一个假设：您使用的合并例程将两个排序数组合并为一个排序数组。 第二个假设：合并例程终止

• 基本情况： n = 1，始终对包含 1 个元素的数组进行排序
• 归纳假设： 合并排序适用于 n = 1,2,...,k
• 归纳步长： n = k+1

现在我们需要证明归纳步骤是正确的。

合并排序将数组拆分为两个子数组 L = [1,n/2] 和 R = [n/2 + 1, n]。根据上述事实，看到 ceil(n/2) 小于 k。根据我们的归纳假设，L 和 R 的合并排序结果都被正确排序（因为它们在 [1,k] 范围内）。此外，根据我们的假设，合并例程将它们合并到一个包含所有元素的排序数组中，因为 size(L) + size(R) = n 所以这意味着它正确地排序了一个大小为 n = k+1.

的数组

@编辑：抱歉，看错了。对于合并部分：

这里我们将进行多维归纳

假设：输入数组 X、Y 已经排序

• 基本情况： 尺寸（X）== 0 && 尺寸（Y）>= 0 => return Y || size(Y) == 0 && size(X) >= 0 => X，这是真的，因为 X 和 Y 都已排序，并且将已排序的数组与空数组合并会产生相同的非空数组
• X 上的归纳假设： merge 适用于 merge(n, size(Y))，其中 n = 1,2,3,...,k && size(Y ) >= 0
• Y 上的归纳假设： merge 适用于 merge(size(X), m) 其中 m = 1,2,3,...,l && size(X ) >= 0
• X 上的感应步长： n = k + 1
• 感应步过Y： m = l + 1

对于 X 上的第一个归纳步骤，我们有 2 个案例，除了基本案例：

• X[1] < Y[1] => X[1] ⊕ merge(tail(X), Y) => 这是真的，因为根据我们对 X 的假设 merge(k, size(Y)) 是真的，我们将较小的元素放在前面所以我们保持秩序
• X[1] >= Y[1] => Y[1] ⊕ merge(X, tail(Y)) => 这里我们有两个选择：
  • size(tail(Y)) = 0 => 我们遇到了一个基本案例，因此这个案例被证明是正确的
  • size(tail(Y)) > 0 => 我们进一步递归最终达到基本情况或 merge(tail(X), subarray(Y)) 其中 size(tail(X)) = k => 由我们的归纳假设
  证明

与 Y 上的归纳步骤类似：

• X[1] >= Y[1] => Y[1] ⊕ merge(X, tail(Y)) => this is true by our hypothesismerge(size(X), l)` 为真，我们将较小的元素放在前面
• X[1] < Y[1] => X[1] ⊕ merge(tail(X), Y) => 这里我们有两个选择：
  • size(tail(X)) = 0 => 我们遇到了一个基本案例，因此这个案例被证明是正确的
  • size(tail(X)) > 0 => 我们进一步递归最终达到基本情况或 merge(subarray(X), tail(Y)) 其中 size(tail(Y)) = l => 由我们的归纳假设
  证明

算法终止，因为在每一步我们都将其中一个数组缩小 1 个元素，因此其中一个最终会达到我们的基本情况