有关递归算法复杂性的信息

这是一个复杂的话题,在互联网上的免费翻版并没有很好的记录。

我刚刚做了一个类似的考试,我可以给你指我老师写的手册: PDF Handbook

本手册主要介绍另一种工具 生成函数 这对于解决任何类型的复发都是有用的,而不必太费心于复发的类型。

有一本关于 算法分析 那就是 算法分析导论 ( amazon link )由Sedgewick和Philippe Flajolet提供,但你在网上找不到它(我不得不扫描部分)。

顺便说一句,我已经在网上搜索了很多,但是我没有找到任何完整的参考资料和有用的例子来学习这些技术。

我想你会更幸运的 recurrence equation .

您也可以查看 Master theorem .

在算法分析中, 主定理,这是一个特殊的 阿克拉-巴兹定理的例子, 提供食谱解决方案 递推的渐近项 发生在 实践。它是由 规范算法教科书 科尔曼算法导论, 莱瑟森、里维斯特和斯坦, 分章节介绍和论证 分别为4.3和4.4。然而,并非所有的复发 关系可以通过使用来解决 关于主定理。