如何使用数学归纳证明合并工作？

Question

这是我作业的链接.

我只想帮助解决合并的第一个问题,我自己会做第二部分.我理解归纳的第一部分证明了算法对于最小的情况是正确的,即如果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.

@Edit:对不起,想念.对于合并部分:

在这里,我们将有一个多维感应.

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

• 基本情况:大小(X)== 0 && size(Y)> = 0 =>返回Y || size(Y)== 0 && size(X)> = 0 => X,这是正确的,因为X和Y都被排序并将排序的数组与空数组合并产生相同的非空数组
• X上的归纳假设:合并适用于合并(n,大小(Y)),其中n = 1,2,3,...,k && size(Y)> = 0
• Y上的归纳假设:合并适用于合并(大小(X),m),其中m = 1,2,3,...,l && size(X)> = 0
• X上的感应步骤: n = k + 1
• Y上的感应步长: m = 1 + 1

对于X的第一个诱导步骤,我们有2个案例,除了基本情况:

• X [1] <Y [1] => X[1] ? merge(tail(X), Y)=> merge(k, size(Y))根据我们对X的假设,这是正确的,我们将较小的元素放在前面,所以我们保持顺序
• 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个元素,因此其中一个最终会触及我们的基本情况