离散数学13.34算法的平均复杂度分析省公开课一等奖全国示范课微课金奖PPT课件.pptx

该【离散数学13.34算法的平均复杂度分析省公开课一等奖全国示范课微课金奖PPT课件 】是由【liaoyumen】上传分享，文档一共【33】页，该文档可以免费在线阅读，需要了解更多关于【离散数学13.34算法的平均复杂度分析省公开课一等奖全国示范课微课金奖PPT课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。 算法平均复杂度分析
排序算法
快速排序算法
桶排序算法
散列表检索和插入
散列函数
链接法
开地址法(线性搜索法,双散列函数法)
1
第1页
快速排序算法
快速排序算法
Quicksort(A,p,r)
1. if p≥r then return A
2. x←A[r] //取A[r]作为轴值
3. i←p1
4. for j←p to r1 do
5. if A[j]≤x then i←i+1, 交换A[i]与A[j]
6. 交换A[i+1]与A[r] //把A[p..r]分成A[p..i]和A[i+2..r],
主元x置于A[i+1]
7. Quicksort(A,p,i)
8. Quicksort(A,i+2,r)
2
第2页
计算实例
i=0
5
6
2
8
1
7
3
4
i=0
5
6
2
8
1
7
3
4
i=0
5
6
2
8
1
7
3
4
i=1
2
6
5
8
1
7
3
4
i=1
2
6
5
8
1
7
3
4
i=2
2
1
5
8
6
7
3
4
i=2
2
1
5
8
6
7
3
4
i=3
2
1
3
8
6
7
5
4
2
1
3
4
6
7
5
8
3
第3页
快速排序算法平均时间复杂度分析
前提:假设输入服从均匀分布
n:n个数排列, T(n):输入为n时算法计算时间,
Tn:输入规模为n 时平均计算时间.
n, P(n)=1/n!,
Tn=E[T(n)]=
设轴值x是第i个小数, 有
T(n)= T(i1)+ T(ni)+O(n).
4
第4页
快速排序算法平均时间复杂度分析(续)
表示对n1
中取ni全部
排列求和
5
第5页
快速排序算法平均时间复杂度分析(续)
又T0=0, 得
Tn=O(nlogn)
6
第6页
桶排序算法
桶排序算法
输入[0,1)上n个数
Bucketsort(A)
1. n←|A|
2. for i←1 to n do
3. 把A[i]插入表
4. for i←0 to n1 do
5. 用插入排序算法对表B[i]进行排序
6. 依次连接表B[0], B[1],…, B[n1]
7
第7页
桶排序算法平均时间复杂度分析
前提:A[1],A[2],…,A[n]相互独立且都~U[0,1)
T(A):对输入A计算时间,
mi :桶B[i]中数个数, 0≤i≤n1, m0+ m1+…+ mn1=n,
Tn:输入规模为n时平均计算时间.

T(A)=O(n)+
Tn=E[T(A)]=O(n)+
8
第8页
桶排序算法平均时间复杂度分析(续)
9
第9页
散列法
设关键码全域为U, 散列表T[0..m1],
散列函数h:U→{0,1,…,m1},
h(K)称作关键码K散列值, 关键码K存放在T[h(K)]内
发生冲突: h(K1) = h(K2) (K1≠K2)
处理冲突方法:
链接法
开地址法
10
第10页