0
如果我在每臺機器上都有m
機器和相同數量的n
數字,找到所有這些數字的中位數的最快算法是什麼,即所有m*n
數字?有兩種情況我想查看:每個n
號碼已排序或未排序。尋找不同機器上數字的中位數的最快算法是什麼?
有沒有人有一些參考,或一些想法分享?謝謝!
如果我在每臺機器上都有m
機器和相同數量的n
數字,找到所有這些數字的中位數的最快算法是什麼,即所有m*n
數字?有兩種情況我想查看:每個n
號碼已排序或未排序。尋找不同機器上數字的中位數的最快算法是什麼?
有沒有人有一些參考,或一些想法分享?謝謝!
中位數的中位數可以在多臺機器上進行調整,特別是如果它們都具有相同數量的元素。
邁克爾的解決方案是quickselect的改編。他們都工作,但快速選擇通常更快,儘管是O(nlogn)相比,中位數的O(n)的中位數。
快速選擇的確切複雜程度是什麼意思? IIRC其平均複雜度爲O(n)。 – maxim1000
@maxim大哦表示最壞的情況。我誤解了:quickselect實際上是O(n^2),但通常會以O(n)結束,而且比中位數的中位數要小得多。 – bdares
@bdares:當你說「中位數的中位數」時,你怎麼在多臺機器上做到這一點?你能提供一些細節嗎? –