Open Topic TC:7.4 快速排序的栈深度

Presentation on theme: "Open Topic TC:7.4 快速排序的栈深度"— Presentation transcript:

1 Open Topic TC:7.4 快速排序的栈深度
徐臣

2 TAIL_RECUSION_QUICKSORT(A,p,r) {
while(p<r) { int q=PARTITION(p,r); TAIL_RECUSION_QUICKSORT(A,p,q-1); p=q+1; }

3 首先我们得知道所有的递归程序都是通过栈来实现的
首先执行的上层递归，在执行下层递归时被压入栈中，在下层递归执行完了（即出栈），再执行 上层递归的剩余部分后将上层递归出栈。

4 A：证明尾递归的正确性 由前证已知PARITION(A,p,r)后得到的q上的数位置不再改变，
令 Q 为命题，当TAIL-recursive-quicksort(A,p,r) 执行后，p-r 上所有元素已确定其位置，即完成排序。 可知对于任意p，r=p 时，Q 恒成立，此包含r=p=1时。 r>p 时，假设 对于任意 1<=p0<=r0<=r , 有 Q 成立， 定义不变式 I ：当while 执行至 p=q+1 后，op-p-1 已排好序（因p会被改变，先设op=p 最开始时） 证明：循环前，p<op 为空集， Q成立。 循环中，在q=PARTITION 之前有op-p已排好序，后执行TAIL-recursive-quicksort(A,p,q-1)后可知 p-q-1已确定位置， 又有op-p确定位置，两者答案可直接合并故op-q-1都确定位置，又有PARTITON得q位置确定，则I得证 又可知q递增且q<=r,p=q.故循环一定终止 由I得 循环完成后，p>=r 则 p-1可能小于r，当p=r 时可知，op-r-1 都已排好序且位置不变，那么r上的数的位置只有r一 种可能，故亦为排好序的，p=r+1时则为op-r排序完成。 则Q得证。

5 B： 描述栈深度为Θ（n）的情况： 即程序在while循环中连续执行了Θ（n）次，不妨只研究n次的情况
那么第一层入栈就为TAIL-recursive-quicksort(A,1,A-length) 可知该函数直接出栈条件为p=r(无while循环的执行) 且可知每次执行压栈（即while循环）时，有q-1-p<r-1-p<r-p故其区间长度一定减小。 此时有： 1 压栈即减小区间长度 2 区间长度为最初为n 区间长度为0 则开始出栈 那么最大压栈数即 每次压栈只减少1的区间长度，此时栈深度最深为 n=Θ（n） 具体情况为每一次PARTITION得到的q 都为n ，即每一次都将最大的数的位置固定

6 C：改进方法 考虑每一次PARTITION后的 TAIL….函数的执行
PARTITION将原区间划分为 (p,q-1),{q},(q+1,r) 原函数固定选择前一种区间进行递归， 此处我们增加一个比较操作 比较（p,q-1）,(q+1,r)的区间大小即q-1-p和 r-q-1的大小， 每次选择区间长度更小的那一个进行递归函数TAIL…的执行。 这样之后我们有对于任意一次TAIL函数，设其所含区间长度为x 则有The_next_TAIL…._A_length <=x/2. 那么栈中上一层的区间长度一定小于等于下一层的1/2. 设最高层数为p 则有长度为1. 那么 1<=A_length(p-1)/2<(A_length(p-2)/2)/2<=…..A_length(1)/(2^p)<=n. 则 p<log n .即递归层数为Θ（log n）

7 算法的复杂度，可知每一次我们执行一个比较操作我们执行一次Tail函数，单次比较的执行为Θ （1），考虑TAIL函数总执行次数，可知其 <=n,则比较操作的最坏复杂度为Θ（n）。
再考虑除开比较函数的复杂度，此处的复杂度证明于原先的书中快速排序的复杂度证明相同，为Θ （nlogn）。 故总复杂度为Θ（n+nlogn）为Θ（nlogn）

8 一点小小的启发（雾） ：当遇到区间的划分操作，且执行代价与区间长度（大小）息息相关时，每次选择更小（或者更大， 依赖代价与区间大小的关系）往往会使得代价的期望值得到质的改变，原因便是一次比较便能使代 价依赖于某一个固定常数，在递归中其更恐怖为常数的层数次方（如这里）。所以这种思考方式在 许多地方都有极大的用途。 推荐例子： 启发式合并（尤其于并查集但不限于并查集，数据结构的合并都可以这样） 在这个例子中你会发现，原本极其暴力的操作加上一个简单的判断，会在时间变得极其优秀， 甚至不符合其暴力做法的本质 2333

9 thx