程序员编程艺术:第三章、寻找最小的k个数

发布时间:2021-10-24 13:23:30

??????????????????? 程序员编程艺术:第三章、寻找最小的k个数


作者:July。
? 咱们先简单的理解,要求一个序列中最小的k个数,按照惯有的思维方式,很简单,先对这个序列从小到大排序,然后输出前面的最小的k个数即可。


1、 ? 至于选取什么的排序方法,我想你可能会第一时间想到快速排序,我们知道,快速排序*均所费时间为n*logn,然后再遍历序列中前k个元素输出,即可,总的时间复杂度为O(n*logn+k)=
O(n*logn)


2、 ? 咱们再进一步想想,题目并没有要求要查找的k个数,甚至后n-k个数是有序的,既然如此,咱们又何必对所有的n个数都进行排序列?

? 当然,更好的办法是维护k个元素的最大堆,原理与上述第2个方案一致,即用容量为k的最大堆存储最先遍历到的k个数,并假设它们即是最小的k个数,建堆费时O(k)后,有k1 O(n*logk)。此方法得益于在堆中,查找等各项操作时间复杂度均为logk(不然,就如上述思路2所述:直接用数组也可以找出前k个小的元素,用时O(n*k))。


4、 按编程之美第141页上解法二的所述,类似快速排序的划分方法,N个数存储在数组S中,再从数组中随机选取一个数X(
随机选取枢纽元,可做到线性期望时间O(N)的复杂度,在第二节论述),把数组划分为Sa和Sb俩部分,Sa<=X<=Sb,如果要查找的k个元素小于Sa的元素个数,则返回Sa中较小的k个元素,否则返回Sa中
所有元素+Sb中小的k-|Sa|个元素。
像上述过程一样,这个运用类似快速排序的partition的快速选择SELECT算法寻找最小的k个元素,在最坏情况下亦能做到O(N)的复杂度。不过值得一提的是,这个快速选择SELECT算法是选取数组中“中位数的中位数”作为枢纽元,而非随机选取枢纽元。


5、?? RANDOMIZED-SELECT,每次都是
随机选取数列中的一个元素作为主元,在0(n)的时间内找到第k小的元素,然后遍历输出前面的k个小的元素。 如果能的话,那么总的时间复杂度为线性期望时间:O(n+k)=
O(n)(当k比较小时)

???????? Ok,稍后第二节中,我会具体给出RANDOMIZED-SELECT(A, p, r, i)的整体完整伪码。在此之前,要明确一个问题:我们通常所熟知的快速排序是以固定的第一个或最后一个元素作为主元,每次递归划分都是不均等的,最后的*均时间复杂度为:O(n*logn),但RANDOMIZED-SELECT与普通的快速排序不同的是,每次递归都是随机选择序列从第一个到最后一个元素中任一一个作为主元。




6、?? 线性时间的排序,即计数排序,时间复杂度虽能达到
O(n),但限制条件太多,不常用。


7、???
updated: huaye502在本文的评论下指出:“可以用最小堆初始化数组,然后取这个优先队列前k个值。复杂度O(n)+k*O(log n)”。huaye502的意思是针对整个数组序列建最小堆,建堆所用时间为O(n)(算法导论一书上第6章第6.3节已经论证,在线性时间内,能将一个无序的数组建成一个最小堆),然后取堆中的前k个数,总的时间复杂度即为:
O(n+k*logn)


??? 关于上述第7点思路的继续阐述:至于思路7的O(n+k*logn)是否小于上述思路3的O(n*logk),即O(n+k*logn)?< O(n*logk)。粗略数学证明可参看如下第一幅图,我们可以这么解决:当k是常数,n趋向于无穷大时,求(n*logk)/(n+k*logn)的极限T,如果T>1,那么可得O(n*logk)>O(n+k*logn),也就是O(n+k*logn)< O(n*logk)。虽然这有违我们惯常的思维,然事实最终证明的确如此,这个极值T=logk>1,即采取建立n个元素的最小堆后取其前k个数的方法的复杂度小于采取常规的建立k个元素最大堆后通过比较寻找最小的k个数的方法的复杂度。但,最重要的是,如果建立n个元素的最小堆的话,那么其空间复杂度势必为O(N),而建立k个元素的最大堆的空间复杂度为O(k)。所以,综合考虑,我们一般还是选择用建立k个元素的最大堆的方法解决此类寻找最小的k个数的问题。


