なぜメモ編集はマージソートのランタイムを改善しないのですか？

Question

なぜメモ変換はマージソートの実行時間を改善しないのですか？

私はこの課題を割り当てタスクから持っています。しかし、私が知る限り、Merge Sortは分裂と征服のアプローチ（重複する部分問題なし）を使用しますが、Memoizationは動的なプログラミングに基づいています（重複した部分問題あり）。私はマージソートの実行時間がO（nlogn）であることを知っています。

私はウェブ検索エンジンでも検索しましたが、この質問の結果はありません。この質問は間違っていますか？それは間違って聞こえるが、教授はなぜ授業で間違った質問をするのだろうか？ 質問が間違っていないか、質問についての私の理解、並べ替えとメモの結合が間違っている場合は、どうすればよいですか？

Answer 1

あなたはすでに質問に回答しています。 Memoizationは、問題を解決した後にメモを書き込むことを意味するので、問題が再び発生したときに同じ問題を再度解決する代わりにメモを使用します。

mergesortでは、問題は重複しないので、メモを書くことは役に立たない。

Answer 2

Memoizationは、後で使用するために高価な機能の結果が格納される技術です。マージソートは、問題をより重複しない小さな問題に分割する分割および征服アルゴリズムです。関数は重複していないので、呼び出されるのはたった1回であるため、後で使用される高価な関数呼び出しの出力を格納する必要がないため、memoizationを実際に使用することはできません。