计算机问题求解一论题2-5 分治法与递归 2016年03月24日
计算机问题求解 – 论题2-5 - 分治法与递归 2016年03月24日
Mergesort Revisited MERGE-SORT (A,p.r) 1 if p<r 2 q=L(p+r)/2」 3 MERGE-SORT(A,p,q) 4 MERGE-SORT(A,q 1,r) 5 MERGE(A,p,q,r) 问题1： 这个算法究竟是如何“排”序的？
Mergesort Revisited
sorted sequence 个 1 2 3 5 6 7 conq merge 2 4 5 7 1 2 3 6 merge merge 2 5 4 3 6 merge merge merge merge 回 回 回 3 6 initial sequence
5 2 4 7 1 3 2 6 5 2 4 7 1 3 2 6 Divid e Divide further, until… conq uer
问题2： 人的思维分而治之” 如何变为算法策咯的呢？
间题3： 如何考虑分治算法的代价？ 递归代价与非递归代价
递归代价与非递归代价