算法定義

在統(tǒng)計(jì)學(xué)中，中值（又稱中位數(shù)）代表一個(gè)樣本、種群或概率分布中的一個(gè)數(shù)值，其可將數(shù)值集合劃分為相等的上下兩部分。對(duì)于有限的數(shù)集，可以通過把所有觀察值高低排序后找出正中間的一個(gè)作為中值。如果觀察值有偶數(shù)個(gè)，則中值不唯一，通常取最中間的兩個(gè)數(shù)值的平均數(shù)作為中值。

一個(gè)數(shù)集中最多有一半的數(shù)值小于中值，也最多有一半的數(shù)值大于中值。如果大于和小于中值的數(shù)值個(gè)數(shù)均少于一半，那麼數(shù)集中必有若干值等同于中值。

設(shè)連續(xù)隨機(jī)變量X的分布函數(shù)為F(X)，那么滿足條件P(X≤m)=F(m)=1/2的數(shù)稱為X或分布F的中位數(shù)。

對(duì)于一組有限個(gè)數(shù)的數(shù)據(jù)來說，它們的中位數(shù)是這樣的一種數(shù)：這群數(shù)據(jù)里的一半的數(shù)據(jù)比它大，而另外一半數(shù)據(jù)比它小。 計(jì)算有限個(gè)數(shù)的數(shù)據(jù)的中位數(shù)的方法是：把所有的同類數(shù)據(jù)按照大小的順序排列。如果數(shù)據(jù)的個(gè)數(shù)是奇數(shù)，則中間那個(gè)數(shù)據(jù)就是這群數(shù)據(jù)的中位數(shù)；如果數(shù)據(jù)的個(gè)數(shù)是偶數(shù)，則中間那2個(gè)數(shù)據(jù)的算術(shù)平均值就是這群數(shù)據(jù)的中位數(shù)。中位數(shù)統(tǒng)計(jì)學(xué)的函數(shù)符號(hào)為MEDIAN。

算法描述?

針對(duì)中位數(shù)，我們可以抽象的定義一個(gè)選擇問題，描述如下：

輸入：一個(gè)包含n個(gè)不同數(shù)的集合A和一個(gè)數(shù)i, i <= i <= n

輸出:恰大于A中i-1個(gè)元素的那個(gè)元素

白話描述: 寫一個(gè)函數(shù)，輸入一個(gè)數(shù)組和索引。返回第索引大的數(shù)字。如[1,5,6,3] 中第2(i=2)大的元素為3.

針對(duì)這個(gè)需求。最直觀的想法是找一個(gè)比較好的排序算法如堆排序等，用n(lgn)的復(fù)雜度排好序然后用線性的復(fù)雜度選擇元素。那么是否還有更優(yōu)復(fù)雜度的算法呢？顯然是有的。

這里的算法整個(gè)思路和前面講的?隨機(jī)版快速排序的思路是一致的。平均復(fù)雜度為O(n)的線性復(fù)雜度

源碼描述

function?RandomSelect(arr,?start,?end,?i)?{
????if?(start?==?end)?return?arr[start];
????//?隨機(jī)選擇一個(gè)分割下標(biāo)
????var?q?=?RandomPartition(arr,?start,?end);?
????var?k?=?q?-?start?+?1;
????//?如果所需要的值的大小位置正好等于K下標(biāo)。那么直接返回
????if?(i?==?k)?{
????????return?arr[q];
????//?如果小于K那么表示所需的元素在前一半分割元素堆里。那么直接在start~q-1的堆里去找第i個(gè)大小元素即可
????}?else?if?(i?<?k)?{
????????return?RandomSelect(arr,?start,?q-1,?i);
????//?如果大于K那么表示所需的元素在后一半分割元素堆里。那么已經(jīng)排除了K個(gè)元素。所以應(yīng)該找第i-k大的元素
????}?else?{
????????return?RandomSelect(arr,?q+1,?end,?i-k);
????}
}

function?swap(arr,?a,?b)?{
????if?(a?==?b)?return;?
????var?temp?=?arr[a];
????arr[a]?=?arr[b];
????arr[b]?=?temp;
}

//?數(shù)組分割
function?Partition(arr,?start,?end)?{
????var?pivot?=?arr[end];?//?將數(shù)組最后一個(gè)元素作為主元
????var?i?=?start?-?1;?//?指定一個(gè)指針
????for?(var?j?=?start;?j?<?end;?j++)?{
????????if?(arr[j]?<=?pivot)??{?//?如果當(dāng)前元素小于主元
????????????i?=?i?+?1;
????????????swap(arr,?i,?j);
????????}?
????}
????swap(arr,?i?+?1,?end);
????return?(i?+?1);
}

//?隨機(jī)交換主元后再Partition
function?RandomPartition(arr,?start,?end)?{
????var?i?=?Math.floor(Math.random()?*?(end?-?start?+?1)?+?start);
????swap(arr,?end,?i);
????return?Partition(arr,?start,?end);
}

var?arr?=?[1,3,6,8,4],?len?=?arr.length-1;
var?re?=?RandomSelect(arr,?0,?len,?2);
alert(re);

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/bluedream2009/archive/2011/04/28/2031260.html

總結(jié)

以上是生活随笔為你收集整理的【思维】中位数与顺序统计的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。