递归树，求解方程复发

Question

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

我们被要求使用替代，我们将需要猜测输出的公式。我从CLRS书上看到，有没有神奇的做到这一点，我很好奇，如果有任何试探法来做到这一点？

我当然可以通过绘制复发树或使用迭代但是，因为输出将在大-OH或θ格式有一个想法，公式犯规必须匹配。

没有任何一个有用于使用替代求解递归方程任何建议？

Answer 1

有关简单的，只取 “合理” 的猜测。

有关更复杂的问题，我会继续使用复发树 - 在我看来是最简单的“算法”，用于产生猜测。请注意，它可能很难使用复发树证明绑定（细节是很难得到正确的）。复发树是用于形成猜测其然后通过取代证明是非常有用的。

我不知道为什么你说的公式将不匹配与大O或θ输出。他们通常不完全匹配，但这是大O点的一部分。想回到替代的伎俩的一部分是知道如何在BIG-O解决方案插上使替代代数锻炼。 IIRC，CLRS并制定出一个例子或两个的这种

Answer 2

请注意，可能的方式来解决复发方程名单肯定是不完全的，它只是一组工具，他们教计算机科学家，因为他们很可能会解决大部分的问题。

有关复发的精确解方程数学家使用一种称为生成函数的工具。生成功能给你确切的解决方案，并且一般比主定理更强大。

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

如果你去通过第一对夫妇的例子，你应该得到它的窍门在任何时间。

您需要一些数学背景，了解基本的泰勒级数。 http://en.wikipedia.org/wiki/Taylor_series

生成功能，可以在概率极为有用。