初赛—算法复杂度
时间：2021-09-09 23:32:21
收藏：0
阅读：41
对于 \(T(n) = a\times T(\frac{n}{b})+c\times n^k\) 这样的递归关系，有这样的结论：
- \(a>b^k\) 则有 ： \(T(n) = O(n^{\log_{b} a})\)
- \(a=b^k\) 则有 ： \(T(n) = O(n^k\times log n)\)
- \(a<b^k\) 则有 ： \(T(n) = O(n^k)\)
例如：
\[T(n)=25\times T\left(\dfrac{n}{5}\right)+n^2
\]
\[a=25,b = 5,k=2\Rightarrow a=b^k
\]
\[T(n)=O(n^k\times \log n)=O(n^2\times \log n)
\]
原文：https://www.cnblogs.com/EricQian/p/15246389.html
评论（0）