计算机问题求解-论题2-4 分治法与递归 2018年03月28日
计算机问题求解 – 论题2-4 - 分治法与递归 2018年03月28日
Mergesort revisited MERGE-SORT(A P, r) I ifp<r 2q=|(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 soquence 7 34567 marge 4 23 C Divide conquer Combine rge merge conquer merge merge merge nLe 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: 如何考虑分治算法的代价? 递归代价与非递归代价
递归代价与非递归代价