理解大师定理

Question

通用形式: 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怎么样？适用时？

Answer 1

注意:我知道回答这个问题为时已晚.我只是把它放在这里为后代:)

解决复发的主要定理

复发发生在解决复杂问题的分而治之的策略中.

它解决了什么？

• 它解决了形式T(n)= aT(n/b)+ f(n)的重现.
• a应该大于或等于1.这意味着问题至少减少到一次较小的子问题.至少需要一次递归
• b应大于1.这意味着在每次递归时,问题的大小都会减小到较小的大小.如果b不大于1,则意味着我们的子问题的尺寸不小.
• 对于相对较大的n值,f(n)必须为正.

考虑下面的图像:

让我们说我们有一个大小n的问题需要解决.在每个步骤中,问题可以分为子问题,并且每个子问题具有较小的尺寸,其中尺寸减小了b倍.

上述陈述用简单的词语表示大小为n的问题可以分成相对较小的n/b大小的子问题.

此外,上图显示,在我们多次划分问题的最后,每个子问题都会很小,以至于可以在恒定时间内解决.

对于以下推导,请考虑记录到基数b

让我们说H是树的高度,那么H = logn.叶数= a ^ logn.

• 第1级完成的工作总数:f(n)
• 在第2级完成的总工作:a*f(n/b)
• 第1级完成的总工作:a*a*f(n/b2)
• 最后一级完成的工作总数:叶数*θ(1).这相当于n ^ loga

主定理三例

情况1: 现在让我们假设操作成本在每个级别上增加一个重要因素,并且当我们到达叶级别时,f(n)的值变为多项式小于值n ^ loga.那么整体运行时间将主要由最后一级的成本决定.因此T(n)=θ(n ^ loga)

案例2: 让我们假设每个级别的操作成本大致相等.在那种情况下,f(n)大致等于n ^ loga.因此,总运行时间将是总水平数的f(n)倍.T(n)=θ(n ^ loga*logn)其中k可以> = 0.其中logn是树的高度,k> = 0

情况3: 让我们假设每个级别上的操作成本在每个级别上降低一个重要因子,并且到达叶级别时,f(n)的值变为多项式大于值n ^ loga.那么整体运行时间将主要由第一级的成本决定.因此T(n)=θ(f(n))

如果您对更详细的阅读感兴趣,也许还有一些实践的例子.您可以随时访问我的博客条目.解决复发的主要方法

Answer 2

我想你误会了. 如果n ^ logba> f(n)是情况1而T(n)=Θ(n ^ logb(a))

在这里你不应该担心f(n)你得到的结果是T(n)=Θ(n ^ logb(a)).f(n)是T(n)的一部分..如果得到结果T(n),那么该值将包括f(n).所以,没有必要考虑那一部分.

如果你不清楚,请告诉我.