欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

《算法导论》第9章:顺序统计、中值

程序员文章站 2023-12-30 20:43:10
...

本章主要解决的问题:求数列中第i小的元素

一、排序+下标定位【最坏情况Θ(n*lgn)】

《算法导论》第9章:顺序统计、中值


 二、随机化分治算法【平均情况Θ(n)】

算法步骤

1.随机选择主元

2.线性时间内以主元划分为两部分,左半部分小于主元,右半部分大于主元。设主元的下标为k。

3.根据情况选择:

if k == i:直接返回A[k]
if k > i:递归最半部分找第i小的数
if k < i:递归右半部分找第i-k小的数

初步分析(假设所有元素都不相同)

《算法导论》第9章:顺序统计、中值

精确分析(平均情况)

其中Xk是指示器随机变量{0,1}:

《算法导论》第9章:顺序统计、中值《算法导论》第9章:顺序统计、中值

再使用代换法:

《算法导论》第9章:顺序统计、中值《算法导论》第9章:顺序统计、中值《算法导论》第9章:顺序统计、中值

代码实现(C++)

#include <iostream>
#include <cstdlib>
using namespace std;

int randomized_partition(int* a, int low, int high)
{
    int i = low - 1;
    int j = rand() % (high - low + 1) + low;
    swap(a[high], a[j]);           //a[high] is the pivot

    for(int j = low; j < high; ++j)
        if(a[j] <= a[high])
            swap(a[++i], a[j]);
    swap(a[++i], a[high]);

    return i;
}

int randomized_select(int* a, int p, int r, int i)
{
    if(p == r) return a[p];
    int q = randomized_partition(a, p, r);
    int k = q - p + 1;              //a[q] is the k-th smaller element in array a
    if(i == k) return a[q];
    else if(i < k) return randomized_select(a, p, q - 1, i);
    else return randomized_select(a, q + 1, r, i - k);
}

int main()
{
    int a[9] = {3, 5, 7, 9, 8, 6, 1, 2, 4};
    cout << randomized_select(a, 0, 9, 5);
    return 0;
}

 


三、选择算法SELECT【最坏情况Θ(n)】

算法步骤

(1)将输入数组的n个元素划分为floor(n/5)组,每组5个元素,且至多只有一组由剩下的n%5个元素组成;
(2)寻找这ceil(n/5)组中每一组的中位数,首先对每组元素进行插入排序,然后确定每组有序元素的中位数;
(3)对第2步中找出的ceil(n/5)个中位数,递归调用SELECT以找出其中位数x(如果有偶数个中位数,约定x是较小的中位数);
(4)利用PARTIONX,按中位数的中位数x对输入数组进行划分。让k比划分的低区中的元素多1,因此x是第k小的元素,并且有n-k个元素在高区。
(5)如果i=k,则返回x。如果i<k,则在低区递归调用SELECT来找出第i小的元素;如果i>k,则在高区递归调用SELECT找出第i-k小的元素。

算法分析

①寻找ceil(n/5)个中位数:Θ(n)

②递归计算ceil(n/5)个中位数的中位数m:T(n/5)

③至少右3n/10个数小于m,因此划分后的子问题规模:T(7n/10)

因此:T(n) = T(7n/10) + T(n/5) + Θ(n)

用代入法可证明:T(n) = Θ(n)

《算法导论》第9章:顺序统计、中值

 


Exercises 9.3-8

Let X[1 .. n] and Y [1 .. n] be two arrays, each containing n numbers already in sorted order. Give an O(lg n)-time algorithm to find the median of all 2n elements in arrays X and Y

解: int findMedian( X[1..n], Y[1..n])  // X 和 Y均为n个以排序的数组

  1.  在 X,Y中取中位数,分别为m、n    --------    O(1)

  2. if m==n:return m

  3. else if m<n:有floor(n/2)个数小于m,floor(n/2)个数大约n。中位数一定在m-n的区间上。

  4. else if m>n:类似上面

  5. else return findMedian(X[floor(n/2)+1..n],Y[1..floor(n/2)])

     T(n) = T(n/2)+O(1)

     由master定理,可知复杂度为O(lgn)

上一篇:

下一篇: