计算时间复杂度T(N)

发表于 | 分类于 |
字数统计: 89 | 阅读时长 ≈ 1

对于$T(n) = a \times T(n/b)+c\times n^k$ 这种类型的。

$if(a>b^k) \quad T(n)=O(n^{\log_ba})$

$if(a=b^k) \quad T(n)=O(n^{k \times \log n})$

$if(a<b^k) \quad T(n)=O(n^k)$

$T(n) = 3T(n/4)+n^3$

$3<4^2$ 所以 $T(n) = O(n^3)$

$T(n)= T(\sqrt{n})+n$

$T(n)=n+n^{\frac{1}{2}}+n^{\frac{1}{4}}+…..=n$

0%