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

差は、これら 2 つを差し引くだけで計算されます。

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

f(2) を計算するには 3 回の呼び出しが必要です。3 番目の回線があった場合、これは 1 回の呼び出しで行われます。

このアルゴリズムの複雑さ (3 行目なし) はO(2^n)です。n = 23 行目を追加すると、複雑さが=にO(2^(n-1))等しくなる場合の明示的な解が含まれます。ここで、係数 k = 0.5 です。n = 3 の場合に明示的な解を追加すると、k = 0.25 などになります。明示的なソリューションを追加すると、複雑さは次のようになります。(1/2) * O(2^n)kO(2^n)p

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

これは、1 から n までの n の答えを計算し、計算されたすべての解を保存するp = n - 1と、各nステップのアルゴリズムと複雑さが になることを意味します2*O(n)。