递归树，求解递归方程
据我所知，求解递推方程有4种方法： 1-递归树 2- 替换 3 - 迭代 4 - 导数
我们被要求使用替换，我们需要猜测输出的公式。我从 CLRS 书中读到，执行此操作没有魔法，我很好奇是否有任何启发式方法可以执行此操作？
我当然可以通过绘制递归树或使用迭代来得到一个想法，但是，因为输出将采用 Big-OH 或 Theta 格式，所以公式不一定匹配。
有人对使用替换法求解递推方程有什么建议吗？
As far as I know There are 4 ways to solve recurrence equations :
1- Recursion trees
2- Substitution
3 - Iteration
4 - Derivative
We are asked to use Substitution, which we will need to guess a formula for output. I read from CLRS book that there is no magic to do this, i was curious if there are any heuristics to do this?
I can certainly have an idea by drawing a recurrence tree or using iteration but, because the output will be in Big-OH or Theta format, formulas doesnt necessarily match.
Does any one have any recommendation for solving recurrence equations using substitution?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
请注意，解决递归方程的可能方法列表绝对不完整，它只是他们教计算机科学家的一组工具，因为他们很可能会解决您的大多数问题。
对于递归方程的精确解，数学家使用称为生成函数的工具。生成函数可以为您提供精确的解决方案，并且通常比主定理更强大。
在线有一个很棒的资源可以了解这里。 http://www.math.upenn.edu/~wilf/DownldGF.html< /a>
如果您完成了前几个示例，您应该很快就能掌握它的窍门。
您需要一些数学背景并了解基本的泰勒级数。 http://en.wikipedia.org/wiki/Taylor_series
生成函数在以下方面也非常有用：可能性。
Please note that the list of possible ways to solve recurrence equations is definitely not complete, its merely a set of tools they teach Computer Scientists, because they will most likely solve most of your problems.
For exact solutions of recurrence equations mathematicians use a tool called generating functions. Generating functions give you exact solutions, and in general are more powerful than the master theorem.
There is a great resource online to learn about the here. http://www.math.upenn.edu/~wilf/DownldGF.html
If you go through the first couple examples you should get the hang of it in no time.
You need some math background and understand rudimentary taylor series. http://en.wikipedia.org/wiki/Taylor_series
Generating functions are also extremely useful in probability.
对于简单的，只需进行“合理”的猜测即可。
对于更复杂的问题，我会继续使用递归树 - 在我看来，这是生成猜测的最简单的“算法”。请注意，使用递归树来证明界限可能很困难（很难获得正确的细节）。递归树对于形成猜测非常有用，然后通过替换来证明猜测。
我不知道你为什么说这些公式与 Big-O 或 Theta 中的输出不匹配。它们通常不完全匹配，但这正是 Big-O 的要点之一。回到替换的部分技巧是知道如何插入 Big-O 解决方案来使替换代数起作用。 IIRC、CLRS 确实提出了一两个这样的例子。
For simple ones, just take a "reasonable" guess.
For more complicated ones, I would go ahead and use a recurrence tree — it seems to me to be the easiest "algorithm" for generating a guess. Note that it can be difficult to use a recurrence tree to prove a bound (the details are tough to get right). Recurrence trees are highly useful for forming guesses which are then proven by substitution.
I'm not sure why you're saying the formulas won't match with the output in Big-O or Theta. They typically don't match exactly, but that's part of the point of Big-O. Part of the trick of going back to substitution is knowing how to plug in the Big-O solution to to make the substitution algebra work out. IIRC, CLRS does work out an example or two of this.