0

再帰的なソリューションが、レベルを戻す前に、たとえば〜N回連続して自分自身を呼び出すことになった場合、N回の呼び出しのそれぞれが一定量のスタックスペースを使用するため、スペース効率はせいぜいO(N)です。

これは、再帰関数内のコードが ~N 回実行される内部ループ コードに似ているため、時間効率もせいぜい O(N) であることを意味しますか?

4

3 に答える 3

2

@Benの答えに加えて、現在のスタックフレームが削除され、呼び出し先のスタックフレームに置き換えられる「末尾再帰」のケースもありますが、呼び出し元の最後のアクションが呼び出し先の結果を返す場合のみです。これにより、完全に関数型言語で実装すると、O(n) 時間関数に O(1) スペースが生じる可能性があります。

于 2012-07-07T22:53:42.257 に答える
1

いいえ、しかしあなたの観察にはいくつかの真実があります-基本的に、アルゴリズムを知っている場合（再帰的かどうか、2つを区別しないため;そして、それらを区別できるものは実際には何もありません。それはスタイルの問題です) 与えられた問題の空間複雑度は少なくともf(n)であり、時間複雑度も少なくとも でなければなりませf(n)ん。

于 2012-07-07T23:06:46.123 に答える
0

いいえ、再帰アルゴリズムの各ステップは O(1) よりも長くかかる可能性があるためです。各ステップに O(n) かかる場合、合計時間の複雑さは O(n^2) になります。

于 2012-07-07T22:51:14.463 に答える