如何在O（logn）時間查找5個排序列表的中位數？

Question

這裏是問題：

有5個排序列表A，B，C，D，E，它有相同的長度n。問題是要找到一個算法，可以在O（logn）時間中的這個列表的中位數。我正在考慮一個普遍的想法，但我無法弄清楚它需要的確切複雜性。

假設A，B，C，D，E的中位數爲a，b，c，d，e。我們有a<b<c<d<e。很明顯，我可以扔掉陣列A的前半部分和陣列E的後半部分。現在我有5個新陣列：B，C，D保持不變，每個都有n個數字; A'和E'每個都剩下n/2個數字。然後我計算A'和E'的中位數作爲'和e'，將它們與b，c，d進行比較。如果5箇中位數的新訂單是a'<b<e'<c<d，那麼我通過一個'（n/4個數字）的前半部分和D個數組的最後n/4個數字，因爲我們需要在最終中位數。這個過程繼續...

我有一種感覺算法是O（logn）。但我不知道確切的證據。在第一個logn步驟中，我們可以肯定地將候選人數減少到3n，將這5個列表中的所有剩餘數加起來。我們第一次踢出n個號碼，第二次至少有n/2號碼，第三次n/4號碼等等。但是，在我得到3n個剩餘數字後，我不知道如何分析。

這個算法實際上能給我O（logn）嗎？

Answer 1

是的，它實際上可以。看看這些陳述

• 只有當我們有一個列表時，我們才能得到最終結果。除非我們至少有兩個名單，否則我們不能說這個。
• 算法的每一步我們正在削減一半的列表。如果列表中只有一個元素，我們將刪除整個列表。
• 讓我們來算一下，刪除列表需要多少步驟。在第一次刪除時，我們將刪除n/2項，第二個 - n/4等，直到一個元素離開，最後刪除列表。它會花費大約log（n）的操作（不知道它是真的log（n）還是log（n）+1，但是在兩種情況下都是O（log（n）））。
• 因此，我們需要消除5個列表（在最後一個列表中查找中位數的操作可以推廣到縮小列表的操作）。它需要O（log（n））來消除其中的一個，因此我們將在O（log（n））中執行所有的操作，因爲5是不變的。