我已閱讀關於selection algorithm，我有一個問題，也許它看起來很愚蠢！但爲什麼我們將數組視爲5個元素的組？我們可以考慮與7或3個元素??謝謝還有任何鏈接，以幫助我更好地理解這個目標？約選擇算法
這也是我的證明，當我們考慮具有3個元素的數組並且它仍然是n的階數時，爲什麼？這是正確的嗎？
T(n)<=T(n/3)+T(n/3)+theta(n)
claim: T(n)<=cn
proof: For all k<=n : T(n)<=ck
T(n)<=(nc/3)+(nc/3)+theta(n)
T(n)<= (2nc/3)+theta(n)
T(n)<=cn-(cn/3-theta(n)) and for c>=3 theta(n) this algorithm with this condition will have an order of n,too !!!!
我認爲你犯了一個錯誤的T（n）。它應該是T（n）= T（n/3）+ T（2n/3）+ O（n）。
T（n/3）用於找到關鍵點（中位數）。所有n/3組中僅有一半的中位數小於樞軸。這些羣體有兩個比樞軸小的元素。給出2 *（1/2 * n/3）== n/3個元素小於主元。因此只有33％必須小於樞軸（而33％必須大於樞軸）。所以，在更糟糕的情況下，下一次迭代T（2n/3）仍然有66％。
我看不出你的證明，但現在不可能證明它。對？
是的你是對的應該是T（2n/3）非常感謝 – user355002 2010-06-18 14:36:11
有點谷歌搜索，我發現this。關於爲什麼5有一個非常小的部分，但它並沒有真正回答你的問題，只是說它是可以使用的最小奇數（對於給出一箇中位數必須是奇數）。有一些數學證明，它不能是3（但我自己並不真正理解）。我認爲基本上可以說它可以是奇數，5或更大，但越小越好，我猜是因爲在小組中找到中位數會更快？
謝謝我也編輯了我的帖子，但是當我用3對它進行分組時，它仍然在Order（n）上工作？哪裏不正確？ – user355002 2010-06-18 09:59:28
對不起，但正如我在答覆中所說的那樣，數學部分是我沒有得到的一點，所以我不能真正評論證明的合法性，我只是想指出你的方向我在這個主題上找到了一些信息。 – DaveJohnston 2010-06-18 11:11:57
「選擇算法」？在什麼情況下？網絡編程？還有別的嗎？ – 2010-06-18 07:28:08
請花一些時間來制定一個連貫的問題 - 沒關係，如果你的英語不完美，但至少提供足夠的細節來提供有意義的答案。 – 2010-06-18 07:31:02
這是我的數據結構課，我讀了這個算法，它讓我問這個問題。 – user355002 2010-06-18 07:36:51