标签: master-theorem

因此,在之前的考试中,我被要求在不使用主定理的情况下求解以下递推方程:

T(n)= 9T(n/3) + n^2

不幸的是,我无法在考试中弄明白,所以我使用硕士定理解决了它,所以我可以知道答案(当然,我对这个问题没有任何赞誉),现在我想知道如何在没有主人定理的情况下解决它,因为在期末考试中,会有类似的问题.

如果有人可以提供一步一步的解决方案(有解释),那就太棒了,谢谢!

为了这种关系

T(n)= T(n-1)+ T(n/2)+ n

我可以先解决得到O(n ^ 2)的项(T(n-1)+ n),然后求解项T(n/2)+ O(n ^ 2)？

根据主定理,它也给出O(n ^ 2)或者它是错的？

所以我使用Master定理计算以下函数的平均大小写复杂度:

T(n) = 2T (n/2)+ n/ log n

根据http://people.csail.mit.edu/thies/6.046-web/master.pdf问题7,

它说

不适用(f(n)和n ^{log _b}之间的非多项式差异^a)

这个答案也支持pdf,说NO.

然而,在这个视频教练在12:26解决了同样的问题,他出来了答案

?(nloglogn) 

任何人都可以解释哪一个是错的,为什么？

最近我一直在研究递归; 如何写它,分析它等等我曾经想过复发和递归是一回事,但是最近的家庭作业和测验中的一些问题让我觉得有一些细微的差别,"复发"是通往描述递归程序或函数.

直到最近,当我意识到有一些叫做"主要定理"的东西用来为问题或程序写出"重现"时,这对我来说都是非常希腊的.我一直在阅读维基百科页面,但是,像往常一样,事情的措辞是这样的,我并不真正理解它在谈论什么.我通过实例了解得更多.

所以,有几个问题:让我们说你再次发生这种情况:

r(n)= 2*r(n-2)+ r(n-1);
r(1)= r(2)= 1

事实上,这是主定理的形式吗？如果是这样,用语言来说,它是什么意思？如果你试图根据这种重复尝试编写一个小程序或一个递归树,那会是什么样子？我是否应该尝试替换数字,查看模式,然后编写可以递归创建该模式的伪代码,或者,因为这可能是主定理的形式,是否有更简单的数学方法？

现在,假设有人要求您查找由上一次重复创建的程序执行的添加次数的重复次数T(n).我可以看到基本情况可能是T(1)= T(2)= 0,但我不知道从那里去哪里.

基本上,我问的是如何从给定的重复发生到代码,反之亦然.由于这看起来像主要定理,我想知道是否有一种直截了当的数学方法.

编辑:好的,我已经查看了我过去的一些作业,找到了另一个我被问到的例子,"找到复发",这是这个问题的一部分,我遇到了麻烦.

以最佳方式描述以下程序片段中的添加操作数的重复(当使用l == 1和r == n调用时)

int example(A, int l, int r) {
  if (l == r)
    return 2;
  return (A[l] + example(A, l+1, r);
}

通用形式: T(n) = aT(n/b) + f(n)

所以我必须比较n ^ logb(a)和f(n)

如果n^logba> f(n)是案例1和T(n)=?(n^logb(a))

如果n^logba< f(n)是案例2和T(n)=?((n^logb(a))(logb(a)))

那是对的吗？或者我误解了什么？

案例3怎么样？适用时？

我很沮丧.

在CLRS第3版,第95页(第4.5章)中,它提到了像

T(n) = 2T(n/2) + n lg n

无法用大师定理解决因为差异

f(n)/n^(log_b(a)) = (n lg n)/n^1 = lg n

不是多项式.

但后来我遇到喜欢的网页这样这个地方,在页面的底部,它提到的完全一样的复发和说,它是能够与主定理,因为它属于一种"扩展的情况下2"来解决,即使不同的是非多项式.它变为n lg^2 n(将对数因子f(n)加1).

然后,我遇到类似的网页这其中,例如,在(E)好像扩展案例2(复发是明确的应用T(n) = 4T(n/2) + n^2 lg n),但随后的解决方案是不是n^2 log^2 n,而是n^2 log n!我错了还是纸张错了？

任何人都可以清理矛盾,并清楚地说明何时可以使用主定理,何时不能使用？什么时候多项式差异检查很重要,什么时候不重要？扩展案例2是否可用,或实际上是否违反了某些内容？

编辑:

我尝试直接从第二篇论文解决复发(e),我得到:

T(n) = n^2 lg^2(n)/2 + n^2 lg(n)/2

这不是大the n^2 lg^2 n？

我在尝试理解原因时遇到一些问题

T(n)=16T(n/4)+n！

被认为

\xce\x98(n!)

我在这里使用下面的主定理：

https://www.geeksforgeeks.org/advanced-master-theorem-for-divide-and-conquer-recurrences/

这里令人困惑的部分是我的朋友说答案实际上是 O(n!) 而不是 \xce\x98(n!)...所以我真的很困惑。

递归关系

T(n)= 2T(n/2)+ n lg lg n

(其中lg是对数2的对数)可以使用主定理来解决,但我不是很确定答案.我找到了答案,但为了防止信息级联,我在这里没有提到它.请帮我找到上面的大O和Ω.

我正在学习数据结构和算法课程,我坚持这个递归方程式:

T(n) = logn*T(logn) + n

显然这不能通过使用主定理来处理,所以我想知道是否有人有任何解决这个递归方程的想法.我很确定它应该通过改变参数来解决,比如考虑n为2 ^ m,但我无法找到任何好的修复.

这个公式是主定理中的情况 2 吗

T(n) = 2 * T(n/2) + 3

a = 2; b = 2; (f(n) = 3^1) ?

所以 logba = 1 且 c = 1 在这种情况下是主定理情况 2 吗？或者我应该忽略常量 3。