数学之美番外篇:快排为什么那样快

目录

0. 前言

1. 猜数字

2. 称球

3. 排序

    3.1 为什么堆排比快排慢

    3.2 为什么快排其实也不是那么快

    3.3 基排又为什么那么快呢

4. 信息论!信息论?

5. 小结

0. 前言

知道这个理论是在TopLanguage上的一次讨论,先是g9转了David MacKay的一篇文章,然后引发了牛人们的一场关于信息论的讨论。Anyway,正如g9很久以前在Blog里面所的:

有时无知是福。俺看到一点新鲜的科普也能觉得造化神奇。刚才读Gerald Jay Sussman(SICP作者)的文章,Building Robust Systems – an essay,竟然心如小鹿乱撞,手心湿润,仿佛第一次握住初恋情人温柔的手。

而看到MacKay的这篇文章我也有这种感觉——以前模糊的东西忽然有了深刻的解释,一切顿时变得明白无比。原来看问题的角度或层面能够带来这么大的变化。再一次印证了越是深刻的原理往往越是简单和强大。所以说,土鳖也有土鳖的幸福:P

这篇文章相当于MacKay原文的白话文版。MacKay在原文中用到了信息论的知识,后者在我看来并不是必须的,尽管计算的时候方便,但与本质无关。所以我用大白话解释了一通。

1. 猜数字

我们先来玩一个猜数字游戏:我心里默念一个1~64之间的数,你来猜(你只能问答案是“是”或“否”的问题)。为了保证不论在什么情况下都能以尽量少的次数猜中,你应该采取什么策略呢?很显然,二分。先是猜是不是位于1~32之间,排除掉一半可能性,然后对区间继续二分。这种策略能够保证无论数字怎么跟你捉迷藏,都能在log_2{n}次以内猜中。用算法的术语来说就是它的下界是最好的。

我们再来回顾一下这个游戏所蕴含的本质:为什么这种策略具有最优下界?答案也很简单,这个策略是平衡的。反之如果策略不是平衡的,比如问是不是在1~10之间,那么一旦发现不是在1~10之间的话就会剩下比N/2更多的可能性需要去考察了。

徐宥在讨论中提到,这种策略的本质可以概括成“让未知世界无机可乘”。它是没有“弱点的”,答案的任何一个分支都是等概率的。反之,一旦某个分支蕴含的可能性更多,当情况落到那个分支上的时候你就郁闷了。比如猜数字游戏最糟糕的策略就是一个一个的猜:是1吗?是2吗?… 因为这种猜法最差的情况下需要64次才能猜对,下界非常糟糕。二分搜索为什么好,就是因为它每次都将可能性排除一半并且无论如何都能排除一半(它是最糟情况下表现最好的)。

2. 称球

12个小球,其中有一个是坏球。有一架天平。需要你用最少的称次数来确定哪个小球是坏的并且它到底是轻还是重。

这个问题是一道流传已久的智力题。网络上也有很多讲解,还有泛化到N个球的情况下的严格证明。也有零星的一些地方提到从信息论的角度来看待最优解法。本来我一直认为这道题目除了试错之外没有其它高妙的思路了,只能一个个方法试,并尽量从结果中寻找信息,然后看看哪种方案最少。

然而,实际上它的确有其它的思路,一个更本质的思路,而且根本用不着信息论这么拗口的知识。

我们先回顾一下猜数字游戏。为了保证任何情况下以最少次数猜中,我们的策略是每次都排除恰好一半的可能性。类比到称球问题上:坏球可能是12个球中的任意一个,这就是12种可能性;而其中每种可能性下坏球可能轻也可能重。于是“坏球是哪个球,是轻是重”这个问题的答案就有12×2=24种可能性。现在我们用天平来称球,就等同于对这24种可能性发问,由于天平的输出结果有三种“平衡、左倾、右倾”,这就相当于我们的问题有三个答案,即可以将所有的可能性切成三份,根据猜数字游戏的启发,我们应当尽量让这三个分支概率均等,即平均切分所有的可能性为三等份。如此一来的话一次称量就可以将答案的可能性缩减为原来的1/3,三次就能缩减为1/27。而总共才有24种可能性,所以理论上是完全可以3次称出来的。

