牛津通识读本：数学（中文版） [16]
有四个对象A、B、C、D时情况如何呢？分析起来就更加困难了。你可能仍从比较A和B开始。但一旦比完这一对，接下来的比较就会有两种本质不同的可能性。一种是用A或B来比较C，另一种是比较C和D，哪种主意更好并不明显。
设想你要比较B和C。如果幸运，你就能够对A、B、C进行排序。假设排序就是A，B，C。接下来还需要考虑D适合什么位置。最好的办法是先比D和B。在这之后，你就只需再比较一次，即比较D和A（如果D比B好）或比较D和C（如果B比D好）。以上一共比较了四次——两次来确定A、B、C的顺序，两次找出D的位置。
我们还没有分析完这个问题，因为在A、B、C的比较中你可能并不走运。也许比完前两次以后，你只知道A和C都比B好。那么面临着另一个困境：是比较A和C更优呢，还是用D来与A、B和C中的一个比较更优呢？考虑完各种情况及各种子情况，你还需要再观察，如果第二次比较的是C和D，情况会如何。
分析变得烦琐起来，但终究还是能够完成的。它表明，五次比较总是足够的，有时必须要比较五次之多，且第二次比较应当在C和D间进行。
这种论证的麻烦在于，要考虑的情况数量会急剧增加。譬如当对象有100个时，需要比较的确切次数是不可能算出来的——几乎可以确定这个数永远无从得知。（我犹记得，当我第一次听一位数学家宣称某个特定量的确切值永远无法算出，我当时有多么震惊。但现在我已经习以为常了，这是常有的事，并不是特殊情况。当时的那个数是拉姆齐数R（5，5），即为了保证n个人中必有五人全部两两认识，同时必有五人全部两两陌生，那么n至少是多大。）作为替代，我们要去寻找上界和下界。对于这个问题来讲，上界cn的意思是，对n个物体进行排序的某种过程至多进行cn次比较，下界bn的意思是：无论你有多聪明，有时候也必须要做上bn次比较才行。这个例子中，已知的最优上界和下界正相差一个乘数因子：相差常数倍情况下，对n个对象进行排序所需的比较次数为nlogn。
要理解这为什么有意思，你不妨自己构思一种排序过程。一种明显的方法是，先找出排序最靠前的对象放到一边，接下来再重复进行。为了找到最好的对象，先比较头两个，再将胜出者与第三个比，再将胜出者与第四个比，依此类推。这种办法下，需要比较n-1次才能找到最好的，再找出次好的需要比较n-2次，等等等等，于是总的比较次数为（n-1）+（n-2）+（n-3）+…+1，计算得约为n2/2。
尽管这种方法很自然，但如果你采用它，最终排列完时就比较了所有对象中的每一对，所以它其实是最低效的方法（虽然它的确具有易编程的优点）。当n很大时，nlogn是对n2/2很显著的改进，因为logn比n/2要小得多。
下述方法被称为“快速排序”，它并不能保证一定就会更快，但通常情况它都会快很多。它是如下递归（即利用自身）定义的。首先选择任一对象，比如x，再将其他对象分成两堆，一堆全都优于x，另一堆全都劣于x。这需要比较n-1次。接下来你只需分别对两堆进行排序——再次利用快速排序。也就是，对每一堆来讲，选出一个对象，将剩余对象分成两小堆，依此类推。一般来说，除非你运气很差，否则分出的两堆中对象数量是差不多的。于是可以表明，所需比较次数大致为nlogn。换句话说，这种方法通常都能以你期待的效率运作，相差常数倍以内。
第八章 常见问题
1. 数学家在30岁以后就不比当年了，这是真的吗？
这种传说影响颇为广泛，正由于人们误解了数学能力的本质，才使得它很有吸引力。人们总喜欢把数学家看作极具天资的人，并认为天资这种东西有些人生来就有，其他人则绝难获得。
其实，年龄与数学成果间的关系对不同人来说差别很大。的确有一部分数学家在20来岁的时候做出了他们最杰出的工作，但绝大多数人都认为，他们的知识水平和专业素质终其一生都在稳健地提高，在许多年里，这种专业水平的增长都能够弥补“原生”脑力的任何衰退（如果确实有“原生”脑力这回事的话）。确实数学家在年逾40岁之后就少有重要的突破性进展了，但这也很有可能是社会学方面的原因。到了40岁时，如果有人还有能力做出突破性的工作，那么他极有可能早已因之前的工作闻名遐迩，因而有可能也不像未成名的年轻数学家那样具有奋斗精神。不过还是有很多反例的，有很多数学家在退休之后热情不减，还继续在数学领域工作。
一般来讲，人们通常所想象的数学家的形象——可能很聪明，但有点古怪，穿着邋遢，毫无性欲，比较孤僻——的确不是一种讨喜的形象。有一部分数学家在一定程度上的确符合这种形象，但如果你认为不这样就做不好数学，这种想法可就太蠢了。实际上，如果所有其他条件都相同的话，可能你还要比这些怪数学家更胜一筹。一开始学习数学的所有学生中，最后成为专职研究人员的比例极小，更多的人在早期阶段便离开了数学，比如失去兴趣、没有申请到读博机会，或者得到了博士学位但没有获得教职。在我看来（实际上不仅只有我这么想），对最终通过了这层层考验的人来说，那些“怪人”所占的比例比占一开始学习数学的学生的比例要小。
对数学家这样的负面刻画可能杀伤力很大，吓走许多本来可能喜欢并且擅长这一领域的人，但是“天才”这个词则更加恶毒，杀伤力更大。这里有一个现成的对“天才”的大致定义：对于别人必须经过多年实践都未必能够掌握的事情，天才就是那些在少年时期就能够轻易做好这些事的人。天才的成就有着魔法般的特质，就好像他们的大脑并不只是比我们更有效率，而是运转方式完全不同。剑桥大学每年都会有一两个数学系本科生，他们经常在数分钟之内就能解决的问题，大多数人——包括应该能够教他们的人——往往需要花上几个小时以上。遇到这种人的时候，我们只能退避三舍、顶礼膜拜。
然而，这些超乎寻常的人并不总是最成功的数学研究者。如果你想要解决某个问题，而之前尝试过的数学家都以失败告终，那么你需要具备种种素质，在这其中天赋（如我所定义的那样）既不是必要的也不是充分的。我们可以通过一个极端一点的例子来说明这一点。安德鲁·怀尔斯（在刚到40岁的时候）证明了费马大定理（即对任意正整数x，y，z及大于2的正整数n，xn+yn不可能等于zn），解决了世界上最著名的数学难题。毫无疑问他很聪明，但他并不是我所说的天才。
你可能会问，如果没有某种神秘的超常脑力，他还可能完成这一切吗？回答是，尽管他的成就非常卓著，但也没有卓越到无法解释的程度。我并不了解究竟是什么因素促使他成功的，但他肯定需要非凡的勇气、坚定和耐心，对他人完成的艰难工作的广泛了解，在正确时间专攻正确领域的运气，以及杰出的战略性眼光。
上面所说的最后一条素质，从根本上要比惊人的大脑运转速度更加重要。数学中绝大多数影响深远的贡献是由“乌龟”们而不是“兔子”们做出的。随着数学家的成长，他们都会逐渐学会这个行当里的各种把戏，部分来自于其他数学家的工作，部分来自于自己对这个问题长时间的思考。是否能将他们的专长用于解决极其困难的问题，则在很大程度上决定于细致的规划：选取一些可能会结出丰硕成果的问题，知道什么时候应该放弃一条思路（相当困难的判断），能够先勾勒出论证问题的大框架继而再时不时地向里面填充细节。这就需要对数学有相当成熟的把握，这绝不与天赋相矛盾，但也并不总是会伴随着天赋。
2. 为什么女性数学家很少见？
真想回避这个问题，因为回答这个问题很容易冒犯别人。但是，在全世界各地的数学系所中，即便是在今日，女性所占比例仍然很小；这是一个值得注意的现象，也是数学生活中的一个重要事实，我被迫感到不得不说点什么，尽管我所要说的也无非是对此感到不解和遗憾。
值得强调的一点是，数学家中女性较少只不过是一种统计现象：确实有十分优秀的女性数学家，与男性同行一样，她们表现优秀的方式也多种多样，有时也包括拥有天赋。没有任何迹象表明，女性在数学中所能达到的成就会有上限。我们有时会读到，在特定的智力测试中——比如说视觉空间能力，男性表现得更优秀，有人认为这解释了他们主导着数学领域的原因。然而，这样的论据不足以令人信服，因为视觉空间能力能够通过练习来增强，而且尽管它有时对数学家有帮助，却并非不可或缺。
更可信的一种理由是社会方面的因素：当男孩子为数学能力感到骄傲时，可以想象某个女孩子可能会为自己擅长这项不那么女性化的事务而感到窘迫。而且，有数学天赋的女孩子所能够效仿的榜样很少，她们只能靠自我保持、自我强化。一项社会因素可能会在之后发挥更大的作用：比起其他学科来，数学需要一个人更加专注，这虽然不是不可能，但也很难与女性的母亲身份相结合。小说家坎迪亚·麦克威廉曾经说，她的每个孩子都使她少写了两本书，不过在几年未动笔之后，她至少还能够重新写小说。但如果你几年没有做数学，你就失去了数学的习惯，很难再重拾了。
有人认为，女性数学家发展起自己事业的时间往往晚于男性同行，而数学家的职业结构倾向于回报早期成就，这就使得女性处于一种不利的地位。最杰出的一些女性数学家的人生故事支持了这种说法。不过她们发展自己职业生涯较晚的原因，基本上都是上面所说的社会原因，而且也有许多这方面的例外。
不过，这些解释看起来都不够充分。我在此不再深入探讨了。我还能做的就是告诉大家，关于这方面已经出了几本书（参见“延伸阅读”）。最后再加上一点评论：这样的情况是在不断进步的。数学家中女性所占的比例近年来在稳步提高，而且随着社会大环境的不断改变，这样的现象一定还会持续下去。
3. 数学与音乐息息相通吗？
尽管有很多数学家完全不了