2

n ステップを実行するメソッドがあるとしますが、それは最悪のケースで n 回線形に呼び出されます。そのような場合、Big O は n*n になりますか? では、再帰呼び出しは通常、2 つの for ループと同様に n^2 ですか?

バイナリ フィボナッチなどのバイナリ再帰アルゴリズムを考えてみましょう。そのアルゴリズムの 1 回の呼び出しには n ステップかかりますが、n 回まで繰り返すことができるとしましょう。そのアルゴリズムの実行時間は 2^n でしょうか?

4

1 に答える 1