如何称的指导原则有了,构造一个称的策略就不是什么太困难的事情了。首先不妨解释一下为什么最直观的称法不是最优的——6、6称:在6、6称的时候,天平平衡的可能性是0。刚才说了,最优策略应该使得天平三种状态的概率均等,这样才能三等分答案的所有可能性。

为了更清楚的看待这个问题,我们不妨假设有6个球,来考虑一下3、3称和2、2称的区别:

在未称之前,一共有12种可能性:1轻、1重、2轻、2重、…、6轻、6重。现在将1、2、3号放在左边,4、5、6放在右边3、3称了之后,不失一般性假设天平左倾,那么小球的可能性就变成了原来的一半(6种):1重、2重、3重、4轻、5轻、6轻。即这种称法能排除一半可能性。

现在再来看2、2称法,即1、2放左边,3、4放右边,剩下的5、6不称,放一边。假设结果是天平平衡,那么可能性剩下——4种:5重、5轻、6重、6轻。假设天平左倾,可能性也剩下4种:1重、2重、3轻、4轻。右倾和左倾的情况类似。总之,这种称法,不管天平结果如何,情况都被我们缩小到了原来的三分之一!我们充分利用了“天平的结果状态可能有三种”这个条件来三等分所有可能性,而不是二等分。

说到这里,剩下的事情就实在很简单了:第二步称法,只要记着这样一个指导思想——你选择的称法必须使得当天平平衡的时候答案剩下的可能性和天平左倾(右倾)的时候答案剩下的可能性一样多。实际上,这等同于你得选择一种称法,使得天平输出三种结果的概率是均等的,因为天平输出某个结果的概率就等同于所有支持这个结果(左倾、右倾、平衡)的答案可能性的和,并且答案的每个可能性都是等概率的。

MacKay在他的书《Information Theory: Inference and Learning Algorithms》(作者开放免费电子书)里面4.1节专门讲了这个称球问题,还画了一张不错的图,我就照抄了:

2313120

图中“1+”是指“1号小球为重”这一可能性。一开始一共有24种可能性。4、4称了之后不管哪种情况(分支),剩下来的可能性总是4种。这是一个完美的三分。然后对每个分支构造第二次称法,这里你只要稍加演算就可以发现,分支1上的第二次称法,即“1、2、6对3、4、5”这种称法,天平输出三种结果的可能性是均等的(严格来说是几乎均等)。这就是为什么这个称法能够在最坏的情况下也能表现最好的原因,没有哪个分支是它的弱点,它必然能将情况缩小到原来的1/3。

3. 排序

用前面的看问题视角,排序的本质可以这样来表述:一组未排序的N个数字,它们一共有N!种重排,其中只有一种排列是满足题意的(譬如从大到小排列)。换句话说,排序问题的可能性一共有N!种。任何基于比较的排序的基本操作单元都是“比较a和b”,这就相当于猜数字游戏里面的一个问句,显然这个问句的答案只能是“是”或“否”,一个只有两种输出的问题最多只能将可能性空间切成两半,根据上面的思路,最佳切法就是切成1/2和1/2。也就是说,我们希望在比较了a和b的大小关系之后,如果发现a<b的话剩下的排列可能性就变成N!/2,如果发现a>b也是剩下N!/2种可能性。由于假设每种排列的概率是均等的,所以这也就意味着支持a<b的排列一共有N!/2个,支持a>b的也是N!/2个,换言之,a<b的概率等于a>b的概率。

我们希望每次在比较a和b的时候,a<b和a>b的概率是均等的,这样我们就能保证无论如何都能将可能性缩小为原来的一半了!最优下界。

一个直接的推论是,如果每次都像上面这样的完美比较,那么N个元素的N!种可能排列只需要log_2{N!}就排查玩了,而log_2{N!}近似于NlogN。这正是快排的复杂度。

3.1 为什么堆排比快排慢

回顾一下堆排的过程:

1. 建立最大堆(堆顶的元素大于其两个儿子,两个儿子又分别大于它们各自下属的两个儿子… 以此类推)

2. 将堆顶的元素和最后一个元素对调(相当于将堆顶元素(最大值)拿走,然后将堆底的那个元素补上它的空缺),然后让那最后一个元素从顶上往下滑到恰当的位置(重新使堆最大化)。

3. 重复第2步。

