设计一个函数的恒定时间算法

Question

这个问题让我摸不着头脑：

函数G(m)定义如下：

a)若m <= 100，则G(m) = G(G(m + 11))

b)如果m> 100，则G(m) =m- 10

根据上面的问题，如何设计一个计算G(m)的常量时间算法？

Answer 1

(b)部分显然可以在固定时间内计算，假设m适合整数变量。

这个问题要求证明的棘手部分是(a)部分是恒定的。然后是O(1)时间。这可以使用数学归纳法或其他方式来完成。

归纳证明如下。

首先，根据定义，G(101)等于101 - 10 = 91。

对于90 <= n <= 100，它保存G(n) = G(G(n + 11))，其中n + 11 > 100。因此，它等于G(n + 11 - 10) = G(n+1)，即91。

由此，这十个方程式G(91 - 1) = 91，G(91 - (1 - 1)) = 91，...，G(91 - (1 - 10)) = 91都是真的。这是一般归纳的基础。

归纳步骤:假设对于从1到某个界限的所有数字i，G(91 - i) = 91，G(91 - (i - 1)) = 91，...，G(91 - (i - 10)) = 91都为真。

然后是G(91 - (i + 1)) = G(G(91 - i - 1 + 11)) = G(G(91 - (i - 10)))。从基本步骤中，我们知道G(91 - (i - 10)) = 91。在上面的方程式中插入这个，我们得到G(91)，它也是已知的91。由此可以得出，这个假设对i+1也是正确的。

因此，对于所有n >= 1，G(91 - n)等于91。归纳是被证明的。

在Python中计算G的常量时间算法的一个示例：

def G(m):
   if m > 100:
      return m - 10
   else:
      return 91