算法复杂度求法初学
参考: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
- [88] Go Reflect 性能
- [15] 我的git笔记
- [12] osx平台上lol英雄联盟launcher启
- [12] 公钥私钥加密解密数字证书数字签名详解
- [11] 正态分布的前世今生(一)
- [11] 浅谈Web安全验证码
- [11] iTerm2 (Mac Terminal)
- [11] iOS可视化编程 Tips 之“无需代码设置
- [10] JVM内存结构
- [10] 基于HTTP缓存轻松实现客户端应用的离线支持