9.2 Selection in expected linear time

9.2-1

Show that \(\text{RANDOMIZED-SELECT}\) never makes a recursive call to a \(0\)-length array.

Calling a \(0\)-length array would mean that the second and third arguments are equal. So, if the call is made on line 8, we would need that \(p = q - 1\), which means that \(q - p + 1 = 0\).

However, \(i\) is assumed to be a nonnegative number, and to be executing line 8, we would need that \(i < k = q - p + 1 = 0\), a contradiction. The other possibility is that the bad recursive call occurs on line 9. This would mean that \(q + 1 = r\). To be executing line 9, we need that \(i > k = q - p + 1 = r - p\). This would be a nonsensical original call to the array though because we are asking for the ith element from an array of strictly less size.

9.2-2

Argue that the indicator random variable \(X_k\) and the value \(T(\max(k - 1, n - k))\) are independent.

The probability that \(X_k\) is equal to \(1\) is unchanged when we know the max of \(k - 1\) and \(n - k\). In other words, \(\Pr\\{X_k = a \mid \max(k - 1, n - k) = m\\} = \Pr\\{X_k = a\\}\) for \(a = 0, 1\) and \(m = k - 1, n - k\) so \(X_k\) and \(\max(k - 1, n - k)\) are independent.

By C.3-5, so are \(X_k\) and \(T(\max(k - 1, n - k))\).

9.2-3

Write an iterative version of \(\text{RANDOMIZED-SELECT}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

PARTITION(A, p, r)
    x = A[r]
    i = p
    for k = p - 1 to r
       if A[k] < x
           i = i + 1
           swap A[i] with A[k]
    i = i + 1
    swap A[i] with A[r]
    return i

1
2
3
4

RANDOMIZED-PARTITION(A, p, r)
    x = RANDOM(p - 1, r)
    swap A[x] with A[r]
    return PARTITION(A, p, r)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

RANDOMIZED-SELECT(A, p, r, i)
    while true
        if p == r
            return A[p]
        q = RANDOMIZED-PARTITION(A, p, r)
        k = q - p + 1
        if i == k
            return A[q]
        if i < k
            r = q - 1
        else
            p = q + 1
            i = i - k

9.2-4

Suppose we use \(\text{RANDOMIZED-SELECT}\) to select the minimum element of the array \(A = \langle 3, 2, 9, 0, 7, 5, 4, 8, 6, 1 \rangle\). Describe a sequence of partitions that results in a worst-case performance of \(\text{RANDOMIZED-SELECT}\).

When the partition selected is always the maximum element of the array we get worst-case performance. In the example, the sequence would be \(\langle 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 \rangle\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用