數據結構中的重現關係

Question

在我的數據結構類中，我們正在研究像T（n）和大O問題O（n）這樣的遞歸關係。我會很感激任何資源來學習這些，我的教科書不包括T（n），教授跳過了很多步驟。

我還沒有看到一個很好的解決這些事情的一步一步的方法。我意識到每一個問題都是獨一無二的，但必須有某種框架才能做到這一點。

謝謝。

Answer 1

檢查Concrete Mathematics - A Foundation for Computer Science，這是一本很好的書，有很多例子和練習。

Answer 2

另一本好書是Introduction to Algorithms。它有一個非常全面的解決復發關係的章節。

你是對的，有一種解決簡單遞歸關係的廣義方法，稱爲Master Theorem。 （在中的解釋算法簡介比維基百科頁面好得多）。它不適用於任何情況，但它解決了很多常見問題。