算法导论第9章思考题

9.1-1 证明：在最坏情况下，找到n个元素中第二小的元素需要n+$\lceil \lg n\rceil$-2此比较。（提示：可同时找最小元素）
先进行n-1次比较，每次比较中较大的数可能是第二小的元素
9.3-3 假设所有元素互异，说明在最坏情况下，如何才能使快排的运行时间为O(nlg n)
通过快速选择选取中位数作主元
9.3-7 设计一个O(n)时间的算法，对于一个给定的包含n个互异元素的集合S和一个正整数k<=n，该算法能确定S中最接近中位数的k个元素
在O(n)时间内找到中位数，用一个新数组存储其它元素与中位数的差值的绝对值。然后在O(n)时间内找到第k小的元素，输出小于等于此值的元素
9.3-8 设X和Y为两个数组，都包含n个有序的元素。请设计一个O(lg n)时间的算法来找出X和Y中所有2n个元素的中位数

MEDIAN(X, Y, n)if n == 1return min(X[1], Y[1])if X[n / 2] < Y[n / 2]return MEDIAN(X[n / 2 + 1..n], Y[1..n / 2], n / 2)return MEDIAN(X[1..n / 2], Y[n / 2 + 1..n], n / 2)

9-3
a. 设计一个能用U${}_i$(n)次比较在n个元素中找出第i小元素的算法，其中，U${}_i$(n)=$\{\begin{array}{rlrl}& T(n)& & 若i⩾\frac{n}{2}\\ & \lfloor \frac{n}{2}\rfloor +U_i(\lceil \frac{n}{2}\rceil )+T(2i)& & 其他\end{array}$
(提示：从$\lfloor \frac{n}{2}\rfloor$个不相交对的两两比较开始，然后对由每对中的较小元素构成的集合递归）

function SELECT(A, i):n=|A|if n <= 2i:return LINEAR_SELECT(A, i)  // O(n) 选择算法// Step 1: 分成 ⌊n/2⌋ 对，比较得到 S（较小者）pairs = split A into ⌊n/2⌋ disjoint pairsS = []for each pair (a, b) in pairs:if a < b:S.append(a)else:S.append(b)if n is odd:S.append(remaining element)// Step 2: 在 S 中递归找第 i 小的元素 xreturn SELECT(S, i)

9-4 假设所有的元素互异，输入数组的元素被重命名为z${}_1$,z${}_2$,…,z${}_n$，其中z${}_i$是第i小的元素。对所有1$⩽$i<j$⩽$n，设X${}_{ijk}$=I{在查找$z_k$期间，z${}_i$和z${}_j$进行过比较}
a. 给出E[X${}_{ijk}$]的准确表达式。（提示：表达式可能有不同的值，依赖于i、j、k的值）
E[X${}_{ijk}$]=$\{\begin{array}{rlrl}& \frac{2}{j-i+1}& & 若i<k<j\\ & 0& & 其他\end{array}$