@[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