据我所知，有 4 种方法可以解决递归方程： 1- 递归树 2- 替换 3 - 迭代 4 - 导数
我们被要求使用 Substitution，我们需要猜测输出公式。我从 CLRS 书中读到，没有魔法可以做到这一点，我很好奇是否有任何启发式方法可以做到这一点？
我当然可以通过绘制递归树或使用迭代来获得一个想法，但是因为输出将采用 Big-OH 或 Theta 格式，所以公式不一定匹配。
有人对使用替换求解递归方程有任何建议吗？
问问题
3490 次
2 回答
3
请注意，解决递归方程的可能方法列表绝对不完整，它只是他们教给计算机科学家的一组工具，因为它们很可能会解决您的大部分问题。
对于递归方程的精确解，数学家使用一种称为生成函数的工具。生成函数为您提供精确的解决方案，并且通常比主定理更强大。
有一个很好的在线资源可以了解这里。http://www.math.upenn.edu/~wilf/DownldGF.html
如果您浏览前几个示例，您应该很快就会掌握它。
您需要一些数学背景并了解基本的泰勒级数。http://en.wikipedia.org/wiki/Taylor_series
生成函数在概率方面也非常有用。
于 2009-10-06T05:24:49.067 回答
1
对于简单的，只需进行“合理”的猜测。
对于更复杂的，我会继续使用递归树——在我看来，这似乎是产生猜测的最简单的“算法”。请注意，使用递归树来证明边界可能很困难（细节很难正确）。递归树对于形成猜测非常有用，然后通过替换来证明。
我不确定您为什么说公式与 Big-O 或 Theta 中的输出不匹配。它们通常不完全匹配，但这是 Big-O 要点的一部分。回到替换的部分技巧是知道如何插入 Big-O 解决方案以使替换代数有效。IIRC，CLRS 确实提出了一个或两个例子。
于 2009-10-06T02:05:04.737 回答