QuickSort寻找中位数?
-
16-10-2019 - |
题
为什么使用QuickSort查找一组数字的中位数时,为什么最坏的方案$ mathcal {o} left(n^2 right)$?
如果您的算法不断选择大于或小于 全部 列表中的数字不会失败?例如,数字列表是:
$ s =(12,75,82,34,55,15,51)$
而且,您不断选择大于$ 82 $或低于$ 12 $的$ 12 $的数字,您的套装不会始终保持相同的尺寸吗?
如果您的算法不断选择一个创建$ 1 $的标准的数字,为什么最坏的情况是$ MATHCAL {O} left(n^2 right)$?考虑到根据 师父定理, ,$ d> log_b a $?
*其中$ d $是效率指数(即线性,指数等),$ b $是每次迭代时问题大小的因素,$ a $是子问题的数量,$ k $是级别。全比:$ t(n)= Mathcal {o} left(n^d right) *( frac {a} {b^d})^k $
解决方案
QuickSort用于排序,您所指的算法是一种选择算法 快速选择.
- 由于您只能选择枢轴列表中的数字#1从未发生过。
- 最坏的情况是,您不断选择一个将列表分为2个列表的数字:只有一个元素的列表和一个带有$ n-1 $元素的列表,如果在每次迭代中是这种情况,您只排除单个元素。
因此,您要进行$ n $操作,第二次迭代$ n-1 $操作,第三个$ n-2 $操作,...最后一个迭代1操作。
它是第一个$ n $自然数的总和:
$ 1+2+3+...+(n-2)+(n-1)+n = n = n(n-1)/2 $ operations = $ o(n^2)$
不隶属于 cs.stackexchange