递归树，解决复发方程

Question

据我知道的有4种方式来解决递归方程： 1递归树 2-换人 3 - 迭代 4 - 衍生

我们要求用换人，我们将需要猜测输出的公式。我从CLRS书中读到，没有什么魔术可以做到这一点，我很好奇是否有任何启发式的做法？

我当然可以通过绘制循环树或使用迭代有一个想法，但由于输出将采用Big-OH​​或Theta格式，因此公式不一定匹配。

有没有人有推荐使用替代求解递推方程？

Answer 1

对于简单的，只需要一个“合理”的猜测。

对于更复杂的问题，我会继续使用循环树—在我看来，它是最容易产生猜测的“算法”。请注意，使用循环树来证明一个界限是很困难的（细节很难正确）。复发树对于形成猜测是非常有用的，然后通过替代来证明。

我不知道你为什么说公式与Big-O或Theta中的输出不匹配。它们通常不完全匹配，但这是Big-O点的一部分。回到替代的一部分技巧是知道如何插入Big-O解决方案来使替代代数运行。 IIRC，CLRS确实解决了这个问题的一个或两个例子。

Answer 2

请注意，解决递推方程式的可能方法列表绝对不完整，它只是一套教计算机科学家的工具，因为它们很可能会解决大部分问题。

对于递推方程的精确解，数学家使用一种称为生成函数的工具。生成函数给出了精确的解，并且通常比主定理更强大。

有一个很好的资源在线了解这里。 http://www.math.upenn.edu/~wilf/DownldGF.html

如果你经历了前几个例子，你应该很快掌握它。

你需要一些数学背景和理解基本的泰勒系列。 http://en.wikipedia.org/wiki/Taylor_series

生成函数在概率中也非常有用。