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

问题来源：麻省理工-算法导论第二集第60min的例题 https://www. bilibili.com/video/BV1K x411f7bL?p=2

问题：

已知 T(n) = 4T(n/2) + n^2/\log n ，证明 T(n)=\Theta(n^2\log\log n) （主定理不可行）

证明：

递归展开得

\begin{align} T(n) & =4T(n/2)+n^2/\log n\\ &=4(4T(n/2^2) + (n/2)^2/\log(n/2))+n^2/\log n\\ &\dots\\ &=4^kT(n/2^k) + \sum_{i=0}^{k-1}\frac{4^i(\frac{n}{2^i})^2}{\log \frac{n}{2^i}}\\ &=n^2T(1) + n^2\sum_{i=1}^{\log n} \frac{1}{i} \end{align}

而由 Euler 常数 \gamma = \lim_{n\to \infty} (\sum_{i=1}^n \frac 1i - \ln n) = \text{const.} 可知 \sum_{i=1}^n \frac 1i =\Theta(\log n)

因此 T(n)=\Theta (n^2\log\log n)

参考：百度知道 https:// zhidao.baidu.com/questi on/535511624.html （强烈吐槽公式编辑。。。）