南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）分治法与递归

计算机问题求解一论题2-4 分治法与递归 2018年03月28日

计算机问题求解 – 论题2-4 - 分治法与递归 2018年03月28日

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： 如何考虑分治算法的代价？ 递归代价与非递归代价

递归代价与非递归代价

导出递归式 MERGE-SORT (A,p,r) 1 if pI

导出递归式 两次递归，理想情 况下每次问题规模 是原来的一半。 非递归开销

cn cn T()= if n 1, 2T(/2)+cn Tn/2) Tn/2) cn Ig n cnlogn c/4 cn/4 cn/4 cn/4 aaann1e cn 确实比插入 排序效率高。 C n 这里似乎假设是2的整次幂，在我们涉 及的大多数情况下，这不影响结果

cnlogn 确实比插入 排序效率高。 T(n/2) T(n/2) 这里似乎假设n是2的整次幂，在我们涉 及的大多数情况下，这不影响结果

更一般的情况是 Θ(1) ifn≤c, T(n aT(n/b)+D(n)+C(n)otherwise. 请解释a,b,c的含义，Dn)和Cn)代表什么？

更一般的情况是 请解释a,b,c的含义，D(n)和C(n)代表什么？

问题4： 书上的投资回报问题是怎样 被转化为最大子数组问题的？

000 90 0 2345678910111213141516 Day 012345678910111213141516 Price 100113110851051028663811019410610179949097 Change 13-3-2520-3-16-231820-712-5-2215-47 Maximum subarray

Maximum subarray