c++ - 2つの入力の関数のT（n）実行時間

Question

2つの入力を持つ関数のT（n）実行時間（大きなO実行時間ではない）をどのように見つけますか？入力を「n」と見なしますか？

int h(int a, int b) {
  if (a > 0) {
    return h(a-1, a+b);
  } 
  else {
    return 0;
  }
}

score 3 · Accepted Answer

aこの場合、このアルゴリズムの長さはbに依存しないため、考慮する必要があります。

言い換えると、bに対して20000または-2を渡すことができ、時間に少しも影響を与えないため（実際の加算時間を無視してa+b）、計算でbを考慮する必要はありません。

より一般的なケースでは、入力がに依存している場合、a時間b計算量関数でこれを単純に説明します。言い換えれば、それはT(a, b)ただではないでしょうT(a)。

score 0 · Accepted Answer

この関数はaでのみ繰り返され、aは各ステップで1ずつ減少するため、線形の複雑さが生じます。したがって、答えはT（a）になります。

score 0 · Accepted Answer

すべての（a、b）ペアについて、関数値がゼロであるとすると（再帰は常にelseブランチで終了します）、コンパイラーは、コードを効果的に減らして全体を「0」に戻すのに十分賢い場合があります。そして、すべてのif / elseと再帰を除外すると、O（1）の複雑さと対応する実行時間が発生します。

3 に答える 3