

首页  思维导图  详情



9-中位数和顺序统计量-算法导论

2016-06-03 10:41:48   8  举报





AI智能生成

算法导论-9-中位数和顺序统计量

算法导论

中位数和顺序统计量

模版推荐

作者其他创作

大纲/内容

顺序统计量

定义

最小值与最大值-第一个顺序统计量为min，第n个~为最大值

获取最小值Minimum(A)

基本思想：将A[1]与后面n-1个数顺次比较得结果即可（共n-1次）

同时获取最大最小值

法1:像获取最小值那样，每次都将最小值与当前值比较，将最大值与当前值比较，计算次数为2n-2

法2:初始值为A[1]or min(A[1],A[2]),然后成对比较，将较大值给MAX, 较小给MIN，最后得到结果，共3n/2-2次

中位数

上中位数&下中位数

随机选择算法Randomized-QuickSort(A,p,r,i)

功能: 返回A数组中第i小的元素

时间复杂度：最坏F(n.^2) ,平均：线性时间O(n)

算法过程：

检查数组A是否为单一输入（if p==r 则直接返回A[p]）

根据分治思想进行随机分割，将A分为A[p, q-1] 和 A[q+1,r]

记 k = p-q+1, if i==k则返回A[q]

否则 if i<k 则进行递归 Randomized-QuickSort(A,p,q-1,i)

否则 if i<k 则进行递归 Randomized-QuickSort(A,q+1,r,i-k)

最坏情况为线性时间的选择算法Select(A,p,r,i)

功能: 确定n个不同元素的输入数组中第i小的元素

基本思路

通过分组获取中位数的中位数x，以此为分节点对输入进行划分，然后递归调用得出结果

算法过程

将含n个不同元素的输入数组A划分为[n/5]组

对每一组进行插入排序并得到该组中位数

将上一步得到的所有中位数作为新的数组A'并一次递归Select(A',...)得到中位数的中位数x （此处指下中位数）

按x对输入数组进行划分A(p,p+k-1)、A(p+k+1,r). 其中 x 是第k小的元素

若i==k则返回 x

若i<k,则在低区递归调用Select来找出第i小的元素；

若i>k,则在高区递归调用Select来找出第i-k小的元素

最坏运行时间为O(n)。

 Collect

Get Started

顺序图-查看影院统计

 Collect

Get Started

zk选举——countVotes投票统计算法

 Collect

Get Started

无序数组的中位数（堆排序）

 Collect

Get Started

统计





0 条评论

下一页