? ? 思路3准确的时间复杂度表述为:O(k+(n-k)*logk),思路7准确的时间复杂度表述为:O(n+k*logn),也就是如gbb21所述粗略证明:要证原式k+n*logk-n-k*logn>0,等价于证(logk-1)n-k*logn+k>,要证思路3的时间复杂度大于思路7的时间复杂度,等价于要证原式k+n*logk-klogk-n-k*logn>0,即证(logk-1)n - k*logn + k - klogk > 0。当when n -> +/inf(n趋向于正无穷大)时,logk-1-0-0>0,即只要满足logk-1>0即可。原式得证。即O(k+n*logk)>O(n+k*logn) =>O(n+k*logn)< O(n*logk),与上面得到的结论一致。


??? 事实上,是建立最大堆还是建立最小堆,其实际的程序运行时间相差并不大,运行时间都在一个数量级上。因为后续,我们还专门写了个程序进行测试,即针对1000w的数据寻找其中最小的k个数的问题,采取两种实现,一是采取常规的建立k个元素最大堆后通过比较寻找最小的k个数的方案,一是采取建立n个元素的最小堆,然后取其前k个数的方法,发现两相比较,运行时间实际上相差无几。结果可看下面的第二幅图。



??





8、???@lingyun310:与上述思路7类似,不同的是在对元素数组原地建最小堆O(n)后,然后提取K次,
但是每次提取时,换到顶部的元素只需要下移顶多k次就足够了,下移次数逐次减少(
而上述思路7每次提取都需要logn,所以提取k次,思路7需要k*logn。而本思路8只需要K^2)。此种方法的复杂度为O(n+k^2)。@July:对于这个O(n+k^2)的复杂度,我相当怀疑。因为据我所知,n个元素的堆,堆中任何一项操作的复杂度皆为logn,所以按理说,lingyun310方法的复杂度应该跟下述思路8一样,也为O(n+k*logn),而非O(n+k*k)。ok,先放到这,待时间考证
。06.02。

updated:


???? 你已经看到,它是随机选取数组中的任一元素为枢纽的,这就是本文下面的第二节RANDOMIZED-SELECT的问题了,只是要修正的是,此算法的*均时间复杂度为线性期望O(N)的时间。而,稍后在本文的第四节或本文文末,您还将会看到此问题的进一步阐述(SELECT算法,即快速选择算法),此SELECT算法能保证即使在最坏情况下,依然是线性O(N)的复杂度。



updated:


?? 1、为了照顾手中没编程之美这本书的friends,我拍了张照片,现贴于下供参考(提醒:1、书上为寻找最大的k个数,而我们面对的问题是寻找最小的k个数,两种形式,一个本质(该修改的地方,上文已经全部修改)。2、书中描述与上文思路4并无原理性出入,不过,勿被图中记的笔记所误导,因为之前也曾被书中的这个n*logk复杂度所误导过。ok,相信,看完本文后,你不会再有此疑惑):



??? 2、同时,在编程之美原书上此节的解法五的开头提到,“上面类似快速排序的方法*均时间复杂度是线性的”,我想上面的类似快速排序的方法,应该是指解法(即如上所述的类似快速排序partition过程的方法),但解法二得出的*均时间复杂度却为O(N*logk),明摆着前后矛盾(参见下图)。



??? 3、此文创作后的几天,已把本人的意见反馈给邹欣等人,下面是编程之美bop1的改版修订地址的页面截图(本人也在参加其改版修订的工作),下面的文字是我的记录(同时,本人声明,此狂想曲系列文章系我个人独立创作,与其它的事不相干):





