关于主定理（时间复杂度分析）

学术版

Defy_HeavenS @ 2024-09-19 22:34:04

这样一道题：

\begin{array}{c} T(n)=4\times T(\frac{n}{2}) + n^2 \log^2 n \\ T(1)=1 \end{array}

该算法时间复杂度为：

  1. O(n^3)
  2. O(n^2 \log n)
  3. O(n^2 \log ^2 n)
  4. O(n^2 \log ^3 n)

（以上 \log 均默认为以 2 为底其实也没啥影响）

by Eric998 @ 2024-09-19 22:37:40

@Defy_HeavenS D

by Eric998 @ 2024-09-19 22:43:22

@Defy_HeavenS 考虑此式子的几何意义，将原问题视为一个大小为n^2的正方形平面，原递归式可以表示为：

显然，总复杂度为这个长方体的“体积”。其底面积为n^2。第i层的高度为(\log n-i)^2，高度之和为O(\log^3n)。因此选D。

by XiaoYiii @ 2024-09-19 23:09:05

把 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

by Eric998 @ 2024-09-19 23:26:19

@XiaoYiii 公式做题就是快

by Defy_HeavenS @ 2024-09-20 18:22:37

@Eric998 谢

by Defy_HeavenS @ 2024-09-20 18:25:10

@XiaoYiii 什么第三种情况？

是这个版本的主定理？：

T(n)=aT(\frac{n}{b})+O(n^d\log^k n)

by XiaoYiii @ 2024-09-20 18:37:42

@Defy_HeavenS 对不起，是我没说清楚。

指的是 OI-wiki 上的

by Defy_HeavenS @ 2024-09-20 18:46:42

@XiaoYiii 谢谢

|