rob*_*hal 4 algorithm mergesort memoization dynamic-programming
为什么memoization不会改善Merge Sort的运行时间？
我从分配任务中得到了这个问题.但据我所知,Merge Sort使用分而治之的方法(没有重叠的子问题),但Memoization基于动态编程(具有重叠的子问题).我知道Merge Sort的运行时是O(nlogn).
我甚至在网络搜索引擎上搜索过,这个问题没有结果.这个问题有误吗？如果听起来不对,但为什么教授会在作业中提出错误的问题？如果问题没有错或我对这个问题的理解,合并排序和记忆是错误的,我该如何回答这个问题？
你已经在问题中给出了答案.Memoization意味着在解决问题后编写备忘录,这样当我们再次遇到问题时,我们会使用备忘录而不是再次解决相同的问题.
因为在mergesort中,问题不重叠,写备忘录是没有用的.