结论
假设所有元素都是互异的，使用RANDOMIZED-SELECT算法可在期望为线性时间内找到任一顺序统计量，特别是中位数。
RANDOMIZED-SELECT算法
RANDOMIZED-SELECT(A, p, r, i)
if p == r
return A[p]
q = RANDOMIZED-PARTION(A, p, r)
k = q - p +1
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)
预备知识：指示器随机变量
证明：
待补
结论 假设所有元素都是互异的，使用RANDOMIZED-SELECT算法可在期望为线性时间内找到任一顺序统计量，特...
本篇源至于《算法导论》第９章学习笔记，记录关于顺序统计量的学习实践。 概念 顺序统计量 在一个由ｎ个元素组成的集合...
算法导论中文第三版Chapter 9 一些概念 顺序统计量：在n元素集合中，第i个顺序统计量是该集合中第i小的元素...
排序算法 输入:一个n个数的序列
小撒是一只好学的小鸭子，这天，小撒在学习算法 顺序统计量（order statistic） 在一个数组中，第i个数...
在一个由n个元素组成的集合中，第i个顺序统计量是该集合中第i小的元素。例如，在一个元素集合中，最小值是第1个顺序统...
1.最大（小）值（1）原理：假设第一个值为最大值，逐一遍历后面的数，若比前面定义的最大值大，则用此值更新最大值。遍...
基础算法 最大值或最小值 单求最大或最小时间，但同时找到最大值和最小值并不需要，成对比较(一次比较当前两数大小，将...
算法，算数，总是需要自己一番番计量的。
定义 抽样分布也称统计量分布、随机变量函数分布，是指样本估计量的分布。样本估计量是样本的一个函数，在统计学中称作统...
本文标题：算法-寻找顺序统计量
本文链接：https://www.haomeiwen.com/subject/ptbfxltx.html
网友评论