为函数设计恒定时间算法

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)等于G(n + 11 - 10) = G(n+1)，也就是91.

据此，G(91 - 1) = 91、G(91 - (1 - 1)) = 91、...、G(91 - (1 - 10)) = 91这十个等式全部成立。这是一般归纳的基础。

归纳步骤：假设 G(91 - i) = 91, G(91 - (i - 1)) = 91, ..., G(91 - (i - 10)) = 91 对于从 1 到某个界限的所有数字 i 都成立。

然后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

为函数设计恒定时间算法

Designing A Constant-Time Algorithm For A Function

algorithm

constant-time