为什么备忘录不能改善合并排序的运行时间? [英] Why does memoization not improve the runtime of Merge Sort?

问题描述

为什么备忘录不能改善合并排序的运行时间?

Why does memoization not improve the runtime of Merge Sort?

我在分配"任务中有这个问题.但是据我所知，合并排序使用分而治之的方法(没有重叠的子问题)，但是记忆化是基于动态编程(具有重叠的子问题)的.我知道合并排序的运行时是O(nlogn).

I have this question from Assignment task. But as far as I know, Merge Sort uses divide and conquer approach (no overlapping subproblems) but Memoization is based on dynamic programing (with overlapping subproblem). I know the runtime of Merge Sort is O(nlogn) .

我什至在网络搜索引擎上进行了搜索，但这个问题没有任何结果.这个问题错了吗?如果听起来不对，那么教授为什么要在作业中提出错误的问题? 如果问题没有错，或者我对问题的理解(合并排序和记忆化是错误的)，我应该如何回答这个问题?

I even searched on web search engines and there is no result for this question. Is this question wrong? If it sounds wrong but why would a professor give a wrong question in assignment? If the question is not wrong or my understanding about the question, Merge Sort and Memoization is wrong, How should I answer this question?

推荐答案

您已经给出了问题的答案. 记忆化意味着在解决问题后写备忘录，以便当我们再次遇到问题时，我们使用备忘录而不是再次解决相同的问题.

You have already given the answer in the question. Memoization implies writing a memo after solving a problem, so that when we encounter the problem again, we use the memo instead of solving the same problem again.

由于在mergesort中，问题不会重叠，因此写备忘录是没有用的.

Since in mergesort, the problems don't overlap, writing a memo is of no use.

这篇关于为什么备忘录不能改善合并排序的运行时间?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！