0
如果我在每臺機器上都有m機器和相同數量的n數字，找到所有這些數字的中位數的最快算法是什麼，即所有m*n數字？有兩種情況我想查看：每個n號碼已排序或未排序。尋找不同機器上數字的中位數的最快算法是什麼？
有沒有人有一些參考，或一些想法分享？謝謝！
A
回答
0
中位數的中位數可以在多臺機器上進行調整，特別是如果它們都具有相同數量的元素。
邁克爾的解決方案是quickselect的改編。他們都工作，但快速選擇通常更快，儘管是O（nlogn）相比，中位數的O（n）的中位數。
相關問題
- 1. 尋找正整數的力量最快的算法是什麼？
- 2. 尋找數組中n個最小數字的最快方法是什麼？
- 3. 尋找合計數字的子集的最快算法是什麼？
- 4. 什麼是計算存儲數字所需位數的最快方法
- 5. 在桶中查找數字的最快方法是什麼？
- 6. 尋找素數的快速算法？
- 7. 找到n個數字的gcd最快的方法是什麼？
- 8. 在二維數組中尋找最大值的快速算法
- 9. 當數值具有不同的抽樣概率時，計算中位數的最快方法是什麼？
- 10. 查找數字最快的方法是什麼？
- 11. 尋找關鍵節點的快速算法是什麼？
- 12. 尋找數百萬計算最大結果的最有效方法是什麼？
- 13. 執行指數運算的最快算法是什麼？
- 14. 尋找瓶頸/優化Magento的最快方法是什麼？
- 15. 什麼是少數整數最快的排序算法？
- 16. 什麼是在隨機數組中找到最大數字的最佳方法？
- 17. 什麼是4位機器上的「最大」負數？
- 18. 尋找最短路徑數的算法
- 19. 尋找std :: map中輸入數字的最接近範圍的最有效的std算法是什麼？
- 20. 尋找相關文章的最佳算法是什麼？
- 21. 什麼是計算32的冪對數的最快方法？
- 22. 計算素數列表中數字位置的最佳方法是什麼？
- 23. 找到數組中出現最多的最大數的算法是什麼？
- 24. 尋找幸運數字的算法
- 25. 什麼是最快的算法來找到數組中的成對數之間的最小差異？
- 26. 什麼是最快的方式尋找最接近的數字對在陣列中的配對
- 27. 什麼是計算e到2萬億位數的最快方法？
- 28. 尋找高效算法在整數列表中尋找最接近的整數
- 29. 什麼是在c中產生隨機ip數字的最快方法？
- 30. 什麼是在Visual Basic 2008中隨機生成數字的最快方法？
快速選擇的確切複雜程度是什麼意思？ IIRC其平均複雜度爲O（n）。 – maxim1000
@maxim大哦表示最壞的情況。我誤解了：quickselect實際上是O（n^2），但通常會以O（n）結束，而且比中位數的中位數要小得多。 – bdares
@bdares：當你說「中位數的中位數」時，你怎麼在多臺機器上做到這一點？你能提供一些細節嗎？ –