聚热点 juredian

中位数怎么求(如何寻找中位数?)

1:n个元素组成的集合,第i个顺序统计量,就是该集合中第i小的元素。所以,集合中的最小值就是第1个顺序统计量,最大值就是第n个顺序统计量。中位数是所属集合的中点元素,当n是奇数的时候,中位数唯一,位于(n+1)/2处。如果n是偶数,中位数有两个,分别位于n/2和(n/2) + 1。

2:选择问题,就是选择第i个顺序统计量的问题。如果利用排序的话,那最快可以在O(n lgn)时间内解决,但其实有更快的算法。

3:为了找到n个元素中的最小值或者最大值,最少需要n-1次比较:

MINIMUM(A)

min = A[1]

for i = 2 to A.len

if min > A[i]

min = A[i]

return min

4:对于需要同时找到最大值和最小值的问题,如果是独立找出最大值和最小值的话,需要2n-2次比较,实际上,采用某种方法可以实现比较次数最多到3(n/2)次。该方法是:记录已知的最大值和最小值,对输入的元素成对的进行处理,首先将2个输入元素相互比较,然后把较小的元素与最小值比较,较大的元素与最大值比较,这样,每两个元素共需比较3次。如果n是奇数,把最大值和最小值的初值都设置为第一个元素的值,所以,比较次数为3((n-1)/2)。如果n是偶数,把前两个元素作比较,确定最初的最大值和最小值,所以,比较次数为3((n-1)/2)。所以,不管哪一种情况,总的比较次数最多为3(n/2)。

如果要找第二小的元素,证明最坏情况下需要n + lg n – 2次比较。

证明:采用这样的方法找最小元素:将n个元素成对比较,找到n/2个小元素,然后对着n/2个元素再次成对比较,知道最后一个元素,也就是最小元素。

在该算法中,可以从底向上画出一棵完全二叉树,数有n个叶子结点,有n-1个内部结点,每个内部结点代表了一次比较,所以在寻找最小元素的过程中,需要n-1次比较。

为了找到第二小的元素,因该元素肯定是在与最小元素的比较过程中被淘汰掉了,所以为了寻找该元素,可以在该完全二叉树中,找到包含最小元素的分支,该分支一共有lg n个结点,在这lgn个结点中在找最小节点就好了,也是需要lg n – 1次比较。所以一共需要n + lg n – 2次比较。

5:对于一般的选择问题,可以采用类似于快速排序的方法,可以使运行时间达到Θ(n)。该算法称为RANDOMIZED-SELECT算法。该算法也是随机算法,因为其中调用了RANDOMIZED-PARTITION。算法伪代码如下:

RANDOMIZED-SELECT(A, p, r, i)

if(p == r)

return A

q = RANDOMIZED-PARTITION(A, p, r)

k = q – p + 1

if(k == i)

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)

该算法的最坏情况运行时间为Θ( )。但因为是随机的,所以不存在一个特定的输入会导致最坏情况的发生。该算法的期望运行时间为O(n)。

int randompartition(int *set, int begin, int end)

{

int i, j, k;

int x;

int ran;

srand((int)time(NULL));

ran = randomab(begin, end);

exchange(set+ran, set+end);

x = set[end];

i = begin - 1;

for(j = begin; j <= end - 1; j++)

{

if(set[j] <= x)

{

i++;

exchange(set+i, set+j);

}

}

exchange(set+i+1, set+end);

return i+1;

}

int partitionselect(int *set, int begin, int end, int index)

{

int q;

int k;

if(index <= 0="" index=""> (end-begin+1))

{

printf("error index: %d", index);

return -1;

}

if(begin == end)

{

return set[begin];

}

q = randompartition(set, begin, end);

k = q - begin + 1;

if(index == k)

{

return set[q];

}

else if(index < k)

{

partitionselect(set, begin, q-1, index);

}

else

{

partitionselect(set, q+1, end, index-k);

}

}

6:SELECT算法可以在最坏情况运行时间为O(n)来解决选择问题,该算法步骤如下:  a、将输入数组的n个元素划分为n/5组,每组5个元素,且至多有一个组由剩下的nmod 5个元素组成。  b、寻找n/5个组中每一组的中位数。(方法首先对每组中的元素进行插入排序,然后从排序过的序列中选出中位数)  c、对第2步中找出的n/5个中位数,递归调用SELECT找出其中位数x。(如果有偶数个中位数,根据约定,x是下中位数。)  d、 利用修改过的PARTITION过程,按中位数的中位数x对输入数组进行划分。让k比划分低区的元素多1,所以x是第k小的元素,并且有n-k个元素在划分的高区。  e、如果i=k,则返回x,否则,如果ik,则在高区找第(i-k)个最小元素。

图中箭头指向表示大的数值指向小的数值,所以根据图可以看出,在x的右边,每一个包含5个元素的组中至少有3个元素大于x,x的左边,每一组中至少有3个元素小于x。(保证x分割一边必定有元素存在)  图中显示的中位数的中位数x的位置,每次选取x作为划分的好处是能够保证必定有一部分在x的一边。  所以算法最坏情况的递归公式可以写成:

使用替换法可以得出T(n)<=cn。

注:凡属于本公众号内容,未经允许不得私自转载,否则将依法追究侵权责任。

搜索建议:中位数怎么求  中位数怎么求词条  
热闻

 小学秋天的作文500字

小学秋天的作文500字锦集九篇在日常学习、工作或生活中,大家都尝试过写作文吧,作文是从内部言语向外部言语的过渡,即从经过压缩的简要的、自己能明白的语言,向开展的...(展开)

热闻

 【歌词】昨天和不同的今天 / 歌...

每天都在一点一滴慢慢的失去却还是在这里贪婪的呼吸就象蜡烛燃烧的火苗照亮了一片片青草暴露无疑美好的生活怎能 怎能不这样怎能不这样度过每一分钟昨天 昨天和今天昨天和...(展开)