快速排序时间复杂度分析

一趟快速排序算法描述:

quad quad quad (1) 初始化i=0,j=n-1 , prior=A[0]

quad quad quad(2)j 处从右向左开始扫描 (j–) ,直到找到第一个 A[j]<prior 的位置,令 A[i]=A[j]

quad quad quad(3)i 处从左向右开始扫描 (i++) ,直到找到第一个 A[i]>prior 的位置,令 A[j]=A[i]

quad quad quad (4) 重复 (2)(3) 直到 i=j ,令 A[i]=prior ,快速排速完成

时间复杂度分析:

经过上述一趟快速排序,我们只确定了一个元素的最终位置,我们最终需要经过n趟快速排序才能将一个含有 n 个数据元素的序列排好序,下面我们来分析其时间复杂度.

n 为待排序数组中的元素个数, T(n) 为算法需要的时间复杂度,则

quad quad quad quad quad quad quad T(n)=left { array{D(1)&n le 1/D(n)+T(I_1)+T(I_2)&n>1 }right.

其中 D(n)=n-1 ,是一趟快排需要的比较次数,一趟快排结束后将数组分成两部分 I_1I_2

最好时间复杂度:

核心点:最好情况下,每一次划分都正好将数组分成长度相等的两半

quad quad quad quad quad quad quad T(n)=left { array{D(1)&n le 1/D(n)+T(frac{n}{2})+T(frac{n}{2})&n>1 }right.

begin{align}所以:T(n)&=D(n)+2T(n/2)/ &=D(n)+2D(n/2)+4T(n/4)/ &vdots / &=D(n)+2D(n/2)+···2^kD(n/2^k)/ &=n-1+2(frac{n}{2}-1)+···2^k(frac{n}{2^k}-1)/ &=n-1+n-2+···n-2^k/ &because k=log_2n / &therefore原式= nlog_2n-2n+1in O(nlog_2n) end{align}

最坏时间复杂度:

核心点:最坏情况下,每一次划分都将数组分成了0和n-1两部分

quad quad quad quad quad quad quad T(n)=left { array{D(1)&n le 1/D(n)+T(0)+T(n-1)&n>1 }right.

begin{align}所以:T(n)&=D(n)+T(n-1)/ &=D(n)+D(n-1)+T(n-2)/ &vdots / &=D(n)+D(n-1)+···+D(2)+D(1)/ &=n-1+n-2+···+1+0/ &=frac{n(n-1)}{2}in O(n^2)/ end{align}

平均时间复杂度:

核心点:任意一种划分情况出现的概率都相等

所有的划分情况为: left { array{I_1=0& I_2=n-1/I_1=1&I_2=n-2/vdots / I_1=n-1 &I_2=0 }right.

begin{align}所以:T(n)&=D(n)+frac{1}{n}sum_{i=0}^{n-1}[T(i)+T(n-i)]/ &=D(n)+frac{2}{n}sum_{i=0}^{n-1}T(i)···(1)/ &because T(n-1)=D(n-1)+frac{2}{n-1}sum_{i=0}^{n-2}T(i)···(2)/ &therefore n*(1)-(n-1)*(2)得:/ nT(n)-(n-1)T(n-1)&=nD(n)+2sum_{i=0}^{n-1}T(i)-(n-1)D(n-1)-2sum_{i=0}^{n-2}T(i)/ &=nD(n)-(n-1)D(n-1)+2T(n-1)/ &=2(n-1)+2T(n-1)/ &移项得/ &n*T(n)=(n+1)T(n-1)+2(n-1)/ &等式两边同除n(n+1)得/ &frac{T(n)}{n+1}=frac{T(n-1)}{n}+frac{2(n-1)}{n(n+1)}/ &令B_n=frac{T(n)}{n+1},得/ &B(n)=B(n-1)+frac{2(n-1)}{n(n+1)}/ 下面通过递归求解B(n)的&表达式,然后将B(n)带回来求T(n)/ B(n)&=B(n-1)+frac{2(n-1)}{n(n+1)}/ &=B(n-2)+frac{2(n-2)}{(n-1)n}+frac{2(n-1)}{n(n+1)}/ &vdots / &=B(1)+sum_{i=1}^nfrac{2(i-1)}{i(i+1)}/ &=sum_{i=1}^nfrac{2(i+1)-4}{i(i+1)}/ &=sum_{i=1}^n[frac{i}{2}-frac{4}{i(i+1)}]/ &because sum_{i=1}^nfrac{4}{i(i+1)}=4sum_{i=1}^n[frac{1}{i}-frac{1}{i+1}]=4[1-frac{1}{n+1}]=4frac{n}{n+1}/ &because sum_{i=1}^nfrac{1}{i}approx ln(n)+0.577/ &therefore B(n)=ln(n)+0.577-4frac{n}{n+1}/ &将其回代进B_n=frac{T(n)}{n+1}/ &得T(n)=(n+1)ln(n)-4n+0.577(n+1)in O(nlog_2n) end{align}

综上:快速排序最好时间复杂度为 O(nlog_2n) ,最坏时间复杂度为 O(n^2) ,平均时间复杂度为 O(nlog_2n)

快速排序的一些改进方案:

(1) 将快速排序的递归执行改为非递归执行

(2) 当问题规模 n 较小时 (n le 16) ,采用直接插入排序求解

(3) 每次选取 prior 前将数组打乱

(4) 每次选取 frac{E[first]+E[Last]}{2}frac{E[first]+E[last]+E[(first+last)/2]}{3} 作为 prior

发表回复

相关推荐

吉利控股集团2024届全球校园招聘

投递链接:http://hturl.cc/n66y8 来源:海投网 吉利控股集团2024届全球校园招聘简章 l 全球汽车品牌组合价值排名前十中唯一 ...

· 1秒前

永遠不要嘲笑“站著的人”

這個2月社會上發生的事情太多太多,以至於每次想寫點什麼,又都無法沉下心來寫完。最近看的電影也不多,終日沉浸在慵懶的遊戲...

· 10秒前

盘点各国传出灵异事件的百年古堡,大马Kellie's Castle也是其一,传说有人在晚上看到堡主的灵魂!

前几年的一部电影《达芬奇密码》让神秘的古堡旅游热了起来。古堡让你的印象是什么呢?阴森?有恐怖传说?好像哈利波特故事里 ...

· 20秒前

后燕开国皇帝的嫡长子慕容令为何惨死异乡?

后燕开国皇帝的嫡长子慕容令为何惨死异乡?

· 31秒前

中耳炎,快遠離

20170728趁現在心情愉悅,精神不錯,輸液百無聊賴中,來寫寫我的中耳炎病史吧。。。 已經忘瞭具體哪年患上中耳炎瞭,大約...

· 40秒前