1700495003
1700495004
1700495006
算法之美：指导工作与生活的算法 平方时间：冒泡排序与插入排序
1700495007
1700495008
2007年，时任参议员的奥巴马访问谷歌公司时，谷歌的首席执行官埃里克·施密特开了一个玩笑，以求职面试官的口气问了奥巴马一个问题：“为100万个32位整数排序，最好采用什么方法？”奥巴马诙谐一笑，回答道：“我认为用冒泡排序肯定是不对的。”谷歌的工程师们爆发出一阵欢呼。一位工程师后来回忆道：“他竟然知道冒泡排序，我一下子就被打动了。”
1700495009
1700495010
奥巴马排除冒泡排序的回答是正确的。这个简单的直觉式算法效率低下，已经成为计算机科学专业的学生攻击的目标。
1700495011
1700495012
假设你希望将杂乱无序的藏书按照字母顺序进行分类排序。那么你会很自然地想到一个方法，于是你在书架前巡视，看到有两本书颠倒了先后次序，就把它们调换过来（例如，将品钦的小说放在华莱士后面）。在将品钦放到华莱士前面之后，你继续巡视。走到书架最后端之后，你就会回过头来，从书架最前端重新开始。如果从头走到尾，都没有看到有哪两本书次序不对，就说明你完成了这项工作。
1700495013
1700495014
这就是冒泡排序，它会把我们带进平方时间。有n本书放在不正确的位置，每次巡视书架最多可以为一本书调换位置。（也就是说，我们发现了一个小问题，然后完成了一个小的修正。）所以，在最坏的情况下，即书架上的书正好是倒序放置的，那么至少有一本书需要移动n个位置。因此，在最坏的情况下，n本书都需要移动最多的n个位置，就会得出O（n2）这个结果。[1]不过，这并不是一个最令人害怕的结果，比如，前面说过，要用洗牌的方法把一副牌理顺，就会得到O（n！）这个可怕的结果。与之相比，O（n2）并不可怕（无须运用计算机科学加以证明，我们也知道是这么回事）。但是，这个平方项很快就会让我们望而生畏。举个例子，这意味着整理5个书架所需要的时间不是整理单个书架的5倍，而是25倍。
1700495015
1700495016
你可能会采取另外一种方法，即把所有的书都从书架上拿下来，然后一本一本放到合适的位置。你把第一本书放在书架中间，然后拿第二本书和第一本比较，根据比较结果把它插到第一本的右边或者左边。在放第三本书时，你先从左到右浏览书架，然后把它放到合适的位置。你不断重复这个过程，渐渐地所有的书都被按次序放到书架上，直到你最终完成这项工作。
1700495017
1700495018
计算机科学家们给这种方法起了一个非常贴切的名称——“插入排序”。好消息是，它比冒泡排序更直观，而且名声也不是太差。坏消息是它实际上并不比冒泡排序快多少。每本书仍然需要一次插入，而且平均每次插入都需要你移动大约半个书架的距离，才能找到合适的插入位置。虽然在实践中插入排序比冒泡排序要快一些，但我们还是会被带进平方时间。为不止一个书架排序仍然是一项难以处理的任务。
1700495019
1700495020
[1]其实，冒泡排序的平均运行时间并不好于这个结果。平均而言，书本与它们最终应该在的位置之间相差n/2个位置。计算机科学家会告诉我们，将n本书分别传递n/2个位置，约需要O（n2）次。
1700495021
1700495022
1700495023
1700495024
1700495026
算法之美：指导工作与生活的算法 打破平方时间的魔咒：分治算法
1700495027
1700495028
看到两个完全合理的方法都会导致平方时间之后，我们不禁要问：真的有更快的排序方法吗？
1700495029
1700495030
这个问题听起来像是一个关于生产力的问题。但是，与计算机科学家讨论这个问题，就会发现它更接近于空谈，类似于思考光速，时光之旅，超导体，或者热力学中的熵。宇宙的基本规则和极限是什么？哪些是可能的？哪些是允许的？计算机科学家就像粒子物理学家和宇宙学家一样，通过这种方式一点一滴地窥探上帝的蓝图。整理出秩序，至少需要付出多少努力？
1700495031
1700495032
我们能否找到一种常数时间，也就是O（1）算法，无论规模大小，耗费的时间都不会有任何变化（就像在客人蜂拥而至之前打扫房间一样）？即使证实书架上的n本书已经排好序，也不可能在常数时间里完成，因为我们需要检查所有书的位置。因此，用常数时间完成图书分类排序工作其实是根本不可能的。
1700495033
1700495034
线性时间O（n）呢？可不可以像在餐桌上传递一道菜那样高效，排序对象增加一倍，工作量也仅仅增加一倍？想一想上面的那些例子，就会发现很难有这样的方法。在各种情况下，n2都与你需要移动n本书这个事实有关，而且每次将书移动位置所需的工作量与n也成某种比例关系。怎么可以把大小为n、次数也为n的工作变得只剩下一个n？在冒泡排序中，运行时间O（n2）是因为我们需要逐本移动n本书的位置，而且每次移动时需要跨越n个位置。在插入排序中，之所以是平方时间，是因为我们需要逐本处理n本书，而且在插入之前还要将每本书与n本书进行比较。线性时间排序意味着每本书都需要常数时间，无须考虑有多少本书需要排位的问题。这好像也是不可能做到的。
1700495035
1700495036
因此，我们知道我们至少可以在平方时间里完成任务，但是可能无法在线性时间里把所有书都排好序。我们的极限或许就在线性时间与平方时间之间的某个位置。在线性与平方之间，即n与n×n之间，是否可以找到合适的算法呢？
1700495037
1700495038
答案是肯定的，而且这些算法近在眼前。
1700495039
1700495040
前面说过，信息处理开始于19世纪的美国人口普查，是由赫尔曼·霍尔瑞斯及后来的IBM公司根据实体打孔卡排序设备开创形成的。1936年，IBM开始生产一系列名为“比较者”的机器，它可以将分别排序的两叠扑克牌合并到一起。只要两叠牌本身是排好序的，就可以在线性时间内，非常轻松地将它们合并到一起，并且排好序。该程序非常简单，首先把两叠牌最上面的那两张相互比较，将较小的那张放在新的那叠牌中。重复这个步骤，直到把所有牌都放好。
1700495041
1700495042
1945年，约翰·冯·诺伊曼为了展示存储程序计算机的威力，编写了一个程序。在这个程序的最终结论中，就包含有比较的概念。为两张牌排序很简单，把较小的那张牌放在上面就可以了。如果有两叠牌，每叠包含两张排好序的牌，我们可以很容易地将这四张牌整理成排好序的一叠牌。重复几次，就可以整理出越来越多且排好序的牌垛。很快，你就可以把完整的一副牌整理得井然有序。在最后一次合并时，你可以通过与交错式洗牌非常相似的手法，将扑克牌整理出你需要的次序。
1700495043
1700495044
这种方法现在被称作“合并排序”，是计算机科学中的传奇算法之一。正如1997年的一篇论文所指出的：“合并排序在排序历史中的重要地位与排序在计算历史中的重要地位旗鼓相当。”
1700495045
1700495046
合并排序威力巨大，是因为它的复杂程度位于线性时间和平方时间之间。具体来说，O（nlogn）被称为“线性对数”时间。每一次操作都会把有序牌叠的规模增加一倍，所以要对n张牌完全排序，你需要的操作次数就等于2通过自乘变成n时所需的次数，换句话说，就是以2为底的对数。你可以通过两次比较操作，为4张牌排序；第三次操作之后，排好序的牌就会有8张；第四次操作，16张。合并排序的分治法问世之后，人们很快受到启发，提出了一系列其他线性对数排序算法。把线性对数复杂程度说成对平方复杂程度的一个改进，远不足以体现出两者之间的差距。如果需要排序的项目数量与人口普查差不多，那么两者的差距就相当于对数据集进行29次操作和3亿次操作之间的差别。各行业在解决大规模排序问题时都青睐这种方法，原因就不难理解了。
1700495047
1700495048
在家庭内部处理小规模排序问题时，合并排序也能找到合适的舞台。它之所以应用广泛，原因之一是它非常适合并行处理。如果你还在苦苦思索对付那个书架的办法，合并排序策略就会建议你订一个比萨，然后邀请几个朋友来分享。把书平均分配，并让每个人负责整理其中一堆。接着，让朋友们两两配对，把他们负责的书合并到一起。重复这个过程，直到最后剩下两堆书，再一次性地合并到书架上。需要注意的是，不要让比萨弄脏了那些书。
1700495049
1700495050
1700495051
1700495052
[
上一页 ]
[ :1.700495003e+09 ]
[
下一页 ]