算法复杂度求法初学
参考: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
- [593] 招聘技巧一二
- [17] 我的git笔记
- [16] 数据分析中常用的数据模型
- [15] 豆瓣是啥?
- [15] 在ssh服务里使用chroot
- [15] 30分钟3300%性能提升――python+
- [14] 一次神奇的MySQL优化
- [14] jQuery性能优化指南
- [14] Android用户界面设计:表格布局
- [14] 密度聚类算法之OPTICS