..r]上时,所需时间是一个随机变量,记为T(n),我们可以这样得到线性期望值E [T(n)]的下界:程序RANDOMIZED-PARTITION会以等同的可能性返回数组中任何一个元素为主元,因此,对于每一个k,(1 ≤kn,子数组A[p ..q]有k个元素,它们全部小于或等于主元元素的概率为1/n.对k = 1, 2,...,n,我们定指示器Xk,为:


Xk = I{子数组A[p ..q]恰有k个元素} ,


我们假定元素的值不同,因此有


??????????E[Xk]=1/n


当调用RANDOMIZED-SELECT并且选择A[q]作为主元元素的时候,我们事先不知道是否会立即找到我们所想要的第i小的元素,因为,我们很有可能需要在子数组A[p ..q - 1], 或A[q + 1 ..r]上递归继续进行寻找.具体在哪一个子数组上递归寻找,视第i小的元素与A[q]的相对位置而定.


2、假设T(n)是单调递增的,我们可以将递归所需时间的界限限定在输入数组时可能输入的所需递归调用的最大时间(此句话,原中文版的翻译也是有问题的).换言之,我们断定,为得到一个上界,我们假定第i小的元素总是在划分的较大的一边,对一个给定的RANDOMIZED-SELECT,指示器Xk刚好在一个k值上取1,在其它的k值时,都是取0.当Xk =1时,可能要递归处理的俩个子数组的大小分别为k-1,和n-k,因此可得到递归式为


??????? ?


取期望值为:
- 1,n - k))是独立的随机变量(这个可以证明,证明此处略)。


3、下面,我们来考虑下表达式max(k - 1,n -k)的结果.我们有:


????????


如果n是偶数,从T(?)到T(n - 1)每个项在总和中刚好出现俩次,T(?)出现一次。因此,有


??????? ?


我们可以用替换法来解上面的递归式。假设对满足这个递归式初始条件的某个常数c,有T(n) ≤cn。我们假设对于小于某个常数c(稍后再来说明如何选取这个常数)的n,有T(n) =O(1)。 同时,还要选择一个常数a,使得对于所有的n>0,由上式中O(n)项(用来描述这个算法的运行时间中非递归的部分)所描述的函数,可由an从上方限界得到(这里,原中文版的翻译的确是有点含糊)。利用这个归纳假设,可以得到:


(此段原中文版翻译有点问题,上述文字已经修正过来,对应的此段原英文为:We solve the recurrence by substitution. Assume thatT(n)≤cn for some constant c that satisfies the initial conditions of the recurrence. We assume thatT(n) =O(1) forn less than some constant; we shall pick this constant later. We also pick a constanta such that the function described by theO(n) term above (which describes the non-recursive component of the running time of the algorithm) is bounded from above byan for alln> 0. Using this inductive hypothesis, we have)


????????


4、为了完成证明,还需要证明对足够大的n,上面最后一个表达式最大为cn,即要证明:cn/4 -c/2 -an ≥ 0.如果在俩边加上c/2,并且提取因子n,就可以得到n(c/4 -a) ≥c/2.只要我们选择的常数c能满足c/4 -a > 0, i.e.,即c > 4a,我们就可以将俩边同时除以c/4 -a, 最终得到:


??????????????? ?


综上,如果假设对n < 2c/(c -4a),有T(n) =O(1),我们就能得到E[T(n)] =O(n)。所以,最终我们可以得出这样的结论,并确认无疑:在*均情况下,任何顺序统计量(特别是中位数)都可以在线性时间内得到。



???? ?结论:?如你所见,RANDOMIZED-SELECT有线性期望时间O(N)的复杂度,但此RANDOMIZED-SELECT算法在最坏情况下有O(N^2)的复杂度。所以,我们得找出一种在最坏情况下也为线性时间的算法。稍后,在本文的第四节末,及本文文末部分,你将看到一种在最坏情况下是线性时间O(N)的复杂度的快速选择SELECT算法。


?


第三节、各执己见,百家争鸣


updated :本文昨晚发布后,现在朋友们之间,主要有以下几种观点(在彻底弄清之前,最好不要下结论):