这里的关键问题就在于第2步,堆底的元素肯定很小,将它拿到堆顶和原本属于最大元素的两个子节点比较,它比它们大的可能性是微乎其微的。实际上它肯定小于其中的一个儿子。而大于另一个儿子的可能性非常小。于是,这一次比较的结果就是概率不均等的,根据前面的分析,概率不均等的比较是不明智的,因为它并不能保证在糟糕情况下也能将问题的可能性削减到原本的1/2。可以想像一种极端情况,如果a肯定小于b,那么比较a和b就会什么信息也得不到——原本剩下多少可能性还是剩下多少可能性。

在堆排里面有大量这种近乎无效的比较,因为被拿到堆顶的那个元素几乎肯定是很小的,而靠近堆顶的元素又几乎肯定是很大的,将一个很小的数和一个很大的数比较,结果几乎肯定是“小于”的,这就意味着问题的可能性只被排除掉了很小一部分。

这就是为什么堆排比较慢(堆排虽然和快排一样复杂度都是O(NlogN)但堆排复杂度的常系数更大)。

MacKay也提供了一个修改版的堆排:每次不是将堆底的元素拿到上面去,而是直接比较堆顶(最大)元素的两个儿子,即选出次大的元素。由于这两个儿子之间的大小关系是很不确定的,两者都很大,说不好哪个更大哪个更小,所以这次比较的两个结果就是概率均等的了。具体参考这里

3.2 为什么快排其实也不是那么快

我们考虑快排的过程:随机选择一个元素做“轴元素”,将所有大于轴元素的移到左边,其余移到右边。根据这个过程,快排的第一次比较就是将一个元素和轴元素比较,这个时候显而易见的是,“大于”和“小于”的可能性各占一半。这是一次漂亮的比较。

然而,快排的第二次比较就不那么高明了:我们不妨令轴元素为pivot,第一次比较结果是a1<pivot,那么可以证明第二次比较a2也小于pivot的可能性是2/3!这容易证明:如果a2>pivot的话,那么a1,a2,pivot这三个元素之间的关系就完全确定了——a1<pivot<a2,剩下来的元素排列的可能性我们不妨记为P(不需要具体算出来)。而如果a2<pivot呢?那么a1和a2的关系就仍然是不确定的,也就是说,这个分支里面含有两种情况:a1<a2<pivot,以及a2<a1<pivot。对于其中任一种情况,剩下的元素排列的可能性都是P,于是这个分支里面剩下的排列可能性就是2P。所以当a2<pivot的时候,还剩下2/3的可能性需要排查。

再进一步,如果第二步比较果真发现a2<pivot的话,第三步比较就更不妙了,模仿上面的推理,a3<pivot的概率将会是3/4!

这就是快排也不那么快的原因,因为它也没有做到每次比较都能将剩下的可能性砍掉一半。

3.3 鸡排为什么又那么快呢?

传统的解释是:基排不是基于比较的,所以不具有后者的局限性。话是没错,但其实还可以将它和基于比较的排序做一个类比。

基排的过程也许是源于我们理顺一副牌的过程:如果你有N(N<=13)张牌,乱序,如何理顺呢?我们假象桌上有十三个位置,然后我们将手里的牌一张一张放出去,如果是3,就放在位置3上,如果是J,就放在位置11上,放完了之后从位置1到位置13收集所有的牌(没有牌的位置上不收集任何牌)。

我们可以这样来理解基排高效的本质原因:假设前i张牌都已经放到了它们对应的位置上,第i+1张牌放出去的时候,实际上就相当于“一下子”就确立了它和前i张牌的大小关系,用O(1)的操作就将这张牌正确地插入到了前i张牌中的正确位置上,这个效果就相当于插入排序的第i轮原本需要比较O(i)次的,现在只需要O(1)了。

但是,为什么基排能够达到这个效果呢?上面只是解释了过程,解释了过程不代表解释了本质。

当i张牌放到位之后,放置第i+1张牌的时候有多少种可能性?大约i+1种,因为前i张牌将13个位置分割成了i+1个区间——第i+1张牌可以落在任意一个区间。所以放置第i+1张牌就好比是询问这样一个问题:“这张牌落在哪个区间呢?”而这个问题的答案有i+1种可能性?所以它就将剩下来的可能性均分成了i+1份(换句话说,砍掉了i/i+1的可能性!)。再看看基于比较的排序吧:由于每次比较只有两种结果,所以最多只能将剩下的可能性砍掉一半。

