分治递归的高级主定理

cserver side programmingprogramming

分治是一种基于递归将问题分支为多个相似类型的子问题的范式，这些子问题可以轻松解决。

示例

让我们举一个例子来了解有关分治技术的更多信息 −

function recursive(input x size n)
   if(n < k)
      将输入分为 m 个大小为 n/p 的子问题。
      并递归调用每个子问题的 f
    else
      求解 x 并返回

合并所有子问题的结果并返回原始问题的解。

解释 − 在上述问题中，问题集将被细分为可以轻松解决的较小子问题。

分而治之大师定理是一个分析定理，可用于确定递归关系算法的大 0 值。它用于查找算法所需的时间，并以渐近符号形式表示。

上例中问题的运行时间值示例 −

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

对于大多数递归算法，您将能够使用大师定理找到算法的时间复杂度，但有些情况下大师定理可能不适用。这些是大师定理不适用的情况。当问题T(n)不是单调时，例如，T(n) = sin n。问题函数f(n)不是多项式。

由于在这些情况下查找时间复杂度的大师定理效率不高，因此设计了递归递归的高级大师定理。它旨在处理形式为 − 的递归问题。

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

其中 n 是问题的大小。

a = 递归中的子问题数，a > 0

n/b = 每个子问题的大小 b > 1，k >= 0 且 p 为实数。

为了解决此类问题，我们将使用以下解决方案，

如果 a>b_k，则 T(n) = ∅ (nlogba)
如果 a = b_k，则
- 如果 p> -1，则 T(n) = ∅(nlogba log^p+1n)
- 如果 p = -1，则 T(n) = ∅(nlog_ba loglogn)
- 如果 p < -1，则 T(n) = ∅(nlog_ba)
如果 a<b_k ，则
- 如果 p> = 0，则 T(n)= ∅(n_klog_pn)
- 如果 p< 0，则 T(n) = ∅(nk)

利用高级大师算法，我们将计算一些算法的复杂度 −

二分查找 − t(n) = θ(logn)

归并排序 − T(n) = θ(nlogn)