算法初探（下）
(function(){
var cover = "http://mmbiz.qpic.cn/mmbiz/dcEP2tDMibcc87WAsFvPa858L8tQjSNR2dyxibWNtciaaw6bt2hgnmOYsTicD2rb3zqzDNTicaksSAD8XjzmBAZwqwQ/0?wx_fmt=jpeg";
var tempImg = document.createElement('img');
tempImg.setAttribute('class', 'rich_media_thumb');
tempImg.setAttribute('id', 'js_cover');
tempImg.setAttribute('data-backsrc', cover);
tempImg.setAttribute('src', cover);
tempImg.setAttribute('onerror', 'this.parentNode.removeChild(this)');
document.getElementById('media').appendChild(tempImg);
})();
本文选自《世界是数字的》，介绍了计算机算法的本质
接着讲述了二分查找的上篇，这一篇介绍排序算法的复杂复杂度
4.3 排序
不过，得先把这些名字按照字母顺序排列起来呀，怎么做到呢？如果没有这个先行步骤，就不能使用二分搜索。这就引出了另一种基本算法——排序，把数据按顺序排好，后续搜索才能更快。
假设我们要把一些名字按照字母顺序排好，以便后面更有效地使用二分搜索。那么可以使用一个叫选择排序的算法，因为它会不断从未经排序的名字中选择下一个名字。
这个算法的技巧，就是前面讨论的找出房间里最高的那个人所用的技巧。
好，让我们就把下面这 16 个熟悉的名字按字母顺序排列一下：
Intel Facebook Zillow Yahoo Picasa Twitter Verizon Bing
Apple Google Microsoft Sony PayPal Skype IBM Ebay
首先是 Intel，它是到目前为止按字母排序后的第一个名字。 Facebook 在字母表中更靠前，所以它暂时又成为第一个。 Zillow 不靠前，而且直到 Bing 才取代 Facebook，但Bing 随后又被 Apple 取代。我们接着比对其余名字，没发现一个位于 Apple 之前的，因此 Apple 是这个序列中真正的第一个，当前的结果如下：
Apple
Intel Facebook Zillow Yahoo Picasa Twitter Verizon Bing
Google Microsoft Sony PayPal Skype IBM Ebay
现在，重复上述过程，找到第二个名字，从 Intel 开始——Intel 是未排序名字中的第一个名字。同样， Facebook 取而代之，然后是 Bing 成为第一个元素。第二遍之后的结果如下：
Apple Bing
Intel Facebook Zillow Yahoo Picasa Twitter Verizon
Google Microsoft Sony PayPal Skype IBM Ebay
最终，通过这个算法得到了完全排好的名字列表。
选择排序的工作量有多大？它每次都会遍历剩余的数据项，每次都会找到字母顺序中的下一个名字。对于 16 个名字的排序，查找第一个名字要检查 16 个名字，查找第二个名字需要 15 步，查找第三个名字需要 14 步，依此类推，加起来总共要检查16+15+14+…+3+2+1 个名字。当然，我们也可能很幸运，发现这些名字已经都按字母排好序了。但研究算法的计算机科学家可都是悲观主义者，他们假设的是最坏的情况
（即这些名字都是按照字母顺序的反序排列的）。
检查名字的遍数与最初的数据项数成正比（我们例子中的数据项有 16 个，可以用一般化的 N 表示）。而每一遍要处理的项数都比前一遍少一项，所以选择排序算法一般
化的工作量是：
N N N N+ - + - + - + + +( 1) ( 2) ( 3) 2 1L
这个序列加起来等于 N ×（ N + 1） /2（最简单的办法是把两头的项成对地加起来），也就是 N 2/ 2 + N / 2。忽略除数 2，可见选择排序的工作量与 N 2 + N成正比。随着 N不断增大， N2最终会大得让 N也可以忽略不计（例如， 如果 N是 1000，则 N2就是 1 000 000）。
因此，结果就是工作量近似地与 N 2即 N的平方成正比，而这个增长率叫做二次增长。二次增长不如线性增长，事实上，差得很远。要排序的数据项增加到原来的 2 倍，时间会增加到原来的 4 倍；数据项增加到 10 倍，时间会增加到 100 倍；数据项增加到 1000倍，时间会增加到 1 000 000 倍！这可不太好。
幸运的是，有办法让排序更快一些。我们简单地介绍一种巧妙的方法——快速排序（ Quicksort），这个算法是英国计算机科学家托尼·霍尔在 1962 年前后发明的（霍尔获得了 1980 年的图灵奖，获奖理由是包括快速排序在内的多项贡献）。快速排序也是分而治之的一个绝佳示例。
同样，下面还是那些未经排序的名字：
Intel Facebook Zillow Yahoo Picasa Twitter Verizon Bing
Apple Google Microsoft Sony PayPal Skype IBM Ebay
要使用快速排序算法给这些名字排序，首先要遍历一次所有名字，把介于 A 到 M 之间的名字放到一组里，把介于 N 到 Z 之间的名字放到另一组里。这样就把所有名字分成了两个组，每个组里包含一半名字（假设这些名字的分布不会很不均匀）。在我们的例子中，这两个组分别包含 8 个名字：
Intel Facebook Bing Apple Google Microsoft IBM Ebay
Zillow Yahoo Picasa Twitter Verizon Sony PayPal Skype
现在，遍历 A-M 组，把 A 到 F 分成一组， G 到 M 分成另一组；遍历 N-Z 组，把 N-S分成一组， T-Z 分成一组。到现在为止，遍历了所有名字两次，分成了四个组，每个组包含四分之一的名字：
Facebook Bing Apple Ebay
Intel Google Microsoft IBM
Picasa Sony PayPal Skype
Zillow Yahoo Twitter Verizon
接下来再遍历每个组，把 A-F 分为 ABC 和 DEF，把 G-M 分成 GHIJ 和 KLM；同样，对 N-S 和 T-Z 也如法炮制。这样，就有了 8 个组，每组差不多有 2 个名字：
Bing Apple
Facebook Ebay
Intel Google IBM
Microsoft
Picasa PayPal
Sony Skype
Twitter Verizon
Zillow Yahoo
当然，到最后我们不仅仅要看名字的第一个字母，比如要把 IBM 排到 Intel 前面，把Skype 排到 Sony 前面，就得继续比较第二个字母。但就这样多排一两遍，即可以得到16 个组，每组 1 个名字，而且所有名字都按字母顺序排好了。
整个过程的工作量有多大？每一遍排序都要检查 16 个名字。假设每次分割都很完美，则每一遍分成的组分别会包含 8、 4、 2、 1 个名字。而遍数就是 16 反复除以 2 直到等于 1 为止除过的次数。结果就是以 2 为底 16 的对数，也就是 4。因此，排序 16 个名字的工作量就是 16 log216。在遍历 4 遍数据的情况下，快速排序总共需要 64 次操作，而选择排序则需要 136 次。
该算法可以对任何数据进行排序，但只有在每次都能把数据项分割成大小相等的组时，它才是最有效的。对于真实的数据，快速排序必须猜测数据的中位值，以便每次都能分割出相同大小的组。好在，只要对少量数据项进行采样，就可以估计出这个值。
一般来说（忽略某些细节上的差别），快速排序在对 N个数据项排序时，要执行 N logN 次操作，即工作量与 N log N 成正比。这与线性增长比要差一些，但还不算太坏，在 N特别大的情况下，它比二次增长即 N 2增长可以好太多了。
为此我做了个实验，随机生成了 1000 万个 9 位数，用于模拟美国的社会保障号，记录了不同规模的分组排序下所花的时间，测试了选择排序（ N 2即二次增长）和快速排序（ N log N）。下表中的短划线表示没有做该项测试。
精确测量运行时间很短的程序并不容易，因此这些测试数据的误差可能比较大。但无论如何，还是可以（粗略地）看到快速排序意料之中的 N log N 式的时间增长，同时也能看到尽管选择排序的效率难以与之匹敌， 但在 10 000 个数据项以内时还是可以接受的；而且，在每个数量级上，选择排序都被快速排序毫无悬念地抛在了后头。
另外也要注意，在对 100 000 个数值进行排序时，选择排序的时间是对 10 000 的数值进行排序时的近 200 倍，而不是我们期望的 100 倍。几乎可以肯定，这是缓存效应——由于这些数据并没有全部保存在缓存中，所以排序变慢了。
4.4 难题与复杂性
刚才，我们对算法的“复杂性”或运行时间进行了简单的剖析。一个极端是 log N，即二分搜索的复杂性，它表示随着数据量的增加，工作量的增长非常缓慢。最常见的情况是线性增长，或者说简单的 N，此时工作量与数据量是成正比的。然后是快速排序的 N log N，比 N差（增长快），但在 N非常大的情况下仍然特别实用。还有就是 N 2，或者二次增长，增长速度太快了，既让人无法忍受又不切实际。
除了这些之外，还有其他很多种复杂性，有的容易理解（例如三次增长，即 N3，比二次增长还差，但道理相同），有的则很难懂，只有少数专业人士才会研究。但有一个还是非常值得了解一下，因为它在现实当中很常见，而且从复杂性上说特别糟糕，这就是所谓的指数级增长，用数学方法表示是 2N（与 N2可不一样）。指数级算法的工作量增长极快：增加一个数据项，工作量就会翻一番。从某种意义上讲，指数级算法与log N 算法是两个极端，后者数据项翻一番，工作量才增加一步。
什么情况下会用到指数级算法呢？那就是除了一个一个地尝试所有可能性，没有更好的办法的情况。谢天谢地，指数级算法总算是有点用武之地的。有些算法，特别是密码学中的算法，都是让特定计算任务具有指数级难度的。对于这样的算法，只要选择了足够大的 N，其他人在不知道某个秘密捷径的情况下，是不可能通过计算直接解决问题的。
现在你只要知道有些问题容易解决，而有些问题则要难得多就可以了。实际上，关于解决问题的难易程度，也可以表达得更加精确一些。所谓“容易”的问题，都具有“多项式”级复杂性。换句话说，解决这些问题的时间可以用 N 2 这样的多项式来表示，其中指数可以大于 2， 但都是可能被解决的。（忘了什么是多项式啦？不要紧，多项式在这里就是指一个变量的整数次幂，比如 N 2 或 N 3。） 计算机科学家称这类问题为“P”（即“Polynomial”，多项式），因为它们可在多项式时间内解决。
现实中大量的问题或者说很多实际的问题似乎都需要指数级算法来解决，也就是说，我们还不知道对这类问题有没有多项式算法。这类问题被称为“NP”问题。 NP 问题的特点是，它可以快速验证某个解决方案是否正确，但要想迅速找到一个解决方案却很难。 NP 的意思是“非确定性多项式”（ nondeterministic polynomial），这个术语大概的意思是：这些问题可以用一个算法在多项式时间内靠猜测来解决，而且该算法必须每次都能猜中。在现实生活中，没有什么能幸运到始终都做出正确的选择，所以这只是理论上的一种设想而已。
很多 NP 问题都会牵扯大量技术细节，三言两语也解释不清楚。不过倒是有一个问题很好解释，乍一看还挺有意思的，而且其实际应用也比较广。
这就是“旅行推销员问题”（ Traveling Salesman Problem）。一个推销员必须从他居住的城市出发，到其他几个城市去推销，然后再回家。目标是每个城市只到一次（不能重复），而且走过的总距离最短。这个问题跟最短校车或者垃圾车路线有异曲同工之妙。很早以前我在研究这个问题的时候，其原理经常被应用于设计电路板上孔洞的位置，或者部署船只到墨西哥湾的特定地点采集水样。
旅行推销员问题已经被仔细推敲了 50 多年，尽管能用它来解决的问题更加多样化了，但解决方案的核心依然是从所有路径中更巧妙地找出最短路径。同样，有许多的其他问题，尽管类型不同，形式各异，也都面临同样的命运：我们没有什么好办法有效地解决它们。
对于研究算法的人来说，这个现实令人沮丧。我们不知道到底是这些问题本质上就很难解决呢，还是因为人类不够聪明，所以至今都没有找到更好的解决办法。当然，不管怎么说，人们更愿意相信它们“本质上就很难解决”。
1970 年，斯蒂芬·库克证明了一个非同小可的数学结论，就是说所有这些问题其实都是等价的，只要我们找到一个多项式时间算法（复杂性类似 N 2）解决其中一个问题，那我们据此就能找到所有问题的多项式时间算法。库克因此获得了 1982 年的图灵奖。
美国克雷数学研究所（ Clay Mathematics Institute）公布了 7 个悬而未决的问题，解决其中一个就可以获得 100 万美元奖金。而问题之一是： P 是否等于 NP？换句话说，这些难题到底跟那些简单的问题是不是一类？（ 7 个问题中的另一个，可以追溯到 20 世纪初的“庞加莱猜想”，已经被俄罗斯数学家格里戈里·佩雷尔曼解决，奖金已经在 2010年发放。所以，现在还剩下 6 个待解决的问题——为了防止别人捷足先登，解题要趁早噢～）
对于这种复杂性，有几个地方需要特别注意。虽然 P=NP 问题很重要，但它更多的是一个理论问题，而不是一个实际问题。正如计算机科学家所说的，复杂性结果就是“最坏的”结果，有些问题的实例可能需要投入全部时间和精力，但并不是所有实例都那么难解决。这些问题也具有“渐近”的特点，也就是说，只有 N 值特别大的情况下才值得考虑。在现实生活中，或许大多数问题都能找到简单的解决办法，或许从实用角度看，近似的结果也是完全可以接受的，或许 N 很小，考虑不考虑渐近问题根本无关紧要。举例来说，如果你只需要对几十或者几百个数据项进行排序，那选择排序可能就足够快了，尽管其复杂性是二次方的，而且与快速排序的 N log N相比是每况愈下。
如果你只需造访五六个城市，要尝试所有可能的路线不是什么难事儿，但如果是 60 个城市，就有点不可行了，而 600 个城市也这么做根本就是不可能的。最后，在大多数情况下，一个近似的解决方案可能就足够好了，完全没有必要追求所谓的绝对最佳方案。而能够给出合理近似答案的算法可能要多少有多少，其中很多可能还更切合实际。
另一方面，一些重要的应用，如加密系统，则完全是建立在某个特定的问题确实极难解决的基础之上的。因此，你若能发现出一种攻击方法，无论其有多么不切实际，也都是意义非凡的。
4.5 小结
重塑人们对“我们能计算多快”的认识，多年来一直是计算机科学研究的主题。而用数据量来表示运行时间/次数（如 N 、 log N 、 N 2或 N log N），则是这一领域研究成果的集中体现。它不去纠结于这台计算机是不是比那一台更快，或者你是不是一个比我更优秀的程序员之类的问题，而是抓住了程序或算法背后的复杂性。正因为如此，才非常合适比较或推断出某些计算是否可行。（一个问题固有的复杂性和解决这个问题的算法的复杂性并不是一个概念。比如，排序是一个 N log N问题，但快速排序是一个N log N算法，而选择排序则是一个 N 2算法。）
算法和复杂性的研究是计算机科学的一个重要组成部分，既有理论也有实践。我们感兴趣的是哪些问题可以计算，哪些不可以，以及如何在无需更多内存的情况下计算得更快（或者是同样速度下使用更少的内存）。我们期待全新的、更好的计算方法。快速排序就是一个典型的例子，尽管它已经出现很多年了。
现实生活中，有许多重要的算法比我们这里介绍的简单的搜索和排序更专业更复杂。
例如，压缩算法旨在让声音（ MP3）、图片（ JPEG）和电影（ MPEG）占用更少的存储空间。错误检测和校正算法也很重要。数据在存储和传输（例如通过嘈杂的无线信道）过程中可能会受到损害；控制数据冗余的算法可以检测甚至纠正某些错误。
密码学高度依赖于算法，它需要发送只让好人看懂而不能让坏人破解的加密消息。对于必应和谷歌等搜索引擎而言，算法同样至关重要。从原理上讲，搜索引擎所做的大量工作都很简单，无非是收集网页、组织信息，使其便于搜索，所不同之处在于数据规模极大。如果每天有数十亿次查询，要搜索数十亿个网页，那么即使 N log N 的复杂性也是无法接受的。为了跟上日益增长的 Web 数据量，满足我们通过它进行搜索的需求，人们在改进算法和编程方面投入了大量聪明才智，以确保搜索引擎能够足够快。
★喜欢这篇文章？
欢迎转发至朋友圈或您的好友。
★对本文有想法？
回到首页，在“发送”栏输入观点。
长按该图片，扫描二维码，即可以一键关注本公众号。
欢迎加小编铁哥个人微信562763765