如何使用数学归纳法证明merge是有效的？

Question

这是我的homework的链接。

我只是希望在merge的第一个问题上得到帮助，并将自己完成第二部分。我知道归纳的第一部分是证明算法对于最小的情况是正确的，如果X是空的，另一个是Y是空的，但我不完全理解如何证明归纳的第二步:显示合并是正确的，输入大小为k+ 1。

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

谢谢!

Answer 1

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

• Base情况：
• Inductive n= 1，1个元素的数组总是排序的；合并排序适用于n= 1,2，...，k
• Inductive ：n= k+1

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

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

@Edit:对不起，missread。对于合并部分：

在这里，我们将有一个多维归纳。

假设:输入数组X，Y已经排序

合并情况：

• Base size(X) (X) == 0 && size(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
• Inductive ((X)，m)，其中m= 1,2,3，...，l && size(X) >= 0
• Inductive step over X：n=k+ 1
• Inductive >= Y: m=l+1>=

对于X上的第一个归纳步骤，除了基本情况外，我们还有两种情况：

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

​

类似地，对于Y上的归纳步长：

• X1 >= Y1 => Y[1] ⊕ merge(X, tail(Y)) => this is true by our hypothesis(

(X)，l)`为真，我们将较小的元素放在前面

• X1< Y1 => X[1] ⊕ merge(tail(X), Y) =>这里我们有两个选择:size =>我们遇到一个基本情况因此这个情况被证明是递归的，我们进一步递归最终达到基本情况或merge(subarray(X), tail(Y))其中由我们的归纳证明

​

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