我已阅读关于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