这就是为什么基排要快得多。而所有基于比较的排序都逃脱不了NlogN的宿命。

4. 信息论!信息论?

本来呢,MacKay写那篇文章是想用信息论来解释为什么堆排慢,以及为什么快排也慢的。MacKay在他的文章中的解释是,只有提出每种答案的概率都均等的问题,才能获得最大信息量。然而,仔细一想,其实这里信息论并不是因,而是果。这里不需要用信息论就完全能够解释,而且更明白。信息论只是对这个解释的一个形式化。当然,信息论在其它地方还是有应用的。但这里其实用不着信息论这么重量级的东西(也许具体计算一些数据的时候是需要的),而是只需要一种看问题的本质视角:将排序问题看成和猜数字一样,是通过问问题来缩小/排除(narrow down)结果的可能性区间,这样一来,就会发现,“最好的问题”就是那些能够均分所有可能性的问题,因为那样的话不管问题的答案如何,都能排除掉k-1/k(k为问题的答案有多少种输出——猜数字里面是2,称球里面是3)种可能性,而不均衡的问题总会有一个或一些答案分支排除掉的可能性要小于k-1/k。于是策略的下界就被拖累了。

5. 小结

这的确是“小结”,因为两点:

1. 这个问题可以有信息论的理论解释,而信息论则是一个相当大的领域了。

2. 文中提到的这种看问题的视角除了用于排序、称球,还能够运用到哪些问题上(比如搜索)。

Update(06/13/2008) : 徐宥在讨论中继续提到

另外,这几天我重新把TAOCP 第三卷(第二版)翻出来看了看 Knuth 怎么说这个问题的, 发现真是牛大了:

先说性能:

pp148, section 5.2.3 说:

When N = 1000, the approximate average runiing time on MIX are
160000u for heapsort
130000u for shellsort
80000u  for quicksort

这里,  Knuth 同学发现一般情况下 heapsort 表现很不好. 于是,在下文他就说,习题18 (pp156, 难度21)

(R.W.Floyd) During the selection phase of heapsort, the key K tends to
be quite small, so that nearly all the comparisons in step H6 find
K<K_j. Show how to modify the algorithm so that K is not compared with
K_j in the main loop of the computation, thereby nearly cutting the
average number of comparisons in half.

答案里面的方法和DMK的方法是一样的。(我觉得DMK是看了这个论文或者TAoCP的) 这里说 by half,就正好和快排差不多了。

再说信息论分析:

在5.3.1 (pp181) 高爷爷就说, “排序问题可以看成是一个树上的鸟儿排排站的问题. (还特地画了一棵树), 下一段就说, 其实这个也
有等价说法, 就是信息论, 我们从称球问题说起…”

然后后面一直讲信息论和最小比较排序…

高爷爷真不愧是姓高的,囧rz..

