理解主定理

Question

通用形式：T(n) = aT(n/b) + f(n)

所以，我必須比較N R個logb（a）用F（N）

如果n^logba>f(n)是殼體1和T(n)=Θ(n^logb(a))

如果n^logba < f(n) is case 2 and T(n)=Θ((n^logb(a))(logb(a)))

這是正確的嗎？或者我誤解了一些東西？

那麼情況3呢？何時適用？

Answer 1

我認爲你誤解了它。 如果n^logba> F（n）是殼體1和T（N）=Θ（N^logb（a））的

在這裏不應該擔心F（N），其結果你正在是T（n）=Θ（n^logb（a））。 （n）是T（n）的一部分，如果得到結果T（n），那麼該值將包含f（n）。 所以，沒有必要考慮那部分。

如果您不清楚，請告訴我。

Answer 2

注：我明白，這是爲時已晚來回答這個問題。我只是把它在這裏爲後人:)

主定理求解復發

復發發生在一個分治解決複雜問題的戰略。

它解決的是什麼？

• 它解決了形式T（n）= aT（n/b）+ f（n）的復發。
• 一個應大於或等於1。這意味着，該問題被至少減少到一個較小的子問題一次。需要至少一個遞歸
• b應大於1.在每個遞歸這意味着越大，該問題的規模被減小到更小的尺寸。如果b不大於1，那意味着我們的子問題不是較小的。
• F（N）必須爲相對較大的n值是正的。

考慮下面的圖片：

可以說，我們必須要解決規模爲n的問題。在每個步驟中，問題可以分解爲一個子問題，每個子問題的尺寸都較小，尺寸減小了一個因子b。

上面的語句中簡單的話是指大小爲n的問題可分爲相對較小的尺寸N/B的子問題。

另外，上面的圖表顯示，最後當我們多次分解問題時，每個子問題都會很小以至於可以在一段時間內解決。

對於下面推導考慮日誌到基b

讓我們說H是樹的高度，則H = LOGN。 葉數= a^logn。

• 1級完成整個工作：F（N）
• 在第2級進行總工作：A * F（N/B）
• 1級完成整個工作：A * A * F （n/b2）
• 最後完成的工作量水平：葉數*θ（1）。這等於爲n ^洛加主定理

  案例

三種情況1： 現在讓我們假設操作成本由顯著的因素在每個層次，並通過增加當我們達到葉級時，f（n）的值變成多項式小於值n^loga。那麼總體運行時間將主要由最後一級的成本支配。因此T（n）=θ（n^loga）

案例2： 讓我們假設在每個級別的操作成本大致相等。在那種情況下，f（n）大致等於n^loga。因此，總運行時間將是f（n）乘以總層數。 T（n）=θ（n^loga * logn）其中k可以> = 0。凡LOGN是對於k樹> = 0

案例3的高度： 讓我們假設操作的每個級別上的成本是由顯著的因素在每個級別和時間降低我們達到葉級時，f（n）的值變爲多項式大於值n^loga。那麼總體運行時間將主要由第一級的成本支配。因此T（n）=θ（f（n））

如果你有興趣更詳細的閱讀，也許是一些例子來練習。你可以隨時訪問我的博客條目。 Master Method to Solve Recurrences