@[Defy_HeavenS](/user/493937) D
by Eric998 @ 2024-09-19 22:37:40
@[Defy_HeavenS](/user/493937) 考虑此式子的几何意义，将原问题视为一个大小为$n^2$的正方形平面，原递归式可以表示为：
- 将平面分成四等份，每份边长为原来的一半
- 使平面的高度增加$\log^2n$
显然，总复杂度为这个长方体的“体积”。其底面积为$n^2$。第$i$层的高度为$(\log n-i)^2$，高度之和为$O(\log^3n)$。因此选D。
by Eric998 @ 2024-09-19 22:43:22
把 $a=4,b=2$ 代入算出 $\log_ba = 2$，然后不难发现取第三种情况 $k=2$，所以 $T(n) = O(n^{\log_ba}\log^{k + 1}n) = O(n^2log^3n)$。 @[Defy_HeavenS](/user/493937)
by XiaoYiii @ 2024-09-19 23:09:05
@[XiaoYiii](/user/1025891) 公式做题就是快
by Eric998 @ 2024-09-19 23:26:19
@[Eric998](/user/678534) 谢
by Defy_HeavenS @ 2024-09-20 18:22:37
@[XiaoYiii](/user/1025891) 什么第三种情况？
是这个版本的主定理？：
$$
T(n)=aT(\frac{n}{b})+O(n^d\log^k n)
$$
by Defy_HeavenS @ 2024-09-20 18:25:10
@[Defy_HeavenS](/user/493937) 对不起，是我没说清楚。
指的是 [OI-wiki](https://oi-wiki.org/basic/complexity/#%E4%B8%BB%E5%AE%9A%E7%90%86-master-theorem) 上的
by XiaoYiii @ 2024-09-20 18:37:42
@[XiaoYiii](/user/1025891) 谢谢
by Defy_HeavenS @ 2024-09-20 18:46:42