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
否则 if i
最坏情况为线性时间的选择算法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
若i>k,则在高区递归调用Select来找出第i-k小的元素
最坏运行时间为O(n)。
职业：暂无
0 条评论
下一页
图形选择
思维导图
主题
补充说明
AI生成
提示
关闭后当前内容将不会保存，是否继续？
取消
确定