数据结构中的递归关系
在我的数据结构课程中，我们正在研究诸如 T(n) 之类的递归关系和大 O 问题 O(n)。我很感激任何学习这些的资源，我的教科书没有涵盖 T(n)，而且教授跳过了很多步骤。
我还没有看到一个好的、分步的方法来解决这些问题。我意识到每个问题都是独特的，但必须有某种框架来解决这些问题。
谢谢。
In my Data Structures Class, we're looking at recurrence relations like T(n) and big O problems O(n). I'd appreciate any resources for learning these, my textbook doesn't cover T(n), and the professor skips over lots of steps.
I haven't seen a good, step-by-step method for solving these things. I realize that every problem is unique, but there has to be some sort of framework for doing these.
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
检查具体数学 - 计算机科学基础，这是一本精彩的书，内容很多示例和练习。
Check Concrete Mathematics - A Foundation for Computer Science, it's a brilliant book with lots of examples and exercises.
另一本好书是算法简介。它有一个关于解决递归关系的非常详尽的部分。
你是对的，有一种解决简单递归关系的通用方法，称为主定理。 （算法简介中的解释比维基百科页面要好得多。）它并不适用于所有情况，但它解决了很多常见问题。
Another great book is Introduction to Algorithms. It has a pretty thorough section on solving recurrence relations.
You are right, there is a generalized method for solving simple recurrence relations called the Master Theorem. (The explanation in Introduction to Algorithms is much better than the Wikipedia page.) It doesn't work for every case, but it solves a lot of common ones.