求中位数 - webdancer's Blog

求中位数

webdancer posted @ 2011年10月13日 00:09 in 算法 with tags c 算法 , 1785 阅读

统计学中,中位数代表一个样本中的一个数值,其可将数值集合划分为相等的上下两部分。

实数$$x_1,x_2,......,x_n$$按大小顺序(升序,降序皆可)排列为$$x_1^,,x_2^,,......,x_n^,$$,实数数列$$x_1,x_2,......,x_n$$的中位数$$Q_\frac{1}{2}(x)$$为:

$$Q_\frac{1}{2}(x)$$=$$\lfloor\frac{(n+1)}{2}\rfloor$$

明确了概念后我们可以来解决怎么找中位数了。

算法1:按照定义所说的,首先排序,然后直接返回$$Q_\frac{1}{2}(x)$$即可。

算法2:在《算法导论》中介绍了如何可以在期望线性时间找到中位数。

 思想是:1.按照快排的思想,不断的随机分割。

                 2.如果随机分割的返回值恰是我们找的,可以返回该位置的数。

                 3.如果不满足,比较一下返回值与我们找的位置的大小,递归的进行下去,直到满足1.

算法3:

思想是: 1.利用快速排序的思想,不断的的分割。不过没有用递归。

用python实现了一下上面的算法,结果:

  algorithm1(ms) algorithm2(ms) algorithm3(ms)
$$10^3$$ 0 0 0
$$10^4$$ 9 19 20
$$10^5$$ 140 120 70
$$10^6$$ 2149 1689 780
$$10^7$$ 27480 21479 12480

 

 

 

 

 

 

参考:

1.http://zh.wikipedia.org/wiki/%E4%B8%AD%E4%BD%8D%E6%95%B0

2.算法导论。

Liwovosa 说:
2021年5月08日 20:05

You make so many great points here that I read your article a couple of times. Your views are in accordance with my own for the most part. This is great content for your readers. 123movies

move In & move out c 说:
2021年9月24日 01:26

Maids may help you to handle all of these tasks. You could hire them for under this move-in sort of service if that may be all you want. On the opposite hand, you could hire them an extra chance after you could have moved set for long-term, regular care of your home. As a new busy specialized, you will not have the time for it to put into this procedure yourself, but you'll be able to still find help to the cleanup a great deal more quickly than you already know.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee