我一直在学习递归和解决递归方程。看到了一个术语“减治法”。它与“分治法”技术有何不同？
我能否使用解决分治递归方程的相同技巧来解决这些问题（如主定理或递归树）？
分治法和减治法的区别是什么？
3
- Rahul Kurup
3个回答
3
"主定理适用于分治算法。一些算法会导致形如T(n) = aT(n-b) + Θ(nd)的递归式。这些算法可能被称为“减法与征服”或“巨步，小步”算法。"
"实际上，减法与除法不同，其子问题的大小不是通过划分而是通过减少来实现的，其他方面都类似。"
"请查看此链接以获取更多详细信息：http://www.eecis.udel.edu/~saunders/courses/621/11s/notes/notes/Master-theorem.html"
"实际上，减法与除法不同，其子问题的大小不是通过划分而是通过减少来实现的，其他方面都类似。"
"请查看此链接以获取更多详细信息：http://www.eecis.udel.edu/~saunders/courses/621/11s/notes/notes/Master-theorem.html"
- Mysterion
1
我们如何解决“减而治之”递归方程？你能给一个例子吗？ - Rahul Kurup
1
我读到了“分治算法”，并了解到“减治算法”将二分查找作为其示例。
因此，我认为“减法征服”与“减治算法”相关，其中我们不是通过合并子问题来找到最终解决方案，而是从子问题本身中找到解决方案，忽略原始问题的其余部分。
- Kaustubh Srivastava
0
在这个话题上，我想补充一下Mysterion所提供的绝佳答案。由于资源链接已经失效，我很难找到关于减治法（也称为减而治之）算法相关的主定理的好资源，但是我在UDel CS Program找到了this document。
- Felipe Joaquín Pastén Cáceres
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接