使用递归关系证明函数具有指数运行时？

Question

这是一个简单的C程序:

int f(int n) {
  if(n==0 || n==1) {
    return n;
  } else {
    return 2 * f(n - 1) + 3 * f(n - 2);
  }
} 

该程序具有指数时间复杂度.您可以在此函数调用图中看到f(5):

我想表明函数只使用递归方程具有指数复杂性,而不是通过绘制图表和计算函数调用的数量.

我想出的复发关系是

T(n)= T(n-1)+ T(n-2)+ c

扩展给出

T(n)= 2T(n-2)+ T(n-3)+ 2c

但是,我不知道如何进一步解决这个问题.我该如何解决这种递归关系？

Answer 1

对于初学者来说,你的复发需要某种基本情况,因为否则当你达到0时它是未定义的.为简单起见,让我们说

T(0)= a

T(1)= a + b

T(n + 2)= T(n)+ T(n + 1)+ c

让我们开始扩展这个重复的前几个术语:

• T(0)= a
• T(1)= a + b
• T(2)= 2a + b + c
• T(3)= 3a + 2b + 2c
• T(4)= 5a + 3b + 4c
• T(5)= 8a + 5b + 7c
• T(6)= 13a + 8b + 12c
• T(7)= 21a + 13b + 20c

这里有一个非常有趣的模式.让我们分别看一下a,b和c项的系数.a项的系数遵循模式

1,1,2,3,5,8,13,21 ......

这是Fibonacci系列,偏移了一步.b项的系数是

0,1,1,2,3,5,8,13 ......

这正是斐波那契系列.最后,我们来看看c术语:

0,0,1,2,4,7,12,20 ......

嗯,这看起来并不熟悉.但是,如果我们将其与条款并排放置,我们会看到:

a:1,1,2,3,5,8,13,21 ......

b:0,0,1,2,4,7,12,20 ......

请注意,b项是所有减去一项的条款!换句话说,它是斐波纳契系列向前移动一步,但每个项减去1.

根据这些观察结果,我们可以推测以下情况属实:

T(n)= aF _{n + 1} + bF _n + c(F _{n + 1} - 1)

我们现在可以通过归纳来证明这一点.作为我们的基本案例:

T(0)=α= 1A + 0B 0C + = 1A + 0B +(1 - 1)C =中国aF ₁ + BF ₀ + C(F ₁ - 1)

T(1)= A + B = 1A + 1B + 0C = 1A + 1B +(1 - 1)C =中国aF ₂ + BF ₁ + C(F ₂ - 1)

对于我们的归纳步骤,让我们假设对于某些自然数n,那个

T(n)= aF _{n + 1} + bF _n + c(F _{n + 1} - 1)

然后

T(n + 1)= aF _{n + 2} + bF _{n + 1} + c(F _{n + 2} - 1)

那我们就有了

T(n + 2)= T(n)+ T(n + 1)+ c

= aF _{n + 1} + bF _n + c(F _{n + 1} - 1)+ aF _{n + 2} + bF _{n + 1} + c(F _{n + 2} - 1)+ c

= A(F _{n + 1个} + F _{N + 2})+ B(F _ñ + F _{n + 1个})+ C(F _{n + 1个} + F _{N + 2} - 2 + 1)

= aF _{n + 3} + bF _{n + 2} + c(F _{n + 3} - 1)

这样就完成了归纳,所以我们的公式必须正确!

那么这与效率有何关系？好了,比奈的公式告诉我们那个F _ñ =Θ(φ ^ñ),其中φ是黄金比例(约1.61).这意味着

T(N)=中国aF _{N + 1} + BF _Ñ + C(F _{N + 1} - 1)=aΘ(φ ^Ñ)+Bθ(φ ^Ñ)+Cθ(φ ^Ñ)=Θ((A + B + C) φ ^ñ)

因此,只要一个+ B + C≠0,运行时间是Θ(φ ^Ñ),这是指数的.

希望这可以帮助!