發現未分類的列表

我想找到沒有排序的列表中位數約約中位數，我知道兩算法發現未分類的列表

算法1 quickselect

算法的2-位數的中位數

我不能使用快速選擇我的項目，因爲它在最壞的情況下需要O（n^2）。我聽說過中位數的中位數，但是我的同事們建議它用一些常數因子來處理O（n）。因此它的時間複雜度是Cn，常數因子與快速選擇相比是大的。我想知道與中位數中位數相關的常數因子是什麼？以及爲什麼中位數中位數不使用9位元的中位數？
還是他們的任何其他算法來找到線性時間O（n）的約中值？

來源

2014-02-18 asd

看到http://stackoverflow.com/questions/9489061/understanding-median-of-medians-algorithm –

[查找一個未排序的陣列的中值]的可能重複（http://stackoverflow.com/questions/10662013 /發現數組的中位數） –

你在問3個相當不同的問題 - 將這些問題分成3個不同的問題可能會更好，因爲問一個問題中的多個問題不會真正的[格式]（這是最後一個答案，所以這是在這個問題上留下的明顯選擇）。 [Wikipedia]（http://en.wikipedia.org/wiki/Median_of_medians）回答你的第二個問題，假設你理解它。前兩個問題可能會更好地適用於[cs.se]，但可能都需要您的一些工作來嘗試自己弄清楚。 – Dukeling

雖然我不會很快放棄quickselect，因爲它的最壞情況下的性能將大大不可能有正確挑選的支點......

也許introselect：

Introselect（以下簡稱「內省選擇「）是一種選擇算法，它是具有快速平均性能和最佳最差情況性能的快速選擇和中位數的混合。

Introselect通過快速選擇樂觀地開始工作，並且如果在沒有充分進展的情況下遞歸太多次，則只切換到最差時間線性算法。切換策略是該算法的主要技術內容。簡單地將遞歸限制在恆定深度是不夠的，因爲這會使算法在所有足夠大的列表上切換。 Musser討論了幾種簡單的方法：

跟蹤到目前爲止處理的子分區的大小列表。如果在任何時候進行k次遞歸調用而不減半列表大小，對於一些小的正k值，切換到最壞情況的線性算法。

總計到目前爲止產生的所有分區的大小。如果這超過列表大小乘以一個小的正常數k，則切換到最壞情況的線性算法。這個總和很容易在單個標量變量中跟蹤。

兩種方法都將遞歸深度限制爲k⌈logn⌉= O（log n），並將總運行時間限制爲O（n）。

來源

2014-02-18 15:49:23 Dukeling

發現未分類的列表

回答

相關問題