和体科用银可料 C刀 品n cn logion 品n 品n 银E接装料 cn 10g10/9n 品 n C刀 4aal≤C7 间题5： ≤C刀 什么是递归树，你能香借助 O(nlgn) 这个图解释影响Quicksort 效率的因素？
In fact,any split of constn proportionality yieldson te of depthhere the costateach lvel is O(m).The running time is therefore O(ng)whenever the split has constant roportionaty. 问题⑥； 你看了这句话有什么想法？
问题7： 为什台么直观上也会觉得快速排 序的平均效率更接近最好情况， 而不是最坏情况？ 直觉对于探索很重要。 “大胆假设，小心求证！
直觉对于探索很重要。 “大胆假设，小心求证！
Worst-Case Performance of Quicksort T(m)=.max,(T(q)+T(-q-1)+Θ(m) 0sgs≤n-1 g是Partition的返回值。 问题8： 你能说说解这个递 归的策略吗？ Guess and verifying
Worst-Case Performance of Quicksort q是Partition的返回值。 Guess and verifying
随机快速排序的期望代价 快速排序的主要代价其实就是Partition的代价。 ■Partition的代价主要是循环中的比较操作。 Lemma 7.1 Let X be the number of comparisons performed in line 4 of PARTITION over the entire execution of QUICKSORT on an n-element array.Then the running time of QUICKSORT is O(n+X). Proof By the discussion above,the algorithm makes at most n calls to PARTI- TION,each of which does a constant amount of work and then executes the for loop some number of times.Each iteration of the for loop executes line 4
随机快速排序的期望代价 快速排序的主要代价其实就是Partition的代价。 Partition的代价主要是循环中的比较操作