主定理：当f(n)包含log的负指数时会出现问题。

Question

7

我正在使用主定理计算以下函数的平均情况复杂度：

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

上面写着 不适用（f(n)和n ^{log _b a}之间存在非多项式差异） 此答案也支持这个答案。

然而，在这个视频中，讲师在12:26解决了同样的问题，他得出了答案。

Θ(nloglogn)

能有人解释一下哪一个是错误的，以及为什么吗？

- Varun Garg

2个回答

2

正如Matt Timmermans正确指出的那样，这个陈述并不是从主定理中推导出来的，但它确实可以从一个扩展版本的主定理中推导出来。

使用树方法直接解决这个问题相当简单。

从 T(n) = 2T (n/2)+ n / log n 开始：

简化后，第i级贡献了n / (log(n) - i)。

请注意，一共需要到达~log(n) - 1个级别才能到达一个常数。

因此，所有级别的总和为∑_{i = 0}^{~log(n) - 1}[n / (log(n) - i)] ~ n ∑_{i = 0}^k[1 / k]，

其中k = log(n)。

请注意，sigma是k阶调和级数，即Θ(log(k))。将k = log(n)设置为总共n Θ(log(log(n))) = Θ(n log(log(n)))。

- Ami Tavory

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Matt Timmermans · Accepted Answer

他们两个都是对的。PDF中的主定理不适用，但视频中的讲师正在使用一种扩展形式的主定理，涵盖了您的情况。

我找不到任何关于视频版本的好参考资料，而且这不是我学到的版本，但在这里有一个在线证明： http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/extended_master_theorem.pdf。