1700494958
算法之美：指导工作与生活的算法 [:1700494124]
1700494959
算法之美：指导工作与生活的算法 排序带来的苦恼
1700494960
1700494961
1955年，詹姆斯·霍斯肯在第一篇公开发表的关于排序的科学论文中写道：“为了降低单位产出的成本，人们通常会增加他们的业务规模。”这是任何一名商科学生都很熟悉的规模经济。但是，在排序这个问题中，规模往往会招致灾难：如果扩大排序的规模，“排序的单位成本就会不降反升”。排序往往呈现非常明显的规模不经济现象，这与普通人认为大批量处理问题有诸多好处的直觉正好相反。一般来说，做两个人的饭并不比做一个人的饭难，肯定比为一个人做两次饭要容易得多。但是，整理好装有100本书的书架，比整理两个各有50本书的书架更费时：因为你需要整理的东西是后者的两倍，而且每件东西可以放置的位置也是后者的两倍。需要整理的东西越多，难度就越大。
1700494962
1700494963
这是排序理论的第一个，也是最基本的深刻见解：规模越大，难度越大。
1700494964
1700494965
由此我们可以推断，在排序的过程中，最大限度地减少痛苦的办法就是在排序时尽可能减少排序对象的数量。的确，降低袜子排序计算难度的一个最有效的预防措施就是勤洗衣服。如果洗衣服的频率增加到原来的3倍，排序时的难度就会变为原先的1/9。如果希利斯的室友继续采用他的那套独特程序，那么把洗衣服的间隔时间从14天改为13天，为袜子配对时从洗衣篮中拿袜子的总次数就可以减少28次。（间隔时间增加1天，拿袜子的次数就会增加30次。）
1700494966
1700494967
即使在14天这样一个不大不小的时间范围内，我们也可以看到排序的规模已经开始变得难以处理。然而，计算机通常需要一口气为数百万个项目排序。面对这种情况，我们可以借用电影《大白鲨》的一句台词：我们需要一艘更大的船以及更好的算法。
1700494968
1700494969
但是，要回答如何排序、哪种排序方法效果最佳这个问题，就需要先弄明白另外一个问题：如何计分。
1700494970
1700494971
1700494972
1700494973
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