首页 > 编程语言 > 详细

初赛—算法复杂度

时间:2021-09-09 23:32:21      阅读:8      评论:0      收藏:0      [点我收藏+]

对于 \(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)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!