算法分析中递推式的一般代数解法
浏览:2207次 出处信息
算法分析中经常遇到需要求解递推式的情况,即将递推式改写为等价的封闭形式。例如汉诺塔问题的时间复杂度递推形式为
因为递推式求解的重要性,许多算法书籍对其有专门介绍。Donald Knuth在Concrete Mathematics一书中多个章节都涉及递推式求解方法。算法导论也在第四章中专门论述的这个主题。
在这些相关论述中,主要介绍了一些启发式方法,这些方法往往需要一些特殊的技巧和灵感才能完成。
而本文将论述一种纯代数式的方法,这种方法将求解递推式转化为求解一个多项式的根和求解一组线性方程组,这样就使得整个求解过程不依赖于太多技巧,因此具有更好的易用性。
本文首先会给出两个例子:如何使用纯代数方法求解斐波那契数列和汉诺塔递推式;然后会借助线性代数论述这种方法背后的数学意义,说明线性递推式与线性方程的内在联系以及这种解法的数学原理;最后将例子中的方法推广到一般情况。
示例
例1:斐波那契数列
斐波那契数列大家应该很熟悉了,这里不再赘述,直接进入问题。
问题
设斐波那契数列为由如下递推式定义的数列:
求解
求解
首先忽略初始条件,考虑递推式
更多请见原文:http://blog.codinglabs.org/articles/linear-algebra-for-recursion.html
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
扫一扫订阅我的微信号:IT技术博客大学习
<< 前一篇:文件系统的树形结构改善构思
后一篇:如何计算两个文档的相似度(一) >>
文章信息
- 作者:ericzhang.buaa@gmail.com 张洋 来源: CodingLabs
- 标签: 递推
- 发布时间:2013-05-20 23:30:33
近3天十大热文
- [587] 招聘技巧一二
- [16] 豆瓣是啥?
- [16] 数据分析中常用的数据模型
- [15] 给自己的字体课(一)——英文字体基础
- [15] 30分钟3300%性能提升――python+
- [14] iOS 8/Android/WP 系统设置的
- [14] 腾讯资深运维专家周小军:QQ与微信架构的惊天
- [14] jQuery性能优化指南
- [13] 一次神奇的MySQL优化
- [13] 密度聚类算法之OPTICS