为什么记忆化不能改善合并排序的运行时间？
我从分配任务中有这个问题。但据我所知，合并排序使用分而治之的方法(没有重叠的子问题)，但 Memoization 是基于动态编程(有重叠的子问题)。我知道合并排序的运行时间是 O(nlogn) 。
我什至在网络搜索引擎上搜索过，这个问题没有结果。这个问题有错吗？如果这听起来不对，但为什么教授会在作业中给出错误的问题？
如果问题没有错，或者我对问题的理解，Merge Sort and Memoization 是错误的，我应该如何回答这个问题？
最佳答案
您已经在问题中给出了答案。 Memoization 意味着在解决一个问题后写一个备忘录，这样当我们再次遇到问题时，我们使用备忘录而不是再次解决同样的问题。
因为在归并排序中，问题不会重叠，所以写备忘录是没有用的。