计算机问题求解-论题2-4 分治法与递归 2018年03月28日
计算机问题求解 – 论题2-4 - 分治法与递归 2018年03月28日
Mergesort revisited MERGE-SORT(A P, r) I ifp
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)
导出递归式 两次递归，理想情 况下每次问题规模 是原来的一半。 非递归开销
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
更一般的情况是 请解释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