1700494974
算法之美：指导工作与生活的算法 [:1700494125]
1700494975
算法之美：指导工作与生活的算法 大O符号：衡量最坏情况的标准
1700494976
1700494977
根据《吉尼斯世界纪录大全》，为一副扑克牌整理次序的最快记录是捷克魔术师兹德涅克·布拉德克保持的。2008年5月15日，布拉德克仅用时36.16秒就把52张扑克牌排好了先后次序。[1]他是怎么做到的？是什么排序技术让他获得这项殊荣的？答案可能与一些有趣的排序理论有关，但是布拉德克拒绝置评。
1700494978
1700494979
对于布拉德克的灵巧与技能，我们只能表示尊敬，但是我们百分之百地确定我们自己也可以打破他的纪录。事实上，我们非常确定，只要向这项殊荣发起80658175170943878571660636856403766975289505440883277824000000000000次挑战，就一定可以创造一个无法打破的纪录。这个数字比10的66次方的80倍略大一点儿，是52的阶乘，数学上记作“52！”——包含52张牌的一副扑克牌可以排出这么多不同的次序。在经过大约这么多次的尝试之后，我们迟早可以为经过洗牌变得杂乱无序的扑克牌快速排序，然后，我们可以自豪地让克里斯汀·格里菲斯这个名字载入《吉尼斯世界纪录大全》，然后在旁边标明一个不太难看的排序时间——0分00秒。
1700494980
1700494981
公正地说，在宇宙进入热寂状态之前，我们可能都需要不停地尝试，才有可能创造出这个完美的纪录。尽管如此，我们从中可以清楚地看到纪录保持者和计算机科学家之间最大、最根本的区别。吉尼斯纪录的工作人员只关心最好的成绩（和娱乐性）。当然，他们的行为也无可厚非，因为所有的体育纪录也都只能反映出最佳表现。然而，计算机科学几乎从不关心最好的情况。相反，计算机科学家可能想知道像布拉德克等人的平均排序时间：让他对所有8×1066副扑克牌或者合理大小的样本进行排序，然后记录平均速度。（这下你知道他们为什么不会让计算机科学家来做这些事情了吧？）
1700494982
1700494983
不仅如此，计算机科学家还希望知道最慢的排序速度。分析最糟糕的情况，可以让我们放心地做出硬性保证——确保关键程序可以及时完成，确保不会超出最后期限。因此，在本章剩余部分（事实上，是全书的剩余部分）里，除非另有说明，否则我们讨论的都是算法的最差表现。
1700494984
1700494985
计算机科学有一种专门用来测量算法最坏情况的速记法，即所谓的“大O”符号。大O符号有一个非常奇怪的特点——设计这个符号的目的就是用来表示不精确性。也就是说，大O符号的目的不是使用分钟和秒钟来表示算法的性能，而是方便我们讨论问题规模和程序运行时间之间的关系。由于大O符号故意剔除了细枝末节的内容，所以展示在我们眼前的是将问题分成不同大类的概略情况。
1700494986
1700494987
假设你准备邀请n名客人出席晚宴。在客人到来之前，打扫房间的时间与来客人数没有任何关系。这类问题最简单，被称为“O（1）”，也被称为“常数时间”。值得注意的是，大O符号根本不关心清理工作需要多长时间，只是要求它保持不变，与宾客名单没有任何关系。无论来几个客人，1个，10个，100个，或者n个，你都需要完成同样多的工作。
1700494988
1700494989
接下来，烤肉在所有客人面前传递一圈所需的时间将是“O（n）”，也被称为“线性时间”——客人增加一倍，菜传递一圈所需的时间就会增加一倍。同样，大O符号根本不关心一共有多少道菜，也不关心这些菜是否会上第二遍。在这两种情况下，时间仍然取决于宾客数量，如果你画出客人数量和时间的关系图，就会得到一条直线。更重要的是，在大O符号中，任何线性时间因子的存在，都会掩盖掉所有常数时间因子。也就是说，将烤肉传递一圈，或者花三个月时间把餐厅重新装修一遍，再把烤肉在所有客人面前传递一遍，对计算机科学家来说，两者都是等效的。不要认为这个说法不可思议，记住计算机处理的是n的值，这个数值变成几千、几十万，甚至几十亿，也不是难事。换句话说，计算机科学家正在考虑举行一个规模非常大的聚会。在数百万的来宾当中传递一次烤肉，所需时间之多，真的足以让房屋重新装修所需的时间变得无足轻重。
1700494990
1700494991
假设客人到来之后，你要与每个人热烈拥抱，情况又会怎么样？第一个到达你家的客人与你拥抱，第二个客人需要拥抱两次，第三个客人要拥抱三次。此时，拥抱一共发生了多少次？这种情况属于“O（n2）”，也称“平方时间”。此时，我们同样只关心n与时间的关系概貌。每个人拥抱两次不会是O（2n2），拥抱加传递食物不会是O（n2+n），拥抱加打扫房间也不是O（n2+1）。所有的时间都是平方时间，所以O（n2）将掩盖掉其他所有因素。
1700494992
1700494993
1700494994
1700494995
1700494996
注：常数时间，记作O（1）；线性时间，记作O（n）；平方时间，记作O（n2）
1700494997
1700494998
从现在开始，情况就会变得越来越糟糕了。如果每增加一名客人都会让你的工作加倍，那么就会有“指数时间”，记作“O（2n）”。更糟糕的是，甚至还有“阶乘时间”，记作“O（n！）”。阶乘时间异常复杂，计算机科学家只有在开玩笑时（例如，我们设想通过洗牌这个方式为一副扑克牌排序），或者真的希望自己是在开玩笑时，才会讨论这类问题。
1700494999
1700495000
[1]除此以外，布拉德克还保持多项纪录。例如，他可以在水下打开三副手铐逃生，所耗时间与给扑克牌排序的时间差不多。
1700495001
1700495002
1700495003
1700495004
1700495005
算法之美：指导工作与生活的算法 [:1700494126]
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