9.1 最小值和最大值

9.1-1

证明：为了找到n个元素中第二小的元素，先需要n-1次比较找到最小元素。然后可以断言：第二小的元素就在与最小元素比较过的元素中。因为如果第二小的元素没有和最小元素比较过，那就无法确定它们两者之间的大小关系。在寻找最小元素的过程中，先将输入元素两两分组进行比较，再将所有组中较小的元素两两分组进行比较，重复此步骤直至找到最小元素，易得：与最小元素比较过的元素数为，从这些元素中找到第二小的元素需要次比较。因此，在最坏情况下，找到n个元素中第二小的元素需要次比较。

9.2 期望为线性时间的选择算法

9.2-1

证明：

1. 在第8行中，k=1，因为i不可能等于0，所以不会进行递归调用。
2. 在第9行中，i-k>r-q-1，因为每次调用时i必须小于等于数组中的元素个数，所以也不会进行递归调用。

因此，在RANDOMIZED-SELECT中，对长度为0的数组，不会进行递归调用。

9.2-2

证明：=I{子数组A[p..q]正好包含k个元素}，A[k]表示被选作主元的元素也即当前划分，而T(max(k-1，n-k))表示之后选择所需要的时间。从字面意思上能够看出，当前划分与之后的选择所需要的时间完全没有关系，因此，指示器随机变量和T(max(k-1，n-k))是独立的。

9.2-3

RANDOMIZED-SELECT的一个基于循环的版本。

RANDOMIZED-SELECT-ITERATIVE(A, p, r, i)
    while r ≥ p
        if p == r
            return A[p]
        q = RANDOMIZED-PARTITION(A, p, r)
        k = q - p + 1
        if i == k        // the pivot value is the answer
            return A[q]
        else if i < k
            r = q - 1
        else
            p = q + 1
            i = i - k

9.2-4

假设用RANDOMIZED-SELECT去选择数组A=<3，2，9，0，7，5，4，8，6，1>的最小元素，能够导致RANDOMIZED-SELECT最坏情况发生的一个划分序列：主元出现的顺序为数组A中所有元素的逆序排列。

9.3 最坏情况为线性时间的选择算法

9.3-1

在算法SELECT中，如果输入元素被分为每组7个元素，该算法仍然会是线性时间。

证明：在算法SELECT中，如果输入元素被分为每组3个元素，SELECT的运行时间不是线性的。

为分析SELECT的运行时间，先要确定大于划分主元x的元素个数的下界。在第2步找出的中位数中，至少有一半大于或等于中位数的中位数x。因此，在这个组中，除了当n不能被3整除时产生的所含元素少于3的那个组和包含x的那个组之外，至少有一半的组中有2个元素大于x。不算这两个组，大于x的元素个数至少为：。类似地，至少有n/5-4个元素小于x。因此，在最坏情况下，在第5步中，SELECT的递归调用最多作用于4n/5+4个元素。

现在，可以设计一个递归式来推导SELECT算法的最坏情况运行时间T(n)了。步骤1、2和4需要O(n)时间。（步骤2是对大小为O(1)的集合调用O(n)次插入排序。）步骤3所需时间为，步骤5所需时间至多为T(4n/5+4)。这里，假设T是单调递增的。根据上述假设，可以得到如下递归式：。用替换法来证明这个运行时间不是线性的。更明确地说，将证明对某个适当大的常数c和所有的n>0，有。首先，挑选一个常数a，使得对所有的n>0，上述公式中的O(n)项所对应的函数（用来描述算法运行时间中的非递归部分）有上界an。其次，假设对某个适当大的常数c，有。将这个归纳假设代入上述递归式的右边，得到：。所以，。

因此，在算法SELECT中，如果输入元素被分为每组3个元素，SELECT的运行时间不是线性的。

9.3-2

证明：根据9.3节中对SELECT的分析，至少3n/10-6个元素大于中位数的中位数x，至少3n/10-6个元素小于x。当时，。因此，如果，则至少个元素大于中位数的中位数x，至少个元素小于x。

9.3-3

可以像SELECT算法那样，在PARTITION中按中位数的中位数x对输入数组进行划分。根据练习9.3-2，在最坏情况下，每次划分都将数组分成1/4和3/4两个部分，可以得到如下递归式：。根据练习4.4-9，。

9.3-5

假设已经有了一个最坏情况下是线性时间的用于求解中位数的“黑箱”子程序。设计一个能在线性时间内解决任意顺序统计量的选择问题算法。

LINEAR-SELECT(A, p, r, i)
    if p == r
        return A[p]
    o = MEDIAN-SELECT(A, p, r)
    exchange A[r] with A[o]
    q = PARTITION(A, p, r)
    k = q - p + 1
    if i == k
        return A[q]
    else if i < k
        return LINEAR-SELECT(A, p, q-1, i)
    else return LINEAR-SELECT(A, q+1, r, i-k)

9.3-6

对一个包含n个元素的集合来说，k分位数是指能把有序集合分成k个等大小集合的第k-1个顺序统计量。给出一个能找出某一集合的k分位数的时间的算法。

