分而治之 是一种基于递归地将问题分解为多个相似类型的子问题，并且这些子问题可以很容易地解决的算法。
示例
让我们举一个例子来更深入地了解分而治之的技巧 –
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
Combine the results of all subproblems and return the solution to the original problem.
Explanation − In the above problem, the problem set is to be subdivided into smaller subproblems that can be solved easily.
Masters Theorem for divide and conquer is an analysis theorem that can be used to determine a big-0 value for recursive relation algorithms. It is used to find the time required by the algorithm and represent it in asymptotic notation form.
Example of runtime value of the problem in the above example −
T(n) = f(n) + m.T(n/p)
For most of the recursive algorithm, you will be able to find the Time complexity For the algorithm using the master’s theorem, but there are some cases master’s theorem may not be applicable. These are the cases in which the master’s theorem is not applicable. When the problem T(n) is not monotone, for example, T(n) = sin n. Problem function f(n) is not a polynomial.
As the master theorem to find time complexity is not hot efficient in these cases, and advanced master theorem for recursive recurrence was designed. It is design to handle recurrence problem of the form −
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 ba)如果 a k，那么如果 p > = 0，那么 T(n)= ∅(nklogpn)如果 p
使用高级主算法，我们将计算一些算法的复杂度 −
二分查找 − t(n) = θ(logn)
归并排序 − T(n) = θ(nlogn)
以上就是高级主定理用于分治递归的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444176.html
微信扫一扫 
支付宝扫一扫 
