java - 再帰関数の時間計算量

Question

マトリックス（2次元配列[] []）を受け取り、この配列の変更オプションの動的配列を作成し、動的配列の各オプションの動的配列を再帰的に作成するJava関数があります。最終的に、N 個のオプションのうちの 1 つのオプションごとに、N 個の他のオプションが作成されます。 その時間複雑度の関数は T(n)=T(n)*n であると言われましたが、これは可能ですか? そして、ビッグオー記法での漸近的な時間の複雑さは何ですか?

Answer 1

再帰関係が T(n)=nT(n) の場合、再帰は停止しません。この再帰関係は、すべての副問題が元の問題と同じサイズであることを意味します。再帰関数では、すべての部分問題が元の問題と同じサイズである場合、それは再帰が終了しないことを意味します。あなたの質問から、あなたの関数は元の行列で一度機能し、次に最初の関数適用の結果で一度機能し、その後停止するように聞こえます。これは実際には再帰関数ではなく、時間の複雑さを計算するための再帰関係モデルに実際には適合しません。ただし、すべての計算を実際に合計するだけでよいため、時間計算量を計算するのも非常に簡単です。