解： 两两比较，直至找到最小值（共需 n − 1 n-1 n−1次），将曾与最小值比较过的值进行比较（共需 ⌈ l g n ⌉ − 1 \lceil lgn\rceil -1 ⌈lgn⌉−1次）。 n − 1 + ⌈ l g n ⌉ − 1 = n + ⌈ l g n ⌉ − 2 n-1+\lceil lgn\rceil -1=n+\lceil lgn\rceil -2 n−1+⌈lgn⌉−1=n+⌈lgn⌉−2

解：先两两比较一轮（比较次数 ⌊ n 2 ⌋ \lfloor \frac{n}{2}\rfloor ⌊2n​⌋），将较大值分为一组（最多 ⌈ n 2 ⌉ \lceil \frac{n}{2}\rceil ⌈2n​⌉个元素），较小值分为一组（最多 ⌈ n 2 ⌉ \lceil \frac{n}{2}\rceil ⌈2n​⌉个元素），之后分别在两组间找出最大值（最小值）（比较次数 2 ⌈ n 2 ⌉ − 2 2\lceil \frac{n}{2}\rceil-2 2⌈2n​⌉−2）， ⌊ n 2 ⌋ + 2 ⌈ n 2 ⌉ − 2 = ⌈ 3 n 2 ⌉ − 2 \lfloor \frac{n}{2}\rfloor+2\lceil \frac{n}{2}\rceil-2=\lceil \frac{3n}{2}\rceil-2 ⌊2n​⌋+2⌈2n​⌉−2=⌈23n​⌉−2。

易证。。

在一个分区中选取主元不会影响子问题的概率。也就是说，在RANDOMIZED-PARTITION中对RANDOM的调用产生一个结果，与下一次迭代中的调用无关。

思路：依次选择9、8、7、6、5、4、3、2、1。

解： （1） T ( n ) ≤ { O ( 1 ) ,   n ; 126 T ( ⌈ n 7 ⌉ ) + T ( 5 n 7 + 8 ) + O ( n ) ,   n ≥ 126 T(n)\leq \begin{cases} O(1), ; \ n;126 \\ T(\lceil\frac{n}{7}\rceil)+T(\frac{5n}{7}+8) +O(n), ; \ n\geq 126\end{cases} T(n)≤{ O(1),T(⌈7n​⌉)+T(75n​+8)+O(n),​ n4