時間：1時間34分13秒 vs メモリ：10 388 MB

動的プログラミングを使用して解決される多くのタスクは、メモリに容赦ありません。 多くの場合、 O（n⋅m）値を保存する必要があります。nとmが大きい場合、これは実際の問題になります。 この記事では、作業時間によってメモリを節約する比較的一般的な方法について説明します。

定義と表記

<k、path（k）>という形式の回答が必要な問題があるとします。ここで、 kは結果であり、 path（k）はこの結果を達成するための可能な方法の1つです。 さらに、 kはカーディナリティがnおよびmの 2つのセットAおよびBに依存し、 mおよびnの 線形再帰を使用して表現できます。 理解を深めるために、そのようなタスクの例を参照してください。 編集上の距離と処方を見つける問題について考えてみましょう。 ウィキペディアでそれについて^読むことができ、 ここでビジュアライザーを見ることができます ^{[ habraeffectに注意してください ]} 。 さらに、読者は何が起こっているのか理解していると思います。

明らかに、時間内に必要なものを取得するための最も最適な方法は、両方の引数で上向きのダイナミクスであり、すべてのn⋅m中間値を格納し、それぞれO（n⋅m）時間動作します。 利便性を高めるために、n = max（m、n） （はい、再割り当て。そうでなければ、常に混乱します）を設定すると、占有メモリの時間と量はO（n ² ）として推定できます。

機会：メモリは有限です！

nが9000を超える可能性があることを想像するために、多くの想像力を持つ必要はありません。 「数十ギガバイトのメモリを浪費する」という考えは、失敗する運命にあると推測するのに天才である必要はありません。 しかし、ここでは、原則として、通常、使用するよりもはるかに多くの時間があります。 この時点で、読者は上向きのダイナミクスが何であり、彼らがそれと共に何を食べているかを理解するとともに、線形再帰とは何かを理解する必要があります。 怠zyな人には別のオプションがあります：私の言葉を聞いてください:)明らかに、関数の次の値を計算するには、一定の（ほとんどの場合2に等しい）行数だけが必要です。これはO（n）を使用できるという明確なヒントですメモリ。 しかし、同時に、一定数の行のみを格納すると、遅かれ早かれ、新しいデータを計算するために古いデータを「忘れる」必要があります。 また、出力にはこの古いデータも必要になるため、再度読み取る必要があります。 簡単なアルゴリズムが判明します。

1. iPos = jPos = nに設定します。
2. 関数の値を（0,0）から（iPos、jPos）まで計算し、新しい行に移動するたびに、最も古い行を削除します（したがって、行数は一定になり、 kで表します）。
3. （iPos、jPos）に到達したら、（ iPos-k 、 k ' ）から（iPos、jPos）に到達するために必要なステップを思い出してください。
4. iPos = iPos-k 、 jPos = k 'に設定します。
5. iPosとjPosがゼロ（またはそれ以下）でない場合は、手順2に戻ります
6. 見つかった値とパス

上記のリンクを使用して編集距離と処方箋を検索する例を使用すると、このアルゴリズムの動作を確認できます。

アルゴリズムがO（n ³ ）に対して機能することは簡単にわかりますが、 O（n）メモリのみを消費します。

可能なオプション

確かに多くの人が疑問に思っていました：「間に何かをすることは可能ですか？」はい、できます。 O（√n⋅n）メモリとO（√n⋅n2）時間から始めましょう。 実際、ここでの変更は重要ではありません。最後のk行を保存する代わりに、 √nを保存します（ピッキーの場合： nが小さい場合は max（k、√n） ） 。 これにより、消費されるメモリは√n倍増加しますが、それに応じて、時間は減少します： n ³ /√n=√n⋅n2 。 少し考えれば、∀ε∈[0,1]はO（n ^{2 +ε} ）時間とO（n2 ^-ε ）メモリを消費することで問題を解決できることを理解できます。 ε= 0.5の可視化は、同じビジュアライザーで利用できます。

あとがき

編集距離と処方を見つけるタスクの実例は、ビジュアライザーの横とミラーにあります。 Java Coding Conventionsについて話す必要はありません。問題とは何の関係もないからです。

頑張って :)