1700495138
1700495139
世界杯、奥运会、美国全国大学体育协会（NCAA）、美国全国橄榄球联盟（NFL）、美国全国曲棍球联合会（NHL）、美国职业篮球联赛（NBA）和美国职业棒球大联盟（MLB），所有这些赛事都毫无疑问地使用了排序程序，利用赛季、排位赛和季后赛等算法排出先后关系。
1700495140
1700495141
体育运动中的循环赛制就利用了算法。如果一共有n支运动队，那么每支运动队最终都要和其余n-1支队伍比赛。这种赛制虽然可以说是最全面的，但也最费时费力。让每一支运动队都与其他所有队伍比赛，就像在晚宴上让客人两两拥抱一样，最终会需要可怕的O（n2）次角逐。
1700495142
1700495143
排位赛（在羽毛球、英式壁球和美式壁球等体育项目中比较常见）对运动员进行线性排序，每个球员都可以直接向排在前面一位的球员发起挑战，如果获胜，则交换排位。排位赛就相当于运动场上的冒泡排序，因此也是平方排序，需要O（n2）场比赛才能得到稳定的排名。
1700495144
1700495145
不过，最流行的赛制可能还是分组淘汰——著名的“疯狂三月”NCAA篮球赛就是其中一例。“疯狂三月”锦标赛的赛程包含“64强赛”“32强赛”到“甜蜜16强”“8强赛”“最后4强”和总决赛。每一轮都会导致比赛人数减半。与我们熟悉的对数排序很像吧？这种赛制其实就是合并排序，先让球队无序配对，然后进行一轮又一轮的比较。
1700495146
1700495147
我们知道合并排序需要线性对数时间［即O（nlogn）］，因此，如果一共有64支队伍，可以预计比赛只需要进行6轮（一共192场），而采用排位赛或者循环赛，则需要多达63轮（2016场）比赛。这是一个巨大的改进，说明对数设计发挥了效用。
1700495148
1700495149
“疯狂三月”有6轮比赛，似乎没有问题，但是怎么是192场比赛呢？美国大学体育协会锦标赛不是只有63场比赛吗？
1700495150
1700495151
“疯狂三月”其实不完全是一种合并排序法，因为它并没有产生所有64支队伍的完整排序。要对所有球队进行排名，我们需要增加一组比赛才能确定第二名，确定第三名时又需要增加一组比赛，以此类推，比赛的总场次就会是一个线性对数函数。但是“疯狂三月”没有采取这种赛制。相反，就像道奇森抱怨的草地网球锦标赛一样，它采用的是一种单一淘汰制，被淘汰的球队是不排序的。这种赛制的优势在于它的线性时间。由于每场比赛正好淘汰一支队伍，因此，要让一支队伍留到最后，一共需要n-1场比赛。这是一个线性数字。不足之处是，这种赛制只能决出第一名，无法给出名次表。
1700495152
1700495153
具有讽刺意味的是，单淘汰赛制其实根本不需要任何赛制结构。只要在63场比赛中保持不败，就是唯一的冠军。举个例子，你可以选择一支球队担任“擂主”，然后接受其他队伍的挑战。一旦某支队伍挑战成功，击败擂主，就立刻成为新的擂主，然后继续接受挑战。然而，这种赛制有一个缺点：因为所有比赛无法同时进行，63场比赛需要安排成63轮。此外，有一支队伍有可能需要连续参加63场比赛，从疲劳这个角度看，这种赛制不是最理想的。
1700495154
1700495155
迈克尔·特里克的出生时间比道奇森晚100多年。在用数学知识解决体育问题这个方面，他或许算得上是21世纪最坚定的人。我们在前面讨论最优停止问题时已经说过特里克。从他非常不幸地把37%法则应用到他的爱情生活中到现在，已经过去几十年了，他现在不仅已经结婚，并成为美国职业棒球大联盟和多个美国大学体育协会（例如十大联盟、大西洋海岸分区）的主要赛程编排人员，他利用计算机科学，确定当年的对阵安排。
1700495156
1700495157
特里克认为，体育联盟不关心如何快速地确定排名。相反，体育运动的赛程安排需要保证整个赛季都处于一种紧张状态，而排序理论几乎不会关注这个问题。
1700495158
1700495159
例如，在美国职业棒球大联盟，我们常常发现分区的竞争非常激烈。如果我们不重视分区的安排，有些分区的竞争结果可能会在赛季之初就比出来了。但是，我们要保证在最后五周内，每支球队都要与分区内其他球队会面。这样安排是出于一个目的：到底谁还在竞争队伍中并不重要，但是所有球队在赛季最后五周里，都至少要在6场比赛里遭遇势均力敌的对手。在这种情况下，比赛的不确定性将保持到最后，因此观众才会对整个赛程或者赛季感兴趣。
1700495160
1700495161
更重要的是，体育运动当然不可能一味地追求减少比赛场次。如果不注意到这一点，计算机科学家就有可能觉得某些体育赛程神秘莫测。关于包含2430场比赛的棒球常规赛季，特里克说：“我们知道只要比较nlogn次，就可以排出完整的名次表。每支球队的名次都会很清楚。如果他们关心的仅仅是名次，那么他们安排n2场比赛，而且从某种意义上讲，仅仅决出第一名，又是为什么呢？”换句话说，如果我们知道利用线性对数时间就可以完成完全排序，或者利用不到n场比赛就可以把在单淘汰赛中保持不败的球队送上冠军宝座，那么我们为什么要安排O（n2）场循环赛，然后再安排一些其他比赛呢？原因很简单，把比赛场次降到最少其实并不符合联盟的利益。在计算机科学中，不必要的比较总是多余的，浪费时间和精力。但在体育运动中，情况远非如此。毕竟，在很多方面，比赛本身就是意义所在。
1700495162
1700495163
[1]只有极少数情况下（例如，在拳击比赛中，从医学这个角度看，刚刚被击败的选手再次比赛是有危险的），两名运动员才会分享铜牌。
1700495164
1700495165
1700495166
1700495167
1700495169
算法之美：指导工作与生活的算法 发牢骚的权利：噪声与健壮性
1700495170
1700495171
将算法应用于体育的另外一个方法，也许是更加重要的方法，即不要问我们应该在银牌上有多大的信心，而是看我们应该对金牌有什么样的信心。
1700495172
1700495173
迈克尔·特里克解释说，在一些体育项目中，“例如棒球，无论哪支球队，都会输掉30%的比赛，都会赢得30%的比赛”。对于单淘汰赛制而言，这个事实就会产生令人不安的影响。比如说，美国大学体育协会锦标赛在70%的比赛中是更强大的球队获胜，并且冠军需要在6场比赛中连续获胜，那么最好的球队只有0.7的6次方（不到12%）的概率夺冠！换句话说，联盟中最优秀的球队每10年才会夺得一次冠军。
1700495174
1700495175
在一些体育项目中，哪怕对一场比赛的结果有70%的信心，也可能会让人们过于相信最后的比分。加州大学圣迭戈分校的物理学家汤姆·墨菲利用数值模拟技术来研究足球，结果发现足球的得分通常比较低，因此比赛结果的随机性远远超出了大多数球迷的想象。他说：“如果比分是3：2，那么获胜球队实力强于对手的概率只有5/8……就我个人而言，我觉得这并不是一个难以接受的事实。即使是6：1的完胜，也有7%可能是统计学上的一个巧合。”
1700495176
1700495177
计算机科学家把这种现象称作噪声。我们目前所考虑的所有排序算法都假设我们可以完美地完成比较这个步骤，而且比较结果准确无误，绝不会发生优劣颠倒的情况。一旦你接受“带噪比测器”，计算机科学中被人们敬若神明的算法就会走下神坛，而受到最多诟病的算法也有死灰复燃的机会。
1700495178
1700495179
新墨西哥大学计算机科学教授戴夫·阿克利研究的是计算机科学和“人工生命”的交叉领域。他相信生物学对计算机有一定的借鉴意义。首先，在生物生活的世界中，几乎所有过程的可靠性都比不上计算机不可或缺的那种可靠性，因此必须从头开始，培养研究人员所谓的健壮性。阿克利称，从现在开始，我们也应该认识到算法健壮性的好处。
1700495180
1700495181
因此，尽管权威的编程巨著《排序与搜索》大胆地宣称：“冒泡排序并没有明显的可取之处。”阿克利和合作伙伴的研究却表明，冒泡排序等算法或许可以卷土重来。冒泡排序的效率的确低下——每次只移动一个位置，但是它们对抗噪声的能力比较强，远胜于合并排序等速度更快的算法（在这种算法中，每一次比较都有可能将一个物品移动非常长的距离）。合并排序的效率非常高，因此健壮性不足。在合并排序早期发生错误，就会像在第一轮淘汰赛中意外失利一样，不仅会使有望夺冠的球队希望破灭，还会把球员们的排名永久性地降到半数球队之后。[1]另一方面，排位赛与冒泡排序相似，意外失利只会让运动员的排名下降一个位置。
1700495182
1700495183
但是，在带噪比测器面前表现最好的并不是冒泡算法，获得这项殊荣的是一种叫作比较计数排序的算法。在该算法中，每个排序对象都会与其他对象做比较，从而统计出比该排序对象小的对象一共有多少个。这个数字可以直接表示该排序对象的排名。因为比较计数排序让所有的排序对象都结对比较，因此与冒泡排序一样，它也是一个平方时间算法。正因为如此，它在传统的计算机科学应用程序中并不是一个深受欢迎的选择，但是它的容错能力非常强。
1700495184
1700495185
这个算法的作用原理听起来应该很熟悉。比较计数排序与循环赛十分相似。换句话说，就像一个运动队参加常规赛一样：与同一赛区中所有其他球队一一对垒，并通过胜败记录决出名次。
1700495186
1700495187
在所有已知的算法中，包括平方时间算法和其他更优秀的算法，比较计数排序是最健壮的排序算法。了解这个事实应该可以帮助体育迷们正确面对某些具体情况。如果球队没有进入季后赛，就不要怨天尤人了。采用合并排序的季后赛有运气的成分，但是采用比较计数排序的常规赛是无法碰运气的。冠军戒指也许不是那么可信，但是分区的排名货真价实。换句话说，如果一支球队在季后赛早早出局，那是运气太差。但是如果一支球队不能进入季后赛，那这就是一个严酷的事实了。失望的球队球迷可能会在运动酒吧里向他们表示同情，但是计算机科学家不会心生任何怜悯。
[
上一页 ]
[ :1.700495138e+09 ]
[
下一页 ]