c - 调用另一个递归函数的递归函数的运行时分析

Question

int f(int x)
{
  if (x < 1) return 1;

  return f(x-1) + g(x);
}


int g(int x)
{
  if (x < 2) return 1;

  return f(x-1) + g(x/2)
}

f 的大 O 是什么？更重要的是，使用什么技术来计算此类问题的运行时间？

Answer 1

让我们写Cf(x) (resp Cg(x))调用f(x)时执行的加法次数(回复 g(x))。

首先，这两个函数都返回一些数字，这些数字是通过加法最终返回到 1 获得的。因此

Cf(x) = f(x) - 1
Cg(x) = g(x) - 1

所以让我们坚持使用 f 和 g。以下是前几个值:

[(f(i), g(i), 2^i) for i in range(10)]
[(1, 1, 1),
 (2, 1, 2),
 (5, 3, 4),
 (11, 6, 8),
 (25, 14, 16),
 (53, 28, 32),
 (112, 59, 64),
 (230, 118, 128),
 (474, 244, 256),
 (962, 488, 512)]

看起来是指数级的。此外:

f(x) = f(x-1) + g(x) 
     = 2*f(x-1) + g(x/2)

这清楚地表明

f(x) > 2*f(x-1) > 4*f(x-2) > 8*f(x-3) > 2^x. 

所以你很确定 f(x)是 O(2^x) , 实际上是一个 Theta(2^x) .

现在f(x) > 2^x和 f(x-1) <= g(x) <= f(x) .这样g和 f以同样的速度增长。结果 g(x/2)与 f(x) 相比完全可以忽略不计.这样

f(x) is a O(2^n)