递归树，求解递归方程
据我所知，求解递归方程有4种方法: 1-递归树，2-替换，3-迭代，4-导数
我们被要求使用替换，我们将需要猜测输出的公式。我从CLRS的书中读到，没有魔法可以做到这一点，我很好奇是否有任何启发式方法来做到这一点？
我当然可以通过绘制递归树或使用迭代来获得一个想法，但是，因为输出将是Big-OH或Theta格式，所以公式不一定匹配。
有没有人推荐使用代换来解决递归方程？
回答 2
Stack Overflow用户
发布于 2009-10-06 02:05:05
对于简单的问题，只需要一个“合理”的猜测。
对于更复杂的问题，我会继续使用递归树-对我来说，它似乎是生成猜测的最简单的“算法”。请注意，使用递归树来证明一个界限可能很困难(细节很难正确)。递归树对于形成猜测非常有用，然后通过替换来证明这些猜测。
我不明白你为什么说这些公式与Big-O或Theta的输出不匹配。它们通常不完全匹配，但这是Big-O点的一部分。返回到替换的技巧的一部分是知道如何插入大O解来使替换代数工作。IIRC，CLRS确实做了一两个这样的例子。
Stack Overflow用户
发布于 2009-10-06 05:24:49
请注意，解决递归方程的可能方法列表肯定是不完整的，它只是一组他们教给计算机科学家的工具，因为它们最有可能解决你的大多数问题。
对于递归方程的精确解，数学家使用一种称为生成函数的工具。生成函数给你精确的解，并且通常比主定理更强大。
有一个很好的在线资源可以了解这里。http://www.math.upenn.edu/~wilf/DownldGF.html
如果你看过前几个例子，你应该很快就会掌握它的诀窍。
你需要一些数学背景，并理解初级的泰勒级数。http://en.wikipedia.org/wiki/Taylor_series
生成函数在概率方面也非常有用。
https://stackoverflow.com/questions/1523232
复制相似问题
腾讯云开发者
