根据递归式求递归树,分析时间复杂度,递归式为:当n=1时,T(n)=O(1),当n>1时,T(n) = T(n/2)+c(n/2)^2
时间: 2024-03-11 09:47:17 浏览: 12
根据递归式求递归树的方法,我们可以将递归过程表示成一棵树,该树的根节点表示最初的递归调用,每个节点表示一个递归调用,该节点的子节点表示该递归调用所产生的子问题的递归调用。
对于该递归式,我们可以得到递归树如下图所示:
```
T(n)
/ \
T(n/2) T(n/2)
/ \ / \
T(n/4) T(n/4) T(n/4) T(n/4)
. . . .
. . . .
. . . .
T(1) T(1) T(1) T(1)
```
其中每个节点的代价为 $c(n/2)^2$,因此,我们可以得到每一层的代价为 $c(n/2)^2$,第 $i$ 层的节点数为 $2^i$,因此,第 $i$ 层的代价为 $2^ic(n/2^i)^2$。
总代价为各层代价之和,即:
$T(n) = \sum\limits_{i=0}^{\log_2 n-1}2^ic(n/2^i)^2$
接下来,我们可以对该式子进行求和:
$T(n) = \sum\limits_{i=0}^{\log_2 n-1}2^ic(n/2^i)^2$
$T(n) = cn^2\sum\limits_{i=0}^{\log_2 n-1}\frac{1}{2^i}$
$T(n) = cn^2\left(\frac{1-2^{-\log_2 n}}{1-2^{-1}}\right)$
$T(n) = cn^2(2-1/n)$
因此,该递归式的时间复杂度为 $O(n^2)$。