平均中位數算法遞推關係

Question

的我知道線性選擇（中位數算法的中位數）復發公式如下：

T(n) <= an + T(n/5) + T(7n/10) 

但是，在將這些術語從何而來？我一直在努力去理解，但我非常困惑。任何人都可以擺脫一些光？

Answer 1

最好的嘗試：

，公式只適用於當你這樣做的5組的中位數，否則它會改變。等式的一部分是算法遍歷所有元素並將它們分組爲5所花費的時間.T（n/5）是爲每組5箇中值找到所需的時間。由於爲n存在5.

T（7N/10）/ 5基團將需要更多的時間...

當執行中位數元素被分成4個象限的中位數。 3/10元素大於中位數的中位數，3/10元素小於中位數的中位數。另外4/10分成2/10組2/10。這些是你不確定它們是否大於或小於中位數中位數的因素。因此，您可能擁有的大於或小於中位數中位數的元素的最大數量是3/10 + 2/10 + 2/10 = 7/10。所以T（7n/10）是繼續方程的一部分，數值的最大段大於/小於中位數的中位數......

希望這種說法有道理。