高階主定理用於分治遞迴

分治法是一種演算法，其範例基於將問題遞迴地分解成多個類似型別的子問題，這些子問題可以很容易地解決。

示例

讓我們來看一個例子，來了解更多關於分治法的知識：

function recursive(input x size n)
   if(n < k)
      Divide the input into m subproblems of size n/p.
      and call f recursively of each sub problem
   else
      Solve x and return

組合所有子問題的結果並返回原始問題的解決方案。

解釋：在上述問題中，問題集被細分為更容易解決的較小子問題。

分治法的Master定理是一個分析定理，可用於確定遞迴關係演算法的Big-O值。它用於查詢演算法所需的時間，並將其表示為漸近符號形式。

上述示例中問題執行時間的示例：

T(n) = f(n) + m.T(n/p)

對於大多數遞迴演算法，可以使用Master定理找到演算法的時間複雜度，但Master定理在某些情況下可能不適用。Master定理不適用的情況包括：當問題T(n)不是單調的，例如T(n) = sin n。問題函式f(n)不是多項式。

由於Master定理在這些情況下查詢時間複雜度效率不高，因此設計了用於遞迴遞迴的**高階Master定理**。它旨在處理以下形式的遞迴問題：

T(n) = aT(n/b) + ø((n^k)logpn)

其中n是問題的大小。

a = 遞迴中的子問題數，a > 0

n/b = 每個子問題的大小，b > 1，k >= 0，p是實數。

為了解決這類問題，我們將使用以下解決方案：

  • 如果a > bk，則T(n) = Θ(nlogba)
  • 如果a = bk，則
    • 如果p > -1，則T(n) = Θ(nlogba logp+1n)
    • 如果p = -1，則T(n) = Θ(nlogba loglogn)
    • 如果p < -1，則T(n) = Θ(nlogba)
  • 如果a < bk，則
    • 如果p >= 0，則T(n) = Θ(nklogpn)
    • 如果p < 0，則T(n) = Θ(nk)

使用高階Master演算法，我們將計算一些演算法的複雜度：

二分查詢 - T(n) = Θ(logn)

歸併排序 - T(n) = Θ(nlogn)

更新於：2020年6月8日

2K+ 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始
廣告