算法复杂度求法初学
参考:http://www.comp.nus.edu.sg/~xujia/mirror/algorithm.myrice.com/algorithm/
有空演习了一点点。
递归方程算法复杂性求法之:迭代法
注:T()函数等于php中的floor()函数
1、T(n) = n^2 + 2T(n/2)
n^2 + 2T(n/2)
n^2 + (n/2)^2 + 2T(n/4)
n^2 + (n/2)^2 + (n/4)^2 + 2T(n/8)
…
n^2 + (n/2)^2 + (n/4)^2 + (n/8)^2 + (n/16)^2 + … + (n/2^(2i))^2 + 2T(n/2^(2i))
n^2(1 + 1/2^2 + 1/2^4 + 1/2^6 + …)
渐进 = n^2
2、T(n) = n + T([n/3])+ T([2n/3])
n + T(n/3)+ T(2n/3)
n + n/3 + T(n/3^2) + T(2n/3^2) + 2n/3 + T(2n/3^2) + T(n(2/3)^2)
= 2n + …(4 items)
2n + n/3^2 + 2n/3^2 + 2n/3^2 + n(2/3)^2 + (8 items)
= 3n + …(8 items)
…
in + (2^i items)
i为递归次数,有限。items最后都趋于0。
i是多少次?取决于每次的最大值。每次的最大值分别是:n,n(2/3),n(2/3)^2,n(2/3)3,…,1
i=log(3/2)n
渐进 = log(3/2)n * n
建议继续学习:
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:kanwairen.z 来源: 铭扬工作室Blog
- 标签: 复杂度
- 发布时间:2009-11-12 00:03:02
- [16] Go Reflect 性能
- [15] 浏览器的工作原理:新式网络浏览器幕后揭秘
- [13] 界面设计速成
- [13] iOS下自己动手造无限循环图片轮播
- [13] iOS可视化编程 Tips 之“无需代码设置
- [13] iTerm2 (Mac Terminal)
- [12] 最萌域名.cat背后的故事:加泰与西班牙政府
- [12] Spark性能优化——和shuffle搏斗
- [12] iOS并发编程(Concurrency Pr
- [11] 内网穿透神器frp