2

私はgeekforgeeksLongest Common Subsequenceでの問題の解決に関する記事を読んでいました。そこでは、2つの解決策があります。1つは再帰的で、もう1つは2次元配列によるDPを介したものです。DPソリューションは時間内にそれを実行しますが、再帰的ソリューションは時間内にそれを実行します。O(NM)O(2^N)

再帰的ソリューションの主な問題は、そこに示されているように、サブシーケンスのオーバーラップが発生することです。ただし、各ペアをハッシュに格納すると、次に関数の再帰でその値が必要になったときに、さらに再帰するのではなく、ハッシュから値を直接フェッチできます。では、この追加によって効率はどの程度向上するのでしょうか。来るのO(NM)でしょうか？

そして第二に、再帰的ソリューションはどうして時間を生み出すO(2^N)のでしょうか？このような再帰関数の複雑さを見つける方法、またはフィボナッチ数列などを見つける方法はありますか？

4

1 に答える 1

4

はい、ハッシュを使用するとそれが作成されO(NM)ます。この場合のプロセスは、メモ化と呼ばれます(はい、 はありませんr)。選択した言語で提供される実際のハッシュマップ コンテナーを使用しないように注意してください。単純な行列にしてください。現在のペアの値が の場合は-1再帰的に計算し、それ以外の場合は既に計算されていると仮定して返します。

2番目の質問については、数学的に実行して最適な境界を取得するか、リンクのように紙に描くことで「十分に良い」ものにすることができます。

                f(n)
               /    \
         f(n-1)      f(n-2)
        /     \        
  f(n-2)       f(n-3)
          ...

これは、次のようになることを帰納的に示唆するのに十分なはずですO(2^n)。ツリーの高さnは であり、各ノードには、問題をサイズnからサイズn - 1( になりますO(2^(n - 1)) に縮小する 2 つの再帰呼び出しがあります。ので、サイズn元の問題になりますO(2^n)。

フィボナッチが であると言っても間違いではありませんがO(2^n)、他の数学的手法を使用すると、より厳密な境界を得ることができることに注意してください。

于 2012-09-27T20:21:35.680 に答える