算法分析中递推式的一般代数解法
浏览:2300次 出处信息
算法分析中经常遇到需要求解递推式的情况,即将递推式改写为等价的封闭形式。例如汉诺塔问题的时间复杂度递推形式为
因为递推式求解的重要性,许多算法书籍对其有专门介绍。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天十大热文
- [66] Go Reflect 性能
- [66] Oracle MTS模式下 进程地址与会话信
- [65] 如何拿下简短的域名
- [59] IOS安全–浅谈关于IOS加固的几种方法
- [59] android 开发入门
- [59] 图书馆的世界纪录
- [58] 【社会化设计】自我(self)部分――欢迎区
- [53] 视觉调整-设计师 vs. 逻辑
- [47] 界面设计速成
- [47] 读书笔记-壹百度:百度十年千倍的29条法则