算法简介

Question

该使用合并排序算法还是快速排序算法，或者该使用数组还是链表。仅仅改用不同的数据结构就可能让结果大不相同。

使用二分查找时，你猜测的是中间的数字，从而每次都将余下的数字排除一半。

不管我心里想的是哪个数字，你在 7 次之内都能猜到，因为每次猜测都将排除很多数字！

一般而言，对于包含 n 个元素的列表，用二分查找最多需要 log_2 n 步，而简单查找最多需要 n 步。

接下来，我们用 log \ n 来表示 log_2 n 。

仅当列表是有序的时候，二分查找才管用。例如，电话簿中的名字是按字母顺序排列的，因此可以使用二分查找来查找名字。

知道算法需要多长时间才能运行完毕还不够，还需知道运行时间如何随列表增长而增加。这正是大 O 表示法的用武之地。

大 O 表示法指出了最糟情况下的运行时间。

一些常见的大 O 运行时间：

• O(log \ n) ，也叫对数时间，这样的算法包括二分查找。
• O(n) ，也叫线性时间，这样的算法包括简单查找。
• O(n * log \ n) ，这样的算法包括第 4 章将介绍的快速排序——一种速度较快的排序算法。
• O(n^2) ，这样的算法包括第 2 章将介绍的选择排序——一种速度较慢的排序算法。
• O(n!) ，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。

算法的速度指的并非时间，而是操作数的增速。

总结：

• 二分查找的速度比简单查找快得多。
• O(log \ n) 比 O(n) 快。需要搜索的元素越多，前者比后者就快得越多。
• 算法运行时间并不以秒为单位。
• 算法运行时间是从其增速的角度度量的。
• 算法运行时间用大 O 表示法表示。

附：旅行商故事

有一位旅行商。他需要前往 5 个城市。这位旅行商（姑且称之为 Opus 吧）要前往这 5 个城市，同时要确保旅程最短。为此，可考虑前往这些城市的各种可能顺序。

对于每种顺序，他都计算总旅程，再挑选出旅程最短的路线。5 个城市有 120 种不同的排列方式。因此，在涉及 5 个城市时，解决这个问题需要执行 120 次操作。涉及 6 个城市时，需要执行 720 次操作（有 720 种不同的排列方式）。涉及 7 个城市时，需要执行 5040 次操作！

推而广之，涉及 n 个城市时，需要执行 n! （n 的阶乘）次操作才能计算出结果。因此运行时间为 O(n!) ，即阶乘时间。除非涉及的城市数很少，否则需要执行非常多的操作。如果涉及的城市数超过 100，根本就不能在合理的时间内计算出结果——等你计算出结果，太阳都没了。

这种算法很糟糕！Opus 应使用别的算法，可他别无选择。这是计算机科学领域待解的问题之一。对于这个问题，目前还没有找到更快的算法，有些很聪明的人认为这个问题根本就没有更巧妙的算法。面对这个问题，我们能做的只是去找出近似答案。