73 Comments

  1. colin | | Reply

    快速排序为什么比堆排序要快?
    是因为 任何一个分支都是等概率的答案,才能在最糟糕的情况下表现最好。
    就像周长相等的长方形和正方形,正方形的面积总是最大的。

  2. mark | | Reply

    那个称球问题,1+2+6-对3+4+5-, 假设1+2+6-在天枰的左边,3+4+5-在天枰的右边,若平衡,则7-8-,然后把7对8称一次就可以得出来(应为已经确定是轻的了);
    那若左边重,即 1+2+6- > 3+4+5- 这个下一次称(仅剩一次了)该如何称呢?这个还不能确定是轻了还是重了啊(是5-轻了呢?还是1+2+重了呢?)

  3. 陈可 | | Reply

    鸡排那么快的原因我认为还可以这么理解:
    电脑通过数组或类似的东西来实现”预先排序“

  4. 汤勇 | | Reply

    一下就清晰了

  5. 藍-乐调 | | Reply

    快排为什么那样快

  6. 忘余尘 | | Reply

    高屋建瓴

  7. vwork | | Reply

    第一次比较确定后,三个数的关系有a1<a2< p,a2<a1<p, a1< p< a2,三种情况,a2<p是2/3。
    三个数可能的位置关系是A(3,3),第一次比较可以排除一半,而第二次比较,运气好可以排除掉2/3,不好只能排除掉1/3。
    列出各种情况会更好理解,5个数排序的话,共有120种情况,中有一种是对的,第一次可以排除1/2,即60种,第二次运气不好只能排除掉20种。

  8. 理科计划购房的撒 | | Reply

    a2跟pivot比较,a2>p,a2<p都是1/2
    此时有3种排序,确定其中一种,余下的entropy是E
    那就很显然了,脸不好,就是走到了2E,脸好就是E
    这就是2/3的说法了

  9. 中国人瘦 | | Reply

    称球问题:
    第一次称:左盘放置1、2、3、4号球, 右盘放置5、6、7、8号球
    第二次称:左盘放置1、5、9、11号球,右盘放置2、3、6、10号球
    第三次称:左盘放置4、8、9、10号球,右盘放置1、2、5、12号球
    详解可参考维基百科,称球问题
    http://zh.wikipedia.org/wiki/%E7%A8%B1%E7%90%83%E5%95%8F%E9%A1%8C

  10. 猪一只 | | Reply

    博主,你好 快排分析那你写错了吧,【所以当a2<pivot的时候,还剩下2/3的可能性需要排查。】这里应该是1/2才对,是个后验概率,而对于a3的概率p(x3| a2<pivot && a3<pivot) = 2/3 (x3表示还需排查的概率)

    • mihooke | |

      同意!一开始我没看出来,后来看了自己以前写的文章,突然发现不对劲,回过头来看博主的文章,才发现博主这点上分析错误了。

  11. SFENP'草帽 | | Reply

    我对于快排有些疑惑,快排不一定是等分等概率才快。而是哪怕是1/9和8/9也是很稳定的。

  12. zhouleyu.com | | Reply

    关于这段分析: ”而log_2{N!}近似于NlogN。这正是快排的复杂度“

  13. Keith | | Reply

    关于这段分析: ”而log_2{N!}近似于NlogN。这正是快排的复杂度“, 我不是很理解.
    实际是说: lim N!/(N^N) =1 ? are you sure ?
    作者的意思应该是如果能利用每次比较能够将可能的解缩小为原来的一半,那么这个算法就应该是最优的。

    • xiefubao | |

      这数学推的,算法导论肯定没好好学。

  14. kmtv2013 | | Reply

    温热问题34554zhangi{1..n]
    procedure qurst(l,h:integer)intteeger;
    var i,n,j,k,n:integer;
    begin
    i:=l;j:=r;
    m:=a[(i+j)div 2];
    repeat
    while a <m then inc(i);
    while a >m then dec(j);
    if i<=j then
    begin
    t:=a ; a :=a ; a :=t;
    inc(i); dec(j);
    end;
    until i>j;
    if i<h then qsort(i,h);
    if j>l then qsort(l,j);
    end;;

  15. 螃蟹009 | | Reply

    以1-8为例,
    1 2 3 4 5 6 7 8
    理论上应该最多检测3次?
    我们假定选8
    二分:
    第一次猜4 小
    第二次猜6 小
    第三次猜7 小
    第四次猜8 OK

  16. 螃蟹009 | | Reply

    ========================================================
    我心里默念一个1~64之间的数,你来猜(你只能问答案是“是”或“否”的问题)。为了保证不论在什么情况下都能以尽量少的次数猜中,你应该采取什么策略呢?很显然,二分。先是猜是不是位于1~32之间,排除掉一半可能性,然后对区间继续二分。这种策略能够保证无论数字怎么跟你捉迷藏,都能在log_2{n}次以内猜中
    ========================================================

  17. 神魔铩羽 | | Reply

    怎么感觉上界和下界说反了,下界不应该是最好情况么

  18. 洪鑫 | | Reply

    鹏神,你好。‘’3.3 鸡排为什么又那么快‘’ 这部分里面扑克牌的例子是不是属于桶排序(bucket sort)啊?基排是radix sort呀。

  19. wuef | | Reply

    非常精彩,世界有些规律就是那么和谐统一。

  20. 王彦皓 | | Reply

    突然想到最大熵原理 最近cs contest正好需要 要好好研究一下了!是时候开始学术了!

  21. 2号领导 | | Reply

    有时无知是福。俺看到一点新鲜的科普也能觉得造化神奇。刚才读Gerald Jay Sussman(SICP作者)的文章,Building Robust Systems – an essay,竟然心如小鹿乱撞,手心湿润,仿佛第一次握住初恋情人温柔的手。

  22. tenos | | Reply

    第一次比较结果是a1<pivot,那么可以证明第二次比较a2也小于pivot的可能性是2/3。这个为什么啊?

  23. ouqi | | Reply

    同不明白这一块:
    然而,快排的第二次比较就不那么高明了:我们不妨令轴元素为pivot,第一次比较结果是a1<pivot,那么可以证明第二次比较a2也小于pivot的可能性是2/3!这容易证明:如果a2>pivot的话,那么a1,a2,pivot这三个元素之间的关系就完全确定了——a1<pivot<a2,剩下来的元素排列的可能性我们不妨记为P(不需要具体算出来)。而如果a2<pivot呢?那么a1和a2的关系就仍然是不确定的,也就是说,这个分支里面含有两种情况:a1<a2<pivot,以及a2<a1<pivot。对于其中任一种情况,剩下的元素排列的可能性都是P,于是这个分支里面剩下的排列可能性就是2P。所以当a2<pivot的时候,还剩下2/3的可能性需要排查。

    我的疑惑在于,第一次的a2是什么,为什么要把第二次的排序和第一次的排序相关联?
    不明白您定义的第二次排序是什么,我以为的第二次排序是对第一次的起始位置到第一次的pivot之间的数字的排序,那么第二次的privot又是重新选定的。也就是说在第一次排序之后,任何一个值跟第一次的privot的大小关系都是确定了的,要么比他大 要么比他小。那您说a2是什么?

  24. 鸡翅呀鸡翅 | | Reply

    哇高爷爷果然是神人也,查了一下73年v3的第一版就有神论~~~膜拜orz~~~

    • KayGuoWhu | |

      高德纳

  25. icrt_ | | Reply

    真心佩服了。之前觉得称球问题没有什么,看这文章才知道原来有这么多的东西!

  26. imgen | | Reply

    关于称球问题,我正是用了信息论的方法为指引,三分而称球,而且我也给出了推广到N的解法,从中获得了很多乐趣和满足。不过那是在大学时代了,久远了

  27. simple | | Reply

    鸡排之所以快,我觉得还可以用另一种说法(以13张牌的例子为例):第i张牌确定位置后,放第i+1张牌时,桌上剩下的位置还有 13-i 个,即放牌的可能性为13-i种,然后,摸牌再看是什么点数就相当于公布答案,而这个答案刚好也是有 13-i 种,即,13-i种答案把13-i种可能性平均分为了13-i/13-i = 1种,最后得到鸡排需要的时间复杂度为O(1)

  28. simple | | Reply

    以6个球的例子来说,这个策略的“答案”是随着剩下的可能性(或者说剩下的球)的数量而发生变化的,比如,当球剩下2个时,那么天平的输出结果只可能有两种:左或右倾。因此,这时候应该是以以2去平分剩下的可能性。

  29. 滔要考研 | | Reply

    关于快排的部分,其实本质是指轴元素如果选取的不够“中间”,会导致第一次排序后左右不均,从而导致较差的效率表现。刘大牛从缩减可能性这个角度出发,让人耳目一新。受教了。

  30. 透明的沙子 | | Reply

    看起来很多人不理解这个,反复想不明白,坐等解答啊

  31. 透明的沙子 | | Reply

    “然而,快排的第二次比较就不那么高明了:我们不妨令轴元素为pivot,第一次比较结果是a1pivot的话,那么a1,a2,pivot这三个元素之间的关系就完全确定了——a1

  32. LittleJ | | Reply

    “第一次比较结果是a1<pivot,那么可以证明第二次比较a2也小于pivot的可能性是2/3!"这里我也不是很明白。这里指的第一次第二次都是相对于快排的一次排序来说的吧?那么第一次将a1和pivot比较,大或者小的概率是相等的这里没有问题。为什么第二次比较a2要“也”小于pivot呢?我的意思就是第一次比较和第二次比较之间有什么关联?这里我没有看明白,能不能解释一下呢?谢谢:)

  33. yeasy | | Reply

    更为本质一些,我觉得跟最大熵原理有些关系。
    参考http://yeasy.blogspot.com/2011/11/blog-post.html

  34. wosunziwuwan | | Reply

    “那么可以证明第二次比较a2也小于pivot的可能性是2/3″这句话有问题吧,可能性应该还是1/2吧?因为只是a2和pivot相对次序的比较,和a1无关,是一次独立的比较。这和取排问题不同,确定了2张牌后,第3张牌只有从剩下的牌中去取

  35. Miller | | Reply

    4、4称了之后不管哪种情况(分支),剩下来的可能性总是》 8 《种吧

  36. hit_alex | | Reply

    把这西抽象出来确实也挺有意思的。另外,我注意到标题:鸡排为什么又那么快呢?中“鸡排”是不是写错了?莫非是作者故意为之?

  37. kmplayer | | Reply

    “那么可以证明第二次比较a2也小于pivot的可能性是2/3!”
    ”a3<pivot的概率将会是3/4!“
    这两个地方的”叹号“很容易误解为”阶层“

  38. rrison | | Reply

    离散数学里的博弈树

  39. bigining | | Reply

    在说到12个的例子时,第二次称时:“这是一个完美的三分。然后对每个分支构造第二次称法,这里你只要稍加演算就可以发现,分支1上的第二次称法,即“1、2、6对3、4、5”这种称法,天平输出三种结果的可能性是均等的(严格来说是几乎均等)。”,但是这样好像是找不出那个不同的球的。不知道1、2、6对3、4、5之后要怎么进行判断?(可以假设1、2、6比3、4、5重,然后只能说明1、 2较重或5较轻,然后第三次要怎么进行?)

    • Ted | |

      晕,你都说了“然后只能说明1、 2较重或5较轻”,这还不明显,再把1,2分别放2边,哪个重,哪个就是,否则就是平衡,那5就是目标。

    • haha | |

      这里的称法存在问题,“1、2、6对3、4、5”这种称法,如果不平衡的话无法判断出来小球是轻还是重,所以是无法走到下一步小球存在于1 2 5中的,因为1 2 5 只是假定小球重的情况下;如果小球是轻的话,小球应该存在于 3 4 6中
      https://zh.wikipedia.org/wiki/%E7%A8%B1%E7%90%83%E5%95%8F%E9%A1%8C
      维基里面的称法是正确的 第二次称量1 5 9对2 3 6,这里面引入一个平衡球9,若1 5 9重的话,则得知1 6中存在坏球,比较1 4;若1 5 9对2 3 6平衡,则知4 7 8中存在坏球,比较4 8和1 2;若2 3 6重的话,则知2 3 5中存在坏球,比较4 8 和 2 5

  40. raymond | | Reply

    这是最大熵原则的几个例子,即保留最大的不确定性,因为这样才能保留最大的信息。生活中很多问题都可以归结为一些简单的法则,而在实际处理问题的时候,这些简单的法则会被以各种各样的形式掩盖,从而让我们失去探索的机会。博主是个有心人啊

  41. conan | | Reply

    关注toplanguage很久了.只是一直不敢在上面留言,看上面的聊天就感觉自己是沧海一粟.今天看到一篇.可能你是幸运的吧.我大概算了下,你应该是和我同届的.不过我比你小一岁.马上就毕业两年了.研究生们也快毕业了….回忆这些日子,感觉偏离了自己的目标,也感觉工作后并没有自己希望的成长着.一直觉得学校的东西很迂腐,什么都需要自己去学习.曾经也深深相信自己能好好成长起来.只是,到了今天,不知道自己是否还跟着大家的脚步….

  42. 帅得不敢出门 | | Reply

    受益良多
    每每看到一些精妙的解法(算法),都想拍手称快.

  43. chaonin | | Reply

    @@之前就在你的卢浮宫看到了,写的直白明了!

    小弟学的是编码,呵呵。
    Mackay的那本书重点是介绍编码的,具体的说是纠错码的。编码理论的重要基础是信息论。
    他对这些问题的分析不是专门要来分析这写问题的,而只是用信息论的方法来解释这些现象。

Leave a Reply to simple Cancel reply

Your email address will not be published. Required fields are marked *