因此，我使用 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，说不。
然而，在这个视频中，教练在 12:26 解决了同样的问题，他给出了答案
Θ(nloglogn)
谁能解释哪一个是错的，为什么？
问问题
1749 次
2 回答
6
他们都是对的。PDF 中的主定理不适用，但视频中的讲师正在使用涵盖您的案例的主定理的扩展形式。
我在视频中找不到任何真正好的版本参考，这不是我学到的版本，但这里有一个在线证明：http: //homepages.math.uic.edu/~leon /cs-mcs401-s08/handouts/extended_master_theorem.pdf
于 2016-10-11T21:07:37.577 回答
2
正如马特·蒂默曼斯正确指出的那样，该陈述并非来自主定理，但它确实来自于它的扩展版本。
直接使用树方法解决这个问题非常简单。
从T(n) = 2T (n/2)+ n / log n开始：
级别 0 有 1 个值为n / log(n)的节点。
级别 1 有 2 个节点，每个节点的值(n / 2) / log(n / 2)。
...
第i层有2 i个节点，每个节点的值(n / 2 i ) / log(n / 2 i )
简化，级别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)))。
于 2016-10-11T18:53:03.813 回答