主定理：当 f(n) 包含对数的负幂时的问题
Master theorem: issue when f(n) contains negative power of log
所以我使用 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.
然而，在 this video 讲师在 12:26 解决了同样的问题，他给出了答案
Θ(nloglogn)
谁能解释一下哪一个是错误的和为什么？
正如 Matt Timmermans 正确指出的那样，该陈述不是从主定理得出的，而是从它的扩展版本得出的。
直接用tree method.
解决这个问题很简单
从 T(n) = 2T (n/2)+ n / log n:
开始
级别 0 有 1 个节点值为 n / log(n)。
级别 1 有 2 个节点，每个节点的值为 (n / 2) / log(n / 2).
...
关卡i有2i个节点，每个节点都有值(n / 2i) / log(n / 2i)
化简，水平i贡献n / (log(n) - i).
请注意，总共有 ~log(n) - 1 级才能达到常数。
因此，所有级别的总和为∑i = 0~log(n) - 1[ n / (log(n) - i)] ~ n ∑i = 0k[1 / k],
for k = log(n).
请注意，西格玛是 kth harmonic series, which is Θ(log(k))。设置 k = log(n) 总共给出 n Θ(log(log(n))) = Θ(n log(log(n))).
他们都是对的。 PDF 中的主定理不适用，但视频中的讲师正在使用涵盖您的案例的主定理的扩展形式。
我没能在视频中找到任何非常好的参考版本，这不是我学到的版本，但这里有在线证明：http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/extended_master_theorem.pdf
所以我使用 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 之间的非多项式差）
然而，在 this video 讲师在 12:26 解决了同样的问题，他给出了答案
Θ(nloglogn)
谁能解释一下哪一个是错误的和为什么？
正如 Matt Timmermans 正确指出的那样，该陈述不是从主定理得出的，而是从它的扩展版本得出的。
直接用tree method.
解决这个问题很简单从 T(n) = 2T (n/2)+ n / log n:
开始级别 0 有 1 个节点值为 n / log(n)。
级别 1 有 2 个节点，每个节点的值为 (n / 2) / log(n / 2).
...
关卡i有2i个节点，每个节点都有值(n / 2i) / log(n / 2i)
化简，水平i贡献n / (log(n) - i).
请注意，总共有 ~log(n) - 1 级才能达到常数。
因此，所有级别的总和为∑i = 0~log(n) - 1[ n / (log(n) - i)] ~ n ∑i = 0k[1 / k],
for k = log(n).
请注意，西格玛是 kth harmonic series, which is Θ(log(k))。设置 k = log(n) 总共给出 n Θ(log(log(n))) = Θ(n log(log(n))).
他们都是对的。 PDF 中的主定理不适用，但视频中的讲师正在使用涵盖您的案例的主定理的扩展形式。
我没能在视频中找到任何非常好的参考版本，这不是我学到的版本，但这里有在线证明：http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/extended_master_theorem.pdf