数据结构中的重现关系

Question

在我的数据结构类中，我们正在研究像T（n）和大O问题O（n）这样的递归关系。我会很感激任何资源来学习这些，我的教科书不包括T（n），教授跳过了很多步骤。

我还没有看到一个很好的解决这些事情的一步一步的方法。我意识到每一个问题都是独一无二的，但必须有某种框架才能做到这一点。

谢谢。

Answer 1

检查Concrete Mathematics - A Foundation for Computer Science，这是一本很好的书，有很多例子和练习。

Answer 2

另一本好书是Introduction to Algorithms。它有一个非常全面的解决复发关系的章节。

你是对的，有一种解决简单递归关系的广义方法，称为Master Theorem。 （在中的解释算法简介比维基百科页面好得多）。它不适用于任何情况，但它解决了很多常见问题。