k-QUANTILE-SELECT(A, p, r, k)
    if k > 1
        m = (r-p+2) / k * ⌊k/2⌋
        a = SELECT(A, p, r, m)
        b = k-QUANTILE-SELECT(A, p, p+m-2, ⌊k/2⌋)
        c = k-QUANTILE-SELECT(A, p+m, r, k-⌊k/2⌋)
        return a, b, c

9.3-7

设计一个O(n)时间的算法，对于一个给定的包含n个互异元素的集合S和一个正整数，该算法能够确定S中最接近中位数的k个元素。

CLOSEST-TO-MEDIAN(A, p, r, k)
    median = ⌈(r-p) / 2⌉
    exchange A[r] with A[median]
    PARTITION(A, p, r)
    left = SELECT(A, p, p+median-1, median-k+1)
    exchange A[p+median-1] with A[left]
    PARTITION(A, p, p+median-1)
    right = SELECT(A, p+median+1, r, k)
    exchange A[r] with A[right]
    PARTITION(A, p+median+1, r)

    let closest[1..2k] be a new array
    index = 1
    for i = p+median-k to p+median-1
        closest[index] = |A[i] - A[median]|
        index = index + 1
    for i = p+median+1 to p+median+k
        closest[index] = |A[i] - A[median]|
        index = index + 1
    closest_median = SELECT(closest, 1, 2k, k)
    exchange closest[2k] with closest[closest_median]
    PARTITION(closest, 1, 2k)

    return closest[1, k]

9.3-8

设X[1..n]和Y[1..n]为两个数组，每个都包含n个有序的元素。设计一个时间的算法来找出数组X和Y中所有2n个元素的中位数。

MEDIAN-IN-TWO-ARRAYS(X, a, b, Y, c, d)
    if X[⌊(a+b) / 2⌋] == Y[⌊(c+d) / 2⌋]
        return X[⌊(a+b) / 2⌋]
    else if X[⌊(a+b) / 2⌋] < Y[⌊(c+d) / 2⌋]
        MEDIAN-IN-TWO-ARRAYS(X, ⌊(a+b)/2⌋, b, Y, c, ⌊(c+d)/2⌋ - 1)
    else
        MEDIAN-IN-TWO-ARRAYS(X, a, ⌊(a+b)/2⌋ - 1, Y, ⌊(c+d)/2⌋, d)

9.3-9

当n是偶数时，主管道的最优位置在所有油井的y坐标的第n/2个和第n/2+1个顺序统计量之间；当n是奇数时，主管道的最优位置在所有油井的y坐标的第(n+1)/2个顺序统计量。

证明：

设所有油井的y坐标的全序为，当主管道从开始向下移动距离d，且没有越过时，总距离变化了。当2i-n<0即i<n/2时，总距离变小；当2i-n>0即i>n/2时，总距离变大。

当n是偶数时，主管道从开始向下移动时，总距离不变，所以主管道的最优位置在和之间；当n是奇数时，主管道从开始向下移动时，总距离变小，主管道从开始向下移动时，总距离变大，所以主管道的最优位置在。

因为1个或2个顺序统计量可以在线性时间内确定，所以，主管道的最优位置可以在线行时间内确定。

---

思考题

9-1 有序序列中的i个最大值

给定一个包含n个元素的集合，利用基于比较的算法找出按顺序排列的前i个最大元素。设计能实现下列每一项要求，并且具有最佳渐进最坏情况运行时间的算法，以n和i来表示算法的运行时间。

a.对输入数据排序，并找出前i个最大数：

FIRST-I-LARGEST(A, i)
    n = A.length
    MERGE-SORT(A, 1, n)
    let i_largest[1..i] be a new array
    index = 1
    for j = n-i+1 to n
        i_largest[index] = A[j]
        index = index + 1
    return i_largest

算法的运行时间为。

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

FIRST-I-LARGEST(A, i)
    n = A.length
    BUILD-MAX-HEAP(A)
    let i_largest[1..i] be a new array
    for j = i to 1
        i_largest[j] = HEAP-EXTRACT-MAX(A)
    return i_largest

算法的运行时间为。

c.利用一个顺序统计量算法来找到第i大的元素，然后用它作为主元划分输入数组，再对前i大的数排序。

FIRST-I-LARGEST(A, i)
    n = A.length
    pivot = SELECT(A, 1, n, n-i+1)
    exchange A[n] with pivot
    PARTITON(A, 1, n)
    let i_largest[1..i] be a new array
    index = 1
    for j = n-i+1 to n
        i_largest[index] = A[j]
        index = index + 1
    MERGE-SORT(i_largest, 1, i)
    return i_largest

算法的运行时间为。

9-2 带权中位数

a.证明：假设的中位数是，即是的第个顺序统计量。，。因此，的中位数就是的带权中位数。

b.利用排序，设计一个最坏情况下时间的算法，可以得到n个元素的带权中位数。

