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

Question

有人知道一些关于计算递归算法复杂度的好资料吗？不知何故，循环方程并不是真正流行的网页标题或什么，我只是无法谷歌搜索出任何合理的东西......

Answer 1

这是一个复杂的话题，在互联网上的免费文献中没有很好的记录。

我刚刚做了一个类似的考试，我可以给你指点我老师写的手册：PDF手册

本手册主要涵盖了另一种称为生成函数的工具，该工具可用于解决任何类型的递归，而无需过多地关注这种递归。

有一本关于算法分析的好书，是Sedgewick 和 Philippe Flajolet对算法分析的介绍（亚马逊链接），但你不会在网上找到它（我不得不扫描其中的一部分）。

顺便说一句，我在互联网上搜索了很多，但我没有找到任何完整的参考，其中包含对学习这些技术有用的示例。

Answer 2

我认为您对递归方程会更幸运。

Answer 3

您还可以查看Master theorem。

在算法分析中，主定理是 Akra-Bazzi 定理的一个特例，它为实践中出现的类型的递归关系提供了一个渐近术语的食谱解决方案。它由 Cormen、Leiserson、Rivest 和 Stein 的经典算法教科书 Introduction to Algorithms 推广，分别在 4.3 和 4.4 节中介绍和证明。然而，并不是所有的递归关系都可以通过使用主定理来解决。