T(n) = 25T(n/5)+n^2的时间复杂度
2024-08-24 00:41:11
对于T(n) = a*T(n/b)+c*n^k;T(1) = c 这样的递归关系,有这样的结论:
if (a > b^k) T(n) = O(n^(logb(a)));logb(a)b为底a的对数
if (a = b^k) T(n) = O(n^k*logn);
if (a < b^k) T(n) = O(n^k);
a=25; b = 5 ; k=2
a==b^k 故T(n)=O(n^k*logn)=O(n^2*logn)
T(n) = 25T(n/5)+n^2
= 25(25T(n/25)+n^2/25)+n^2
= 625T(n/25)+n^2+n^2 = 625T(n/25) + 2n^2
= 25^2 * T( n/ ( 5^2 ) ) + 2 * n*n
= 625(25T(n/125)+n^2/625) + 2n^2
= 625*25*T(n/125) + 3n^2
= 25^3 * T( n/ ( 5^3 ) ) + 3 * n*n
= ....
= 25 ^ x * T( n / 5^x ) + x * n^2
= 625T(n/25)+n^2+n^2 = 625T(n/25) + 2n^2
= 25^2 * T( n/ ( 5^2 ) ) + 2 * n*n
= 625(25T(n/125)+n^2/625) + 2n^2
= 625*25*T(n/125) + 3n^2
= 25^3 * T( n/ ( 5^3 ) ) + 3 * n*n
= ....
= 25 ^ x * T( n / 5^x ) + x * n^2
T(n) = 25T(n/5)+n^2
T(0) = 25T(0) + n^2 ==> T(0) = 0
T(1) = 25T(0)+n^2 ==> T(1) = 1
x = lg 5 n
25 ^ x * T( n / 5^x ) + x * n^2
= n^2 * 1 + lg 5 n * n^2
= n^2*(lgn)
最新文章
- WeakReference在Handler中的应用
- 今天遇到sqlyog连接不上阿里云的数据库,最后百度解决了...
- Zend Studio 11.0 汉化
- poj 3264
- [python爬虫] Selenium定向爬取海量精美图片及搜索引擎杂谈
- Git Tips
- iis错误记录
- U3D 精灵的点击监听
- 怎样学好C语言,一个成功人士的心得!
- JavaScript--DOM增删改操作
- php连接sql server 2008数据库
- java实现——007用两个栈实现队列
- (转)JAVA新特征
- flume实现kafka到hdfs测试用例
- openssl error while loading serial number
- Confluence 6 内存使用和需求
- SDOI2017 R2泛做
- oracle的db link
- Beta阶段基于spec评论作品
- 一、EnterpriseFrameWork框架总体介绍