Презентация на тему 算法设计与分析

合并排序
2.8 快速排序
2.9 线性时间选择
2.10 最接近点对问题
2.11 循环赛日程表
计划授课时间：6～8课时

{
if (n

小兔子问题

a, int b, int c)
{
　if (n > 0)
　{
　　hanoi(n-1, a,

adhoc(P); //解决小规模的问题
　divide P into smaller subinstances P1,P2,...,Pk；//分解问题
　for (i=1,i

int n)
{
// 在 a[0]

bd 或
XY = ac 2n + ((a+c)(b+d)-ac-bd) 2n/2 +

= tile++; // L型骨牌号
s = size/2; // 分割棋盘
// 覆盖左上角子棋盘
if

// 覆盖左下角子棋盘
if (dr >= tr + s && dc < tc + s)
// 特殊方格在此棋盘中
CB(tr+s, tc, dr, dc, s);
else {// 用 t 号L型骨牌覆盖右上角
board[tr + s][tc + s - 1] = t;
// 覆盖其余方格
CB(tr+s, tc, tr+s, tc+s-1, s);}
// 覆盖右下角子棋盘
if (dr >= tr + s && dc >= tc + s)
// 特殊方格在此棋盘中
CB(tr+s, tc+s, dr, dc, s);
else {// 用 t 号L型骨牌覆盖左上角
board[tr + s][tc + s] = t;
// 覆盖其余方格
CB(tr+s, tc+s, tr+s, tc+s, s);}
}

int right)
{
if (left

[38 49] [65 97] [13 76]

int p, int r)
{
if (p

r)
{
int i = p, j = r + 1;

r)
{
int i = Random(p,r);
Swap(a[i], a[p]);
return Partition (a, p, r);
}

(p==r) return a[p];
int i=RandomizedPartition(a,p,r),
j=i-p+1;
if (k

int k)
{
//用某个简单排序算法对数组a[p:r]排序;
if (r-p

复杂度分析

C1为直接简单排序时间
C2n为执行for循环的时间
解递归方程得T(n)=O(n)
说明：
上述算法将每一组的大小定为5，并选取75作为是否作递归调用的分界点。这2点保证了T(n)的递归式中2个自变量之和n/5+3n/4=19n/20=εn，0<ε<1。这是使T(n)=O(n)的关键之处。当然，除了5和75之外，还有其他选择。
上述算法中我们假设元素互不相等已保证划分后子数组不超过3n/4。当元素可能相等时，设有m个（将他们集中起来），若j≤k≤j+m-1时返回ai；否则调用select(i+m+1, r, k-j-m)。

S2={x|x>m}
CPair1(S1, d1);
CPair1(S2, d2);
p=max(S1);
q=min(S2);
d=min(d1, d2, q-p);
return ture;
}
复杂性分析：

T(n)=O(nlogn)
该算法可推广到二维的情形中去。

;
m=S中各点x间坐标的中位数;
构造S1和S2；
//S1={p∈S|x(p)m}
d1=cpair2(S1);
d2=cpair2(S2);
dm=min(d1,d2);
设P1是S1中距垂直分割线l的距离在dm之内的所有点组成的集合；
P2是S2中距分割线l的距离在dm之内所有点组成的集合；
将P1和P2中点依其y坐标值排序；
并设X和Y是相应的已排好序的点列；
通过扫描X以及对于X中每个点检查Y中与其距离在dm之内的所有点(最多6个)可以完成合并；
当X中的扫描指针逐次向上移动时，Y中的扫描指针可在宽为2dm的区间内移动；
设dl是按这种扫描方式找到的点对间的最小距离；
d=min(dm,dl);
return d;
}
复杂度分析：

T(n)=O(nlogn)
算法的具体实现：略。