算法复杂度求法初学
参考: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
- [17] [译]Google Chrome中的高性能网
- [14] 最近总结的一些技巧(vim,python,s
- [14] 在FreeNAS/BSD搭建基于Nginx+
- [14] 关于Linux的文件系统cache
- [13] Linux常用系统信息查看命令
- [11] Linux(Ubuntu 10.04)上安装
- [9] Centos yum 安装nginx+PHP
- [8] base64_encode 和 urlenc
- [7] 根据文件大小删除一个特殊文件名的文件
- [7] 浏览器缓存机制