当前位置: 动力学知识库 > 问答 > 编程问答 >

algorithm - Difference between Divide and conquer And Subtract and conquer?

问题描述:

I have been reading about recursion and solving recurrence equations.Came across a term "subtract and conquer". How is it difference from "Divide and conquer" technique.Can i solve these kind of problems using the same techniques used for solving divide and conquer recurrence equations (like master theorem or recursion tree).

网友答案:

"The master theorem applies to divide and conquer algorithms. Some algorithms lead to recurrences of the form T(n) = aT(n-b) + Θ(nd). These might be called "subtract and conquer" or "giant step, baby step" algorithms."

Actually subtract differs from divide, that size of sub problem not divided, but subtracting, everything else is the similar.

Check this link for more details http://www.eecis.udel.edu/~saunders/courses/621/11s/notes/notes/Master-theorem.html

网友答案:

I read about "Divide and Conquer" algorithm and came across "Decrease and Conquer" which used Binary Search as its example. So I think "Subtract and Conquer" relates to "Decrease and Conquer" where instead of joining the sub-problems to find the final solution, we find the solution from the sub-problem itself ignoring the remaining part of the original problem.

分享给朋友:
您可能感兴趣的文章:
随机阅读: