找第k大数的时间复杂度
Tang Qiao
����������⣬�����öѽ��֮�⣬��һ���ÿ��ŵ�˼��Ľⷨ�����£�
������S��
����ҳ�һ��Ԫ��X���������Ϊ������Sa��Sb��Sa�е�Ԫ�ش��ڵ���X��Sb��Ԫ��С��X����ʱ�����������
1. Sa��Ԫ�صĸ���С��k����Sb�еĵ�k-|Sa|��Ԫ�ؼ�Ϊ��k����
2. Sa��Ԫ�صĸ�����ڵ���k����Sa�еĵ�k��
��
�����ǣ���μ��������㷨��ƽ��ʱ�临�Ӷȣ�����һ�£��������2��������partition����ƽ�������Ҫlog(n)�Ρ�
ÿ��partition��Ҫ�ƶ���Ԫ�ظ�����������㣬ƽ���һ����n�����ڶ����� n/2 ����
��ô���ܵ�ƽ��ʱ�临�Ӷ���ô���أ�
Xiang Wang
有个问题是：从一个无序的数组里面找出第k大的数。
对于这个问题，除了用堆解决之外，有一种用快排的思想的解法，如下：
从数组S中 随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：
这样递归下去，最终不用把整个数组排序就可以找到第k大数。
1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；
2. Sa中元素的个数大于等于k，则返回Sa中的第k大 数。
问题是，如何计算这种算法的平均时间复杂度？简单分析一下，把数组分2部分这种partition操作平均情况下要log(n)次。
每个partition需要移动的元素个数这个不好算，平均第一次是n个，第二次是 n/2 个。
那么，总的平均时间复杂度怎么算呢？
--
窦小蹦
Wu Yin
有个问题是：从一个无序的数组里面找出第k大的数。
对于这个问题，除了用堆解决之外，有一种用快排的思想的解法，如下：
从数组S中 随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：
这样递归下去，最终不用把整个数组排序就可以找到第k大数。
1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；
2. Sa中元素的个数大于等于k，则返回Sa中的第k大 数。
问题是，如何计算这种算法的平均时间复杂度？简单分析一下，把数组分2部分这种partition操作平均情况下要log(n)次。
每个partition需要移动的元素个数这个不好算，平均第一次是n个，第二次是 n/2 个。
那么，总的平均时间复杂度怎么算呢？
--
是非成败转头空。
青山依旧在，几度夕阳红。
白发渔樵江渚上，惯看秋月春风。
一壶浊酒喜相逢。
古今多少事，都付笑谈中。
----------
Email: wyw...@gmail.com
Gtalk: wyw...@gmail.com
MSN: wyw...@hotmail.com
Wu Yin
嗯，就是O(N)，而且那个证明过特BT。。。我还写过一个泛型版的linear_selection。但是注意一个限制，原始数据得无重复，否则CLRS上那个算法(LZ的也一样)是得不到正确结果的。
Xinyu LIU
每隔一段时间就有人问K-th selection问题(或曰n-th selection)。
上次是这里：
https://groups.google.com/d/topic/pongba/33UW3x5oKfc/discussion
想严格证明的话，需要用数学希望的知识。上次我给了个不求甚解的解释。
另外在那个thread，我给过另外一个解法：
function nth(xs, k)
l <- 1
u <- length xs
loop
x <- max(xs[1..k])
y <- min(xs[k+1..u])
if x < y then
return
else
swap(x, y)
l <- partition xs[1..k] with x
u <- partition xs[k_1..n] with y
有个问题是：从一个无序的数组里面找出第k大的数。
对于这个问题，除了用堆解决之外，有一种用快排的思想的解法，如下：
从数组S中 随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：
这样递归下去，最终不用把整个数组排序就可以找到第k大数。
1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；
2. Sa中元素的个数大于等于k，则返回Sa中的第k大 数。
问题是，如何计算这种算法的平均时间复杂度？简单分析一下，把数组分2部分这种partition操作平均情况下要log(n)次。
每个partition需要移动的元素个数这个不好算，平均第一次是n个，第二次是 n/2 个。
那么，总的平均时间复杂度怎么算呢？
--
Larry, LIU Xinyu
https://sites.google.com/site/algoxy/
https://github.com/liuxinyu95/AlgoXY