高级主定理用于分治递归

分治法是一种算法，其范例基于将问题递归地分解成多个类似类型的子问题，这些子问题可以很容易地解决。

示例

让我们来看一个例子，来了解更多关于分治法的知识：

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+ 次浏览

开启你的职业生涯

通过完成课程获得认证

开始
广告