通过归纳法证明函数被调用 n-1 次

Question

这是问题的伪代码：

Procedure Foo(A,f,L)，前提条件：

代码

procedure Foo(A,f,L
    if (f=L) then

      return A[f]

    else

       m <-- [(f+L)/2]

       return min(Foo(A,f,m), Foo(A, m+1,L))

    end if

问题:

使用归纳法，证明 Foo 最多调用 min n-1 次。

我对如何继续第 (iii) 部分的证明有点迷茫。我已经写出了索赔和基本案例。我认为它是 n>=2。但是我该如何处理 k + 1 个术语呢？因为这是归纳证明。

谢谢

Answer 1

我们将在 n = L - f + 1 进行归纳。

基本情况：当 n = 1、f=L 并且我们立即 return A[f] 调用 min 零次时；我们有 n - 1 = 1 - 1 = 0.

归纳假设：假设声明对所有 n 直到并包括 k - 1 都是正确的。

归纳步骤：我们必须证明 k 的声明是正确的。由于 L > f 我们执行第二个分支调用 min 一次，并在大小为 floor(k/2) 和 ceiling(k/2).

的子数组上调用 Foo

如果k是偶数，k/2是整数，floor(k/2) = ceiling(k/2) = k/2。这两个都小于 k，因此我们知道 Foo 每次调用至少调用 min 次 k/2 - 1 次。但是2(k/2 - 1) + 1 = k - 2 + 1 = k - 1，所以n = k.

k - 1

如果 k 是奇数，k/2 不是整数并且 floor(k/2) = ceiling(k/2) - 1。对于 k > 1，这两个都小于 k，因此我们知道每个递归调用分别调用 min 至少 floor(k/2) - 1 和 ceiling(k/2) - 1 次。但是floor(k/2) - 1 + ceiling(k/2) - 1 + 1 = floor(k/2) - 1 + floor(k/2) + 1 = 2*floor(k/2) - 1 + 1 = 2*floor(k/2)。因为k是奇数，所以k/2可以写成w+1/2，其中w = floor(k/2)。重新排列，我们有 k = 2w + 1 并且我们调用 min 至少 2*w 次。但是k - 1 = 2*w + 1 - 1 = 2*w = 2*floor(k/2)，按要求

因为 k 不是偶数就是奇数，并且我们已经证明在这两种情况下 min 的最小调用次数至少是 k - 1，这就完成了证明。

Prooving by induction that a function gets called n-1 times