再帰アルゴリズムの空間複雑度

私はインタビューで、パイルドロムの問題を解決する効率的な方法を尋ねられました。等しくなるように私に= N/2と比較するi番目とn番目の文字を私から始まる再帰アルゴリズムの空間複雑度

= 0：
は、今私は2つのことを行うことができます。
再帰を使って、最初と最後が同じで、残りの文字列がpallindromeであるかどうかを調べることができます。

2番目は再帰的です。私の質問は、アルゴリズムの再帰型と非再帰型の空間の複雑さの違いは何ですか？

出典

2012-05-30 dharam

は基本的には、再帰的なアルゴリズムは、オーバーヘッドが追加されます

で読み取りを持っています。

しかし、再帰関数が呼び出しの最後の行（末尾再帰）である場合、追加のペナルティはありません。

もちろん、どちらのアルゴリズムも同じです。

出典

2012-05-30 17:22:42 Yannis

理論上、それらは同じ空間の複雑さを持ちます。 tail recursionを最適化できるかどうかによって大きく異なります。

もしそうなら、スタックはすべての再帰で置換されるので、ペナルティは発生しません。あなたが実行スタックで再帰呼び出しを保存するので

出典

2012-05-30 17:20:37

大きなデータセットの場合、テール再帰を使用しても、StackOverflowエラーが発生します。いいえ？ – Sudhakar

@Sudhakarそれはちょうど尾の再帰最適化が防止するものです。 –

このプログラムはテール再帰の有効な例ですか？これは、stackoverflowを生成します。私は間違っている場合、私は正しいことを教えてください。

 public class TailTest { \t public static void main(String[] args) { \t \t System.out.println(TailTest.iterate(100000)); \t } \t \t public static long iterate(int n){ \t \t if(n==1) return 1; \t \t \t \t return iterate(n-1); \t } }

– Sudhakar

再帰アルゴリズムの空間複雑度

答えて

関連する問題