_Sort作用于规模为n的输入上的最坏情况的时间,则РT(n)=max(T(q)+T(n-q))+θ(n) ,其中1≤q≤n-1 (2)Р我们假设对于任何k<n,总有T(k)≤ck2 ,其中c为常数;显然当k=1时是成立的。Р将归纳假设代入(2),得到:РT(n)≤max(cq2+c(n-q)2)+θ(n)=c*max(q2+(n-q)2)+θ(n)Р因为在[1,n-1]上q2+(n-q)2关于q递减,所以当q=1时q2+(n-q)2有最大值n2-2(n-1)。于是有:РT(n)≤cn2-2c(n-1)+θ(n)≤cn2Р只要c足够大,上面的第二个小于等于号就可以成立。于是对于所有的n都有T(n)≤cn2 。Р这样,排序算法的最坏情况运行时间为θ(n2),且最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候。Р最好情况Р如果每次划分过程产生的区间大小都为n/2,则快速排序法运行就快得多了。这时有:РT(n)=2T(n/2)+θ(n), T(1)=θ(1) (3)Р解得: T(n)=θ(nlogn)Р快速排序法最佳情况下执行过程的递归树如下图所示,图中lgn表示以2位底的对数,而本文中用logn表示以2位底的对数.Р图2 快速排序法最佳情况下执行过程的递归树Р由于快速排序法也是基于比较的排序法,其运行时间为Ω(nlogn),所以如果每次划分过程产生的区间大小都为n/2,则运行时间θ(nlogn)就是最好情况运行时间。Р但是,是否一定要每次平均划分才能达到最好情况呢?要理解这一点就必须理解对称性是如何在描述运行时间的递归式中反映的。我们假设每次划分过程都产生9:1的划分,乍一看该划分很不对称。我们可以得到递归式:РT(n)=T(n/10)+T(9n/10)+θ(n) , T(1)=θ(1) (4)Р这个递归式对应的递归树如下图所示:
全文预览