?




    luuillu:我不认为随机快排比直接快排的时间复杂度小。使用快排处理数据前,我们是不知道数据的排列规律的,因此一般情况下,被处理的数据本来就是一组随机数据,对于随机数据再多进行一次随机化处理,数据仍然保持随机性,对排序没有更好的效果。?? 对一组数据采用随选主元的方法,在极端的情况下,也可能出现每次选出的主元恰好是从大到小排列的,此时时间复杂度为O(n^2).当然这个概率极低。随机选主元的好处在于,由于在现实中常常需要把一些数据保存为有序数据,因此,快速排序碰到有序数据的概率就会高一些,使用随机快排可以提高对这些数据的处理效率。这个概率虽然高一些,但仍属于特殊情况,不影响一般情况的时间复杂度。我觉得楼主上面提到的的思路4和思路5的时间复杂度是一样的。


    571楼 得分:0 Sorehead 回复于:2011-03-09 16:29:58

    这两天我总结了一下,有以下方法可以实现:



?总结:


????? 关于RANDOMIZED-SELECT(A, q + 1, r, i - k),期望运行时间为O(n)已经没有疑问了,更严格的论证在上面的第二节也已经给出来了。


???????? ok,现在,咱们剩下的问题是,除了此RANDOMIZED-SELECT(A, q + 1, r, i - k)方法(实用价值并不大)和计数排序,都可以做到O(n)之外,还有类似快速排序的partition过程,是否也能做到O(n)?


?


第四节、类似partition过程,最坏亦能做到O(n)?


???我想,经过上面的各路好汉的思路轰炸,您的头脑和思维肯定有所混乱了。ok,下面,我尽量以通俗易懂的方式来继续阐述咱们的问题。上面第三节的总结提出了一个问题,即类似快速排序的partition过程,是否也能做到O(n)?


??? 我们说对n个数进行排序,快速排序的*均时间复杂度为O(n*logn),这个n*logn的时间复杂度是如何得来的列?


?? 经过之前我的有关快速排序的三篇文章,相信您已经明了了以下过程:快速排序每次选取一个主元X,依据这个主元X,每次把整个序列划分为A,B俩个部分,且有Ax

?? 假如我们每次划分总是产生9:1 的划分,那么,快速排序运行时间的递归式为:T(n)=T(9n/10)+T(n/10)+cn。形成的递归树,(注:最后同样能推出T(n)=n*logn,即如下图中,每一层的代价为cn,共有logn层(深度),所以,最后的时间复杂度为O(n)*logn)如下:



??? 而我们知道,如果我们每次划分都是*衡的,即每次都划分为均等的两部分元素(对应上图,第一层1/2,1/2,,第二层1/4,1/4.....),那么,此时快速排序的运行时间的递归式为:


??? T (n) ≤ 2T (n/2) + Θ(n) ,同样,可推导出:T (n) = O(n lg n).


??? 这就是快速排序的*均时间复杂度的由来。


??? 那么,咱们要面对的问题是什么,要寻找n个数的序列中前k个元素。如何找列?假设咱们首先第一次对n个数运用快速排序的partition过程划分,主元为Xm,此刻找到的主元元素Xm肯定为序列中第m小的元素,此后,分为三种情况:
to describe the quickselect algorithm that uses the pivot selection rule given above. (我们将用术语“五分化中项的中项”来描述使用上面给出的枢纽元选择法的快速选择算法)。We will now show that median-of-median-of-five partitioning guarantees that each recursive subproblem is at most roughly 70 percent as large as the original(现在我们要证明,“五分化中项的中项”,得保证每个递归子问题的大小最多为原问题的大约70%). We will also show that the pivot can be computed quickly enough to guarantee an O (n) running time for the entire selection algorithm(我们还要证明,对于整个选择算法,枢纽元可以足够快的算出,以确保O(N)的运行时间。看到了没,这再次佐证了我们的类似快速排序的partition过程的分治方法为O(N)的观点)。


??? 咱们用比较大量的数据文件测试一下,如这个数据文件:



??? 输入k=4,即要从这大量的数据中寻找最小的k个数,可得到运行结果,如下图所示:



至于,这4个数,到底是不是上面大量数据中最小的4个数,这个,咱们就无从验证了,非人力之所能及也。毕。


?


?


第六节、stl之_nth_element ,逐步实现


??? 以下代码摘自stl中_nth_element的实现,且逐步追踪了各项操作,其完整代码如下:



第七节、再探Selection_algorithm,类似partition方法O(n)再次求证


