algorithm - 如何证明递归算法的正确性

Question

// sorts the items from L[i] through L[j]
void threewaysort(int[] L, int i, int j) {
    if (L[i] > L[j]) swap (i, j);
    if (j - i + 1 > 2) {
        t = (j - i + 1) / 3;
        threewaysort(L, i, j - t);
        threewaysort(L, i + t, j);
        threewaysort(L, i, j - t);
    }
}

上面的代码是将列表l从最小排序到最大排序。为了证明这个算法是正确的，我想我们可以用归纳法吗提示是，调用 threewaysort(L, 0, L.length-1)实际上具有使l排序的副作用。
但我目前正处于归纳证明阶段。

Answer 1

你确实可以用归纳法。让我们用符号l i，j来表示子阵，子阵的项从l[i]到l[j]。
基本情况
这种归纳证明有两种基本情况：
j-i+1=1
这意味着Li，j中只有一个元素，因此它已经被排序条件都不是真的，所以什么都没有发生：Li，j在调用if之后被排序。
J-I+1=2
li，j中有两个元素。如果尚未排序，则第一个threewaysort(L, i, j)条件为true，调用if将有效排序li，j。第二个swap条件为false。所以Li，j在调用if
诱导步骤
我们到了j-i+1>2的情况
现在Li，j中至少有3个元素。通过归纳证明，我们假设threewaysort(L, i, j)对于较小的子阵正确工作。
我们暂时忽略athreewaysort可能被执行，而只关注第二个swap的主体，它将被执行：
保证t大于零。
有三个递归调用：在子数组li上，j-t，li+t，j，然后再次调用li，j-t。
让我们定义一下：
a=li，i+t-1
b=li+t，j-t
C=LJ-T+1，J
这些是不重叠的，相邻的li，j的范围。a和c的大小都是t。b的大小至少是t（可以是t，t+1或t+2）。
让我们定义加号来表示两个子数组的并集。那么li，j=a+b+c，递归调用实际上是对a+b，b+c，然后再对a+b进行排序。
由于t是严格正的，A+B和B+C是比A+B+C更小的子数组，因此我们可以假设这些递归调用成功地对相应的子数组进行排序（归纳前提）。
让我们看看a+b+c中的t最大值会发生什么。那些不在c中的值在第一次递归调用之后会在b中结束（记住b的大小至少是t）。因此，我们确定t的最大值都在b+c中，在第二次递归调用之后，我们可以确定所有这些t的最大值都只在c中找到。
类似的情况发生在A+B+C中的t最小值上。在第一次递归调用之后，它们中的任何一个都不能再出现在B中，但这并不是真正有用的在第二次递归调用之后，它们中的任何一个都不能在c中了。在第三次递归调用之后，它们中的任何一个也不能在B中，所以它们都在A中。
总结一下我们得到：
A被排序（因为在上次递归调用A+B被排序之后）
B排序（相同原因）
C被排序（因为在第二个递归调用B+C被排序之后，在第三个调用期间没有接触C）
A具有A+B+C中的最小值
C具有A+B+C中的最大值
B的剩余值来自A+B+C
这意味着a+b+c被排序。
这就完成了归纳证明。
更少的掉期
证明还表明，当数组大小与2不同时，交换是可选的。所以代码甚至是这样正确的：

void threewaysort(int[] L, int i, int j) {
    if (j - i + 1 > 2) {
        t = (j - i + 1) / 3;
        threewaysort(L, i, j - t);
        threewaysort(L, i + t, j);
        threewaysort(L, i, j - t);
    } else if (L[i] > L[j]) {
        swap(L, i, j);
    }
}

然而，执行原始代码中描述的交换平均将导致更少的交换（但更多的比较）。
时间复杂性
首先，我们注意到除了递归调用之外，所有其他语句都在恒定时间内执行。
其次，递归调用是在一个大小大约为三分之一的数组上进行的。
因此，当n=j-i+1时，递推关系为：
f（n）=3·f（（2/3）n）
F（2）=F（1）=1
如果我们扩展递归，我们得到：
f（n）=32·f（（2/3）2n）=…=3k·f（（2/3）千牛）
当k被选择为（2/3）kn=2（或1）时，我们知道f（（2/3）kn=1，这个因子可以从表达式中省略：
f（n）=3K
现在我们必须用n来表示k：
（2/3）千牛=2
k=对数3/2（n/2）
k=对数3（n/2）/对数3（3/2）
k=2.7对数3（n/2）
所以，现在我们有：
f（n）=3k
f（n）=（3log3（n/2））2.7
f（n）=（n/2）2.7
将时间复杂度设置为：
f（n）=o（n2.7）
…相当低效的排序算法；比气泡排序效率低。