Exercise

9.1-1

对所有的元素,两个一组进行比较,共需n-1次比较,可以构成一棵二叉树,最小的元素在树的根结点上,接下来,画出二叉树,可以很容易的看出共需lgn-1次比较,所以共需n+lgn-2次比较才可以找出第二小的元素。

9.1-2

略。

9.2-1

在randomized-select中,对于长度为0的数组,此时p=r,直接返回A[p],所以不会进行递归调用。

9.2-2

略。

9.2-3

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];
        else if(i<k)
            q--;
        else{
            q++;
            i-=k;
        }
    }
}

9.2-4

每次都以最大的元素进行划分即可。

9.3-1

数学计算,根据书中例题仿照分析即可。

9.3-3

随机化

9.3-5

类似主元划分,只要把黑箱子输出的值作为主元划分去选择即可。

9.3-6

多重二分即可。

9.3-7

算出中位数,之后算出每一个数与中位数的差即可。

9.3-8

分别取两个数组的中位数进行比较,如果两个中位数相等,那么即为所求,否则,取中位数较小的一个的右边,取较大的一个的右边,直到就剩4个元素为止,这时候只要求这4个元素的中位数即可。

 

 

版权声明:本文为hlj-ljz原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/hlj-ljz/p/3515860.html