《算法导论》笔记第9章总结与思考

【思考】

9-1 已排序的i个最大数

给定一个含n个元素的集合，我们希望能用一个基于比较的算法来找出按顺序排列的i个最大元素。

请找出能实现下列每一种方法的、具有最佳的渐进最坏运行时间的算法，并分析各种方法的运行时间（用n和i表示）。

a) 对输入数排序，并列出i个最大的数。

O(nlogn)的排序。

b) 对输入数建立一个优先级队列，并调用EXTRACT-MAX过程i次。

建堆O(n)，每次调用O(logn)，共O(n+ilogn)

c) 利用一个顺序统计量算法来找到第i个最大元素，然后划分输入数组，再对i个最大数排序。

寻找第i大元素O(n)，排序O(ilogi)，共O(n+ilogi)

9-2 带权中位数

对分别具有正的权重w1, w2, ... , wn且的n个不同元素x1, x2, ..., xn，带权（下）中位数是满足如下条件的元素xk

a) 论证x1, x2, ..., xn 的中位数即各xi的带权中位数，此处权值 wi=1/n, i=1,2 ..., n。

将wi=1/n带入得

即中位数。

b) 如何通过排序，在O(nlgn)的最坏情况时间内求出n个元素的带权中位数。

先对元素排序，再对权值进行累计，找到第一个xk满足

则xk为带权中位数。

c) 说明如何利用一个线性时间的中位数算法，来在最坏情况Θ(n) 时间内求出n个数的带权中位数。

void prepare(double W[],double SW[],int n) {
    for (int i=1;i<=n;i++) SW[i] += SW[i-1] + W[i];
}
int partition(int A[],int p,int r) {
    int x = A[r];
    int i = p - 1;
    for (int j=p;j<r;j++) {
        if (A[j] <= x) {
            i++;
            swap(A[i],A[j]);
        }
    }
    swap(A[i+1],A[r]);
    return i+1;
}
int randomizedPartition(int A[],int p,int r) {
    int q = rand()%(r-p+1)+p;
    swap(A[q],A[r]);
    return partition(A,p,r);
}
int randomWeightSelect(int A[],double SW[],int p,int r,double w0) {
    if (p==r) return A[p];
    int q = randomizedPartition(A,p,r);
    double w1 = SW[q] - SW[p-1];
    if (w0==w1) return A[q];
    else if (w0<w1) return randomWeightSelect(A,SW,p,q-1,w0);
    else return randomWeightSelect(A,SW,q+1,r,w0-w1);
}

mid = randomWeightSelect(A,SW,1,n,1/2);

邮局选址问题（post-office location problem）定义如下：已知n个点p1, p2, ..., pn及与它们相联系的权重w1, w2, ..., wn。我们希望能找到一点p（不一定时输入点中的一个），使和式最小，此处d(a,b）表示点a与b之间的距离。