中位數的中位數算法理解

Question

我在網上搜索周圍，並參觀了維基頁面的中值算法的中位數。但似乎無法找到我的問題的明確聲明：

如果有一個非常大的整數列表（TB大小），並希望以分佈方式查找此列表的中位數，將打破名單成不同大小（或等於其實並不重要）的子表，然後進行計算那些更小的子列表中位數，然後計算這些中位數的中位數導致原始大名單的中位數？

而且是這種說法也是正確的任何第k個統計的？我對這方面的研究等有興趣。

Answer 1

的回答你的問題是沒有。

如果您想了解如何在並行設置（分佈式設置當然並不真的不同）中實際選擇第 - 階統計量（包括當然值的中位數），請參閱最近的論文，其中我提出了新的算法改進並行選擇在本領域算法的先前狀態：使用五向圍繞這些樞軸

Deterministic parallel selection algorithms on coarse-grained multicomputers

這裏，我們使用兩個加權3-位數作爲樞軸，和分區分區。我們還使用MPI實施並測試了該算法。結果都非常好，考慮到這是一個確定性的算法利用最壞情況Ø（n）的選擇算法。使用隨機化的QuickSelect算法提供了一種極其快速的並行算法。

Answer 2

如果一個人有一個整數的非常非常大名單（大小TBS），並希望找到這個列表中位數以分佈式的方式，將打破名單成大小不等的子列表（或等於沒有按真的很重要），然後繼續計算那些較小的子列表的中位數，然後計算這些中位數的中位數，結果是原始大列表的中位數？

不是。整個列表的實際中值不一定是任何子列表的中位數。

中位數中位數可以給你一個很好的快速選擇樞軸，因爲它比一個隨機選擇的元素更接近實際的中位數，但你必須做快速選擇算法的其餘部分來找到實際的中位數的較大名單。