网友反馈:
a good split when the array is partitioned. SELECT uses the deterministic partitioning algorithm PARTITION from quicksort (seeSection 7.1), modified to take the element to partition around as an input parameter(像RANDOMIZED-SELECT一样,SELECTT通过输入数组的递归划分来找出所求元素,但是,该算法的基本思想是要保证对数组的划分是个好的划分。SECLECT采用了取自快速排序的确定性划分算法partition,并做了修改,把划分主元元素作为其参数).


??? The SELECT algorithm determines theith smallest of an input array ofn > 1 elements by executing the following steps. (Ifn = 1, then SELECT merely returns its only input value as theith smallest.)(算法SELECT通过执行下列步骤来确定一个有n>1个元素的输入数组中的第i小的元素。(如果n=1,则SELECT返回它的唯一输入数值作为第i个最小值。))


  1. Divide then elements of the input array into? groups of 5 elements each and at most one group made up of the remainingn mod 5 elements.
  2. Find the median of each of the? groups by first insertion sorting the elements of each group (of which there are at most 5) and then picking the median from the sorted list of group elements.
  3. Use SELECT recursively to find the medianx of the? medians found in step 2. (If there are an even number of medians, then by our convention,x is the lower median.)
  4. Partition the input array around the median-of-mediansx using the modified version of PARTITION. Letk be one more than the number of elements on the low side of the partition, so thatx is thekth smallest element and there aren-k elements on the high side of the partition.(利用修改过的partition过程,按中位数的中位数x对输入数组进行划分,让k比划低去的元素数目多1,所以,x是第k小的元素,并且有n-k个元素在划分的高区)
  5. Ifi =k, then returnx. Otherwise, use SELECT recursively to find theith smallest element on the low side ifi <k, or the (i -k)th smallest element on the high side ifi >k.(如果要找的第i小的元素等于程序返回的k,即i=k,则返回x。否则,如果ik,则在高区间找第(i-k)个最小元素)


(以上五个步骤,即本文上面的第四节末中所提到的所谓“五分化中项的中项”的方法。)


?


??? To analyze the running time of SELECT, we first determine a lower bound on the number of elements that are greater than the partitioning element x. (为了分析SELECT的运行时间,先来确定大于划分主元元素x的的元素数的一个下界)Figure 9.1 is helpful in visualizing this bookkeeping. At least half of the medians found in step 2 are greater than[1] the median-of-medians x. Thus, at least half of the ? groupscontribute 3 elements that are greater than x, except for the one group that has fewer than 5 elements if 5 does not dividen exactly, and the one group containingx itself. Discounting these two groups, it follows that the number of elements greater thanx is at least:


???


?


???
is at least 3n/10 - 6. Thus, in the worst case, SELECT is called recursively on at most 7n/10 + 6 elements in step 5.


??? We can now develop a recurrence for the worst-case running timeT(n) of the algorithm SELECT. Steps 1, 2, and 4 take O(n) time. (Step 2 consists ofO(n) calls of insertion sort on sets of sizeO(1).) Step 3 takes timeT(?), and step 5 takes time at mostT(7n/10+ 6), assuming thatT is monotonically increasing. We make the assumption, which seems unmotivated at first, that any input of 140 or fewer elements requiresO(1) time; the origin of the magic constant 140 will be clear shortly. We can therefore obtain the recurrence:


??????? ?


??? We show that the running time is linear by substitution. More specifically, we will show thatT(n) ≤cn for some suitably large constant c and alln > 0. We begin by assuming thatT(n) ≤cn for some suitably large constantc and alln ≤ 140; this assumption holds ifc is large enough. We also pick a constanta such that the function described by theO(n) term above (which describes the non-recursive component of the running time of the algorithm) is bounded above byan for alln > 0. Substituting this inductive hypothesis into the right-hand side of the recurrence yields



T(n)

c? +c(7n/10 + 6) +an

?

cn/5 +c + 7cn/10 + 6c +an

?

=

9cn/10 + 7c +an

?

=

cn + (-cn/10 + 7c +an) ,












which is at mostcn if


??????????????


