9-3 Small order statistics

We showed that the worst-case number \(T(n)\) of comparisons used by \(\text{SELECT}\) to select the \(i\)th order statistic from \(n\) numbers satisfies \(T(n) = \Theta(n)\), but the constant hidden by the \(\Theta\)-notation is rather large. When \(i\) is small relative to \(n\), we can implement a different procedure that uses \(\text{SELECT}\) as a subroutine but makes fewer comparisons in the worst case.

a. Describe an algorithm that uses \(U_i(n)\) comparisons to find the \(i\)th smallest of \(n\) elements, where

\[ U_i(n) = \begin{cases} T(n) & \text{if $i \ge n / 2$}, \\\\ \lfloor n / 2 \rfloor + U_i(\lceil n / 2 \rceil) + T(2i) & \text{otherwise}. \end{cases} \]

(\(\textit{Hint:}\) Begin with \(\lfloor n / 2 \rfloor\) disjoint pairwise comparisons, and recurse on the set containing the smaller element from each pair.)

b. Show that, if \(i < n / 2\), then \(U_i(n) = n + O(T(2i)\lg(n / i))\).

c. Show that if \(i\) is a constant less than \(n / 2\), then \(U_i(n) = n + O(\lg n)\).

d. Show that if \(i = n / k\) for \(k \ge 2\), then \(U_i(n) = n + O(T(2n / k)\lg k)\).

(Removed)

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