计算机问题求解（PPT讲稿）分治法与递归

计算机问题求解-论题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: 如何考虑分治算法的代价? 递归代价与非递归代价

递归代价与非递归代价

导出递归式 MERGE-SORT(A, P, r) <r 2345 q=(0+)2 两次归,理想情 况下条次问题规棋 MERGE-SORT(A, P,9) 是原来的一。 MERGE-SORT(A, 9+1, r) MERGE(A, P,q,r) 非逼归开萄 ifn=I =1x02+6051

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

C ifn=1 CT(n/2)+cn ifn>I T2) T(n/2)mmmmmmmmilin.CI Ig n cologne m/4 14 cn/4 cn/4 mil cn 确实比插入 排序效率高。 nl 这里似乎假设n是2的整次幂,在我们涉 及的大多数情况下,这不影响结果

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

更一般的情况是 T(n) e(1) if n<c, ar(n/b)+D(n)+C(n)otherwise 请解释a,bc的含义,D()和C()代表什么?

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

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

5678910111213141516 Day|0123456789101213141516 Rice001310851051028663811094106107949097 3-3-2520-3-16-231820-712-5-2215-47 Maximum subarray

Maximum subarray