3/8 }

掌握Partition(a,p,r)方法。

平均情况复杂性O (nlogn )

2.9 线性时间选择

template<class Type>

Type RandomizedSelect (Type a[],int p,int r,int k)

{

if (p==r) return a[p];

int i=RandomizedPartition(a,p,r),

j=i-p+1;

if (k<=j) return RandomizedSelect(a,p,i,k);

else return RandomizedSelect(a,i+1,r,k-j);

}

在最坏情况下，算法randomizedSelect 需要O(n 2)计算时间。但算法randomizedSelect 可以在O(n)平均时间内找出n 个输入元素中的第k 小元素。

进一步改进：

● 将n 个输入元素划分成⎡n/5⎤个组，每组5个元素，只可能有一个组不是

5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共⎡n/5⎤个。

● 递归调用select 来找出这⎡n/5⎤个元素的中位数。如果⎡n/5⎤是偶数，

就找它的2个中位数中较大的一个。以这个元素作为划分基准。

● 所以按此基准划分所得的2个子数组的长度都至少缩短1/4。

第3章 动态规划

算法的思想:

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。

动态算法基本步骤：

(1)找出最优解的性质，并刻划其结构特征。

(2)递归地定义最优值。

(3)以自底向上的方式计算出最优值。

(4)根据计算最优值时得到的信息，构造最优解。

⎩⎨⎧≥<++≤75

75)4/3()5/()(21n n n T n T n C C n T