如何解決如$ T（n）= T（n/2）+ T（n/4）+ O（m）這樣的遞歸關係$

Question

我希望得到這個再發生的更嚴格的界限，兩個變量m和n。

Answer 1

從我以前的答案here，我們可以得出一個二項求和公式T(n)：

凡

C是這樣的n = C是停止狀態對於T(n)。

---

在您的具體示例中，常量爲：c1 = 1, c2 = 1, a = 2, b = 4, f(n) = O(m)。由於O(m)對n沒有依賴性，我們可以簡單地用它替換f條款。

我們如何來衡量內部總和？回想二項展開的整數次冪：

設置a = b = 1我們得到：

這樣：