时间复杂度主定理分析及练习

article/2025/9/19 2:44:50

本文主要分析主定理，时间复杂度详细分析请移步至此。主定理是一种现在常用分析时间复杂度的方法，它主要适用于递归形式如下：

$T\left ( n \right ) = aT\left ( n/b \right ) + f\left ( n \right )$

当 $a \geqslant 1$ 和 $b > 1$ 为常量且 $f\left ( n \right )$ 是一个渐进正函数时有以下三种情况：

如果 $f\left ( n \right ) < O\left ( n^{log_ba} \right )$ ，则 $T\left ( n \right ) = \Theta \left ( n^{log_ba} \right )$
如果 $f\left ( n \right ) = \Theta \left ( n^{log_ba}log^{k}n \right )$ ，则 $T\left ( n \right ) = \Theta \left ( n^{log_ba} log^{k+1}n \right )$
如果 $f\left ( n \right ) > \Omega \left ( n^{log_ba} \right )$ ，则 $T\left ( n \right ) = \Theta \left (f\left ( n \right ) \right )$

在这里为了简单起见，我们不考虑 $O \Theta \Omega$ 之间的区别。

练习题：

1、 $T\left ( n \right ) = 3T\left ( n/2 \right ) + n^{2}$ 解 $a = 3$ $b = 2$ $f\left ( n \right ) = n^{2}$ 那么 $log_ba = log_23$ ，那么 $f\left ( n \right ) > n^{2}$ ，根据主定理有 $T\left ( n \right ) = O\left ( n^{2} \right )$

2、 $T\left ( n \right ) = 4T\left ( n/2 \right ) + n^{2}$ 解 $a = 4$ $b = 3$ $f\left ( n \right ) = n^{2}$ 那么 $log_ba = log_24$ ，那么 $f\left ( n \right ) = n^{2}$ ，根据主定理有 $T\left ( n \right ) = O\left ( n^{2}log_2n \right )$

3、 $T\left ( n \right ) = T\left ( n/2 \right ) + 2^{n}$ ，解 $a = 1$ $b = 2$ $f\left ( n \right ) = 2^{n}$ 那么 $log_ba = log_21$ ，那么 $f\left ( n \right ) > n^{0}$ ，根据主定理有 $T\left ( n \right ) = O\left ( 2^{n} \right )$

4、 $T\left ( n \right ) = 2^{n}T\left ( n/2 \right ) + n^{n}$ ，解 $a = 2^{n}$ $b = 2$ $f\left ( n \right ) = n^{n}$ 那么因为 $a$ 不是常数，所以不适用于主定理

5、 $T\left ( n \right ) = 16T\left ( n/4 \right ) + n$ ，解 $a=16$ $b = 4$ $f\left ( n \right ) = n$ 那么 $log_ba = log_416$ ，那么 $f\left ( n \right ) < n^{2}$ ，根据主定理有 $T\left ( n \right ) = O\left ( n^{2} \right )$