9-4 Alternative analysis of randomized selection

In this problem, we use indicator random variables to analyze the \(\text{RANDOMIZED-SELECT}\) procedure in a manner akin to our analysis of \(\text{RANDOMIZED-QUICKSORT}\) in Section 7.4.2.

As in the quicksort analysis, we assume that all elements are distinct, and we rename the elements of the input array \(A\) as \(z_1, z_2, \ldots, z_n\), where \(z_i\) is the \(i\)th smallest element. Thus, the call \(\text{RANDOMIZED-SELECT}(A, 1, n, k)\) returns \(z_k\).

For \(1 \le i < j \le n\), let

\[X_{ijk} = \text{I \\{$z_i$ is compared with $z_j$ sometime during the execution of the algorithm to find $z_k$\\}}.\]

a. Give an exact expression for \(\text E[X_{ijk}]\). (\(\textit{Hint:}\) Your expression may have different values, depending on the values of \(i\), \(j\), and \(k\).)

b. Let \(X_k\) denote the total number of comparisons between elements of array \(A\) when finding \(z_k\). Show that

\[\text E[X_k] \le 2 \Bigg (\sum_{i = 1}^{k}\sum_{j = k}^n \frac{1}{j - i + 1} + \sum_{j = k + 1}^{n} \frac{j - k - 1}{j - k + 1} + \sum_{i = 1}^{k-2} \frac{k - i - 1}{k - i + 1} \Bigg).\]

c. Show that \(\text E[X_k] \le 4n\).

d. Conclude that, assuming all elements of array \(A\) are distinct, \(\text{RANDOMIZED-SELECT}\) runs in expected time \(O(n)\).

(Removed)

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