algorithm - 如果删除“LINE 3”，fib(n) 需要多少额外的函数调用？

Question

我刚在面试中得到这个问题，不知道如何计算答案。
如果删除“LINE 3”，fib(n) 需要多少额外的函数调用？答案应该是关于 n 的。

int fib(int n) {
  if(n == 0) return 0;
  if(n == 1) return 1;
  if(n == 2) return 1; //LINE 3 HERE <---

  return fib(n - 1) + fib(n - 2);
}

Answer 1

它可以很容易地计算出来。旧代码：

TO(0)=TO(1)=TO(2)=1
TO(n)=TO(n-1)+TO(n+2)+1

新代码：

TN(0)=TN(1)=1
TN(n)=TN(n-1)+TN(n-2)+1

只需减去这两者即可计算出差异：

D(0)=D(1)=0
D(2)=3-1=2
D(n)=TN(n)-TO(n)=TN(n-1)+TN(n-2)+1-(TO(n-1)+TO(n+2)+1)
    =(TN(n-1)-TO(n-1))+(TN(n-2)-TN(n-2))+(1-1)
    =D(n-1)+D(n-2)

这意味着差异是以 0,0,2 开头的斐波那契数列。也可以为它计算一个封闭形式的表达式。

Answer 2

所需的额外调用次数也是斐波那契数列。

0 0 2 2 4 6 10 16 26 42 68 110 178 288 466

#include<iostream>
using namespace std;

int a = 0;
int b = 0;

int fib(int n) {
    a++;
  if(n == 0) return 0;
  if(n == 1) return 1;
  if(n == 2) return 1; //LINE 3 HERE <---

  return fib(n - 1) + fib(n - 2);
} 

int fib1(int n) {
    b++;
  if(n == 0) return 0;
  if(n == 1) return 1;

  return fib1(n - 1) + fib1(n - 2);
}

int main(int argc, char* argv[])
{
    for(int i =0 ;i<15;i++)
    {
        fib(i);
        fib1(i);

        cout<<b-a<<" ";

        b = a = 0;
    }
}

注意：我认为这将是一些恒定的，但......

Answer 3

让我们假设没有第 3 行并计算 f(3)：

f(3) = f(2) + f(1)
f(1) = 1
f(2) = f(1) + f(0)
f(0) = 0
f(1) = 1

现在需要 3 次调用来计算 f(2)。如果有第三行，那么这将在 1 次调用中完成。

这个算法的复杂度（没有第 3 行）是O(2^n). 当您添加第 3 行时，其中包含针对n = 2复杂性变为O(2^(n-1))等于(1/2) * O(2^n)=kO(2^n)其中系数 k = 0.5 的情况的显式解决方案。如果为 n = 3 的情况添加显式解决方案，则得到 k = 0.25，依此类推。当您添加p显式解决方案时，复杂性将是：

    1
O (--- * 2^n)
   2^p 

这意味着如果您将计算 n 从 1 到 n 的答案，并且如果您将保存所有计算出的解决方案，那么您将获得p = n - 1每个n步骤的算法和复杂性2*O(n)。