先进的掌握定理,用于分而治之

分而治之是一种基于递归式将问题分解为多个可以轻松解决的类似子问题的范例的算法。

示例

让我们以一个例子来学习更多关于分而治之的技巧-

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

合并所有子问题的结果,并将解决方案返回到原始问题。

解释-在上述问题中,问题集应细分为较小的子问题,可以轻松解决。

分而治之的Masters定理是一种分析定理,可用于确定递归关系算法的big-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 + 1 n)

    • 如果p = -1,则T(n)=∅(nlog ba loglogn)

    • 如果p <-1,则T(n)=∅(nlog ba

  • 如果a <b k,则

    • 如果p> = 0,则T(n)=∅(n k log p n)

    • 如果p <0,则T(n)=∅(nk)

使用高级主算法,我们将计算某些算法的复杂度-

二元搜索-t(n)=θ(logn)

合并排序-T(n)=θ(nlogn)