performance - 再帰疑似コードの時間計算量

Question

擬似コードの時間計算量関数は何でしょうか?

int what(int k){
   if(k==0 || k==1) 
      return k;
   else 
      return what(k-1)*what(k-2);
}

Answer 1

k が増加するにつれて呼び出しの数は黄金比で (漸近的に) 増加しますが、これはフィボナッチ数列ではありません。0 から始まる n に対する what() の呼び出し回数は、1、1、3、5、9、15 です。同様に、関数 what(k) は k: -> Fib(k) です。

前に述べたように、複雑さは O(Fib(n)) のままであることがすべて明らかになりました。

Answer 2

その関数はフィボナッチ数列を計算しませんが、呼び出しの数はフィボナッチ数列です。

この関数は内部的に話す作業を行わないため、時間計算量は呼び出しの数と同じです。

だからですO(fib N)。

Answer 3

このコードの時間の複雑さはO(n!)だと思います。これは、呼び出しの数がk 個のインクリメントごとに乗算されるためです (これは非常に悪いことです)。

(冗談) でも良いニュースがあるよ! このコードは、常に 0 を返すため、O(1)に単純化できます。

int what(int k) { return 0; }