Inequality (9.2) is equivalent to the inequalityc ≥ 10a(n/(n - 70)) when n > 70. Because we assume thatn ≥ 140, we have n/(n - 70) ≤ 2, and so choosing c ≥ 20a will satisfyinequality (9.2). (Note that there is nothing special about the constant 140; we could replace it by any integer strictly greater than 70 and then choosec accordingly.) The worst-case running time of SELECT is therefore linear(因此,此SELECT的最坏情况的运行时间是线性的).


?


??? As in a comparison sort (seeSection 8.1), SELECT and RANDOMIZED-SELECT determine information about the relative order of elements only by comparing elements. Recall fromChapter 8 that sorting requires?(n lgn) time in the comparison model, even on average (see Problem 8-1). The linear-time sorting algorithms in Chapter 8 make assumptions about the input. In contrast, the linear-time selection algorithms in this chapter do not require any assumptions about the input. They are not subject to the ?(n lgn) lower bound because they manage to solve the selection problem without sorting.


(与比较排序(算法导论8.1节)中的一样,SELECT和RANDOMIZED-SELECT仅通过元素间的比较来确定它们之间的相对次序。在算法导论第8章中,我们知道在比较模型中,即使在*均情况下,排序仍然要O(n*logn)的时间。第8章得线性时间排序算法在输入上做了假设。相反地,本节提到的此类似partition过程的SELECT算法不需要关于输入的任何假设,它们不受下界O(n*logn)的约束,因为它们没有使用排序就解决了选择问题(看到了没,道出了此算法的本质阿))


??? Thus, the running time is linear because these algorithms do not sort; the linear-time behavior is not a result of assumptions about the input, as was the case for the sorting algorithms inChapter 8. Sorting requires?(n lgn) time in the comparison model, even on average (see Problem 8-1), and thus the method of sorting and indexing presented in the introduction to this chapter is asymptotically inefficient.(所以,本节中的选择算法之所以具有线性运行时间,是因为这些算法没有进行排序;线性时间的结论并不需要在输入上所任何假设,即可得到。.....)??



?


ok,综述全文,根据选取不同的元素作为主元(或枢纽)的情况,可简单总结如下:


程序员面试题狂想曲、第四章(更多有关海量数据处理,及Top K 算法问题(此问题已作为第三章续),第四章,择日发布。),五月份发布(*期内事情较多,且昨夜因修正此文足足熬到了凌晨4点(但室内并无海棠花),写一篇文章太耗精力和时间,见谅。有关本人动态,可关注本人微博:http://weibo.com/julyweibo。谢谢。July、updated,2011.05.05)。


ok,有任何问题,欢迎随时指出。谢谢。完。



?


版权声明:严禁用于商业用途,严禁出版。转载,请注明出处。违者,追究法律责任。

相关文档

  • 梦想造就成功的名言警句|关于梦想的名言警句
  • 甲鱼要煮多久才能熟
  • 学习吉他的步骤
  • 一世长宁,一生清欢
  • 高中班主任2020年-2020年学年度工作总结
  • 在centos6中用yum安装mysql失败解决办法
  • 超简单有趣的绕口令口诀
  • java中对象创建过程
  • 耳机音频线接法图解
  • 房地产销售5月份工作计划2020年
  • 九轴传感器matlab,【技术分享】九轴传感器之陀螺仪
  • 2020年师德师风个人总结4篇
  • 喉咙痒咳嗽怎么办?保护喉咙的方法是这样的
  • 凉拌蘑菇怎么做好吃凉拌蘑菇的家常做法
  • 让男人感动的句子
  • 女性炎症怎么治疗
  • 读书励志演讲稿中学
  • 初中作文经典素材积累
  • PPTV怎么打开弹幕
  • 工商局优秀党务工作者事迹材料精选多篇
  • 群英会蒋干中计周瑜几次笑的不同含义
  • 描述陕北的经典散文心驰神往的陕北
  • 【数据结构C语言】链栈的表示和实现
  • 《鲁滨孙漂流记》读后感范文1300字
  • 中级导游考试模拟试题及答案
  • 学习目的、态度、方法教育
  • 婴幼儿童床销售合同
  • 天天p图怎么把蓝底换白
  • 红茶大红袍的功效与作用
  • 最新工程车租赁合同范本
  • 猜你喜欢

    电脑版