math - 数据结构中的递归关系

Question

在我的数据结构课程中，我们正在研究 T(n) 和大 O 问题 O(n) 之类的递归关系。我很感激学习这些的任何资源，我的教科书没有涵盖 T(n)，教授跳过了很多步骤。

我还没有看到解决这些问题的好方法。我意识到每个问题都是独一无二的，但必须有某种框架来解决这些问题。

谢谢。

Answer 1

检查具体数学 - 计算机科学的基础，这是一本包含大量示例和练习的精彩书籍。

Answer 2

另一本很棒的书是《算法导论》。它有一个关于解决递归关系的非常详尽的部分。

你是对的，有一种通用的方法可以解决简单的递归关系，称为主定理。（Introduction to Algorithms中的解释比 Wikipedia 页面要好得多。）它并不适用于所有情况，但它解决了很多常见的情况。