WEIGHTED-MERGE(X, W, p, q, r)
    n1 = q - p + 1
    n2 = r - q
    let A[1..n1+1], B[1..n1], C[1..n2+1] and D[1..n2] be new arrays
    for i = 1 to n1
        A[i] = X[p + i - 1]
        B[i] = W[p + i - 1]
    for j = 1 to n2
        C[j] = X[q + j]
        D[j] = W[q + j]
    A[n1 + 1] = ∞
    C[n2 + 1] = ∞
    i = 1
    j = 1
    for k = p to r
        if A[i] ≤ C[j]
            X[k] = A[i]
            W[k] = B[i]
            i = i + 1
        else X[k] = C[j]
            W[k] = D[j]
            j = j + 1

WEIGHTED-MERGE-SORT(X, W, p, r)
    if p < r
        q = ⌊(p+r) / 2⌋
        WEIGHTED-MERGE-SORT(X, W, p, q)
        WEIGHTED-MERGE-SORT(X, W, q+1, r)
        WEIGHTED-MERGE(X, W, p, q, r)

WEIGHTED-MEDIAN(X, W)
    n = X.length
    WEIGHTED-MERGE-SORT(X, W, 1, n)
    weight_sum = 0
    for i = 1 to n
        weight_sum = weight_sum + W[i]
        if weight_sum ≥ 1/2
            return X[i]

c.利用像9.3节的SELECT这样的线性时间中位数算法，在最坏情况时间内求出带权中位数。

MARKED-PARTITION(X, W, p, r)
    x = X[r]
    i = p - 1
    for j = p to r-1
        if X[j] ≤ x
            i = i + 1
            exchange X[i] and X[j]
            exchange W[i] and W[j]
    exchange X[i+1] with X[r]
    exchange W[i+1] with W[r]
    return i+1

WEIGHTED-MEDIAN(X, W, p, r, i)
    if p == q
        return X[p]
    q = MARKED-PARTITION(X, W, p, r)
    weight_sum = 0
    for j = p to q-1
        weight_sum = weight_sum + W[j]
    if weight_sum < i and weight_sum+W[q] ≥ i
        return X[r]
    else if weight_sum < i
        return WEIGHTED-MEDIAN(X, W, q+1, r, i-weight_sum-W[q])
    else return WEIGHTED-MEDIAN(X, W, p, q-1, i)

d.证明：

当点p从开始向右移动距离d，且没有越过时，变化了。当即时，变小；当即时，变大。所以，使得最小的点p是的带权中位数。

因此，对一维邮局位置问题，带权中位数是最好的解决方法，其中，每个点都是一个实数，点a与b之间的距离是d(a，b)=|a-b|。

e.二维邮局位置问题的最好解决方法：其中的点是(x，y)的二维坐标形式，点与之间的距离是Manhattan距离，即。

分别找出的带权中位数x和的带权中位数y，使得最小的点p的坐标是(x，y)。

9-3 小顺序统计量

a.设计一个能用次比较在n个元素中找出第i小元素的算法，其中，。（提示：从个不想交对的两两比较开始，然后对由每对中的较小元素构成的集合进行递归。）

SMALL-ORDER-STATISTIC(A, p, r, i)
    if p == r
        return A[p]
    let R[1..⌈(r-p+1) / 2⌉] and S[1..⌈(r-p+1) / 2⌉] be a new array
    index = p
    for j = 1 to ⌈(r-p+1) / 2⌉
        if index + 1 > r or A[index] ≤ A[index+1]
            S[j] = A[index]
            R[j] = index
        else S[j] = A[index+1]
            R[j] = index + 1
        index = index + 2
    // S now contains the elements smaller in comparison
    // R now contains the index of elements smaller in comparison
    s = SMALL-ORDER-STATISTIC(S, 1, ⌈(r-p+1) / 2⌉, i)
    exchange S[⌈(r-p+1) / 2⌉] with s
    exchange R[⌈(r-p+1) / 2⌉] with s
    MARKED-PARTITION(S, R, 1, ⌈(r-p+1) / 2⌉)
    let T[1..2i] be a new array
    for j = 1 to i
        T[2j - 1] = S[j]
        if (R[j]-p) % 2 == 0
            T[2j] = A[R[j] + 1]
        else T[2j] = A[R[j] - 1]
    return SELECT(T, 1, 2i, i)

b.证明：

1. 当时，假设对某个适当选出的常数c>0，假定对所有正数m<n都成立，特别是对于，有。将其代入递归式，得到。其中，只要，最后一步都会成立。
2. 当时，易得：。

因此，如果，则有。

c.证明：因为i是小于n/2的常数，所以。因此，。

d.证明：因为对所有有，所以。因此，。

9-4 随机选择的另一种分析方法

a.给出的准确表达式。（提示：表达式可能有不同的值，依赖于i、j、k的值。）。

b.证明：。

c.证明：

1. 。
2. 。
3. 。

因此，。

d.证明：因为RANDOMIZED-SELECT的期望运行时间是，根据上一问的结论，。因此，RANDOMIZED-SELECT的期望运行时间是。