为什么回忆录不改进合并排序的运行时？

Question

为什么回忆录不改进合并排序的运行时？

我有个作业任务的问题。但据我所知，合并排序使用分而治之的方法(没有重叠子问题)，但记忆是基于动态规划(带有重叠子问题)。我知道合并排序的运行时是O(nlogn)。

我甚至在网络搜索引擎上搜索，这个问题没有结果。这个问题是错的吗？如果这听起来不对，但为什么教授会在作业中提出一个错误的问题？如果问题没有错，或者我对问题的理解，合并排序和记忆是错误的，我该如何回答这个问题？

Answer 1

你已经在问题中给出了答案。记忆意味着在解决问题之后写一份备忘录，所以当我们再次遇到问题时，我们使用备忘录而不是再次解决相同的问题。

因为在合并中，问题没有重叠，写一份备忘录是没有用的。

Answer 2

追忆是一种将昂贵功能的结果存储起来以供以后使用的技术。合并排序是一种分而治之的算法，它将问题划分为较小的不重叠子问题。由于函数是不重叠的，它们只被调用一次，因此回忆录不能真正用于优化它，因为它们不需要存储昂贵函数的输出，因此需要稍后使用它，因为它只被调用一次。