如果“LINE 3”为0，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)。如果有第 3 行，那么这将在 1 次调用中完成。

该算法的复杂度（没有第三行）是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 

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