计算机问题求解一论题2-4 分治法与递归 2022年03月16日
计算机问题求解 – 论题2-4 - 分治法与递归 2022年03月16日
Mergesort Revisited MERGE-SORT(A,p.r) 1 if p<r 2 9=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 2 2 3 4 5 6 7 merge □ 2 5 12 6 Divide Conquer Combine merge merge Conquer □ 2 5 4 1 2 merge merge merge merge 回 回 回 回 6 initial sequence
5 2 4 7 1 3 2 6 5 2 4 7 1 3 2 6 Divide Divide further, until… Conquer Combine Divide Conquer
问题2： 人的思维分而治之” 如何变为算法策咯的呢？
间题3： 如何考虑分治算法的代价？ 递归代价与非递归代价 非递归代价：子问题切分+子问题解的合并
递归代价与非递归代价 非递归代价：子问题切分+子问题解的合并