algorithm - 我如何证明以下算法？

Question

Exp(n)
  If n = 0
    Return 1
  End If
  
  If n%2==0
    temp = Exp(n/2)
    Return temp × temp
  Else //n is odd
    temp = Exp((n−1)/2)
    Return temp × temp × 2
  End if

我如何通过 n 中的强归纳证明对于所有 n ≥ 1，Exp (n) 的乘法次数≤ 2 log2 n。

ps: Exp(n) = 2^n

Answer 1

一个简单的方法是使用强归纳。

• 首先，证明Exp(0)终止并返回2^0。

• 令 N 为任意偶数非负数。

• 假设函数Exp正确计算并返回[0, N] 中2^n的每一个。n

• 在这个假设下，证明Exp(N+1)andExp(N+2)都终止并正确返回2^(N+1)and 2^(N+2)。

你完成了！通过归纳，对于任何非负数N，Exp(N)正确返回2^N。

PS：请注意，在这篇文章中，2^N表示“2 的 N 次方”而不是“2 和 N 的二进制表示的按位异或”。

Answer 2

该程序完全应用以下重复：

P[0] = 1
n even -> P[n] -> P[n/2]²
n odd  -> P[n] -> P[(n-1)/2]².2

1. 程序总是终止，因为 forn>0和n/2and(n-1)/2 < n递归调用的参数总是减少。

2. P[n] = 2^n是递归的解。的确，

• n = 0 -> 2^0 = 1
• n = 2m -> 2^n = (2^m)²
• n = 2m+1 -> 2^n = 2.(2^n)²

这涵盖了所有情况。

由于每次调用都会将有效位数减一并n执行一两次乘法，因此总数不超过有效位数的两倍。