ISRO | ISRO CS 2018 |问题53

考虑下面的C代码段

int f (int x)
{
      if (x < 1)  return 1;
      else return (f(x-1) + g(x))
}

int g (int x)
{
      if (x < 2) return 2;
      else return (f(x-1) + g(x/2));
}

以下哪一项最能描述f（x）作为x函数的增长？

（A） 线性的 （B） 指数型 （C） 二次的 （D） 立方体的 答复: （B） 说明： f（n）=f（n-1）+g（n）—1 g（n）=f（n-1）+g（n/2）—2

把g（n）的值放到方程1中， f（n）=2*f（n-1）+g（n/2）

我们可以推导出下面的方程， f（n）>2f（n-1） =>f（n）>2*2*f（n-2）–因为f（n）>2*f（n-1），所以，f（n-1）>2*2*f（n-2）。。。。等等 =>f（n）>（2^n）f（1）–这里的“^”表示指数。 所以，f（n）>θ（2^n）

所以，选项B是真的，f（x）的指数增长。 这个问题的小测验