c语言入门18，作为程序员，你的使命是什么？程序员都是如何衡量效率的？

第 16 节介绍了算法的概念，并且举出了数组插入排序算法的例子。能够解决问题的算法往往不止一个，不同的算法之间在效率上存在显著的差异，为了说明这一差异性，我们在第 17 节又分析了数组的归并排序算法。这几节我想介绍的其实并不是算法本身，而是一种观念：能够设计算法并编写代码完成的，是程序员。不会算法，只会写代码的，是码农。

能够写出库给别人调用的，是程序员。只会调用别人库的，是码农。

再来说说不同算法之间的差异性，因为计算机的资源是有限的（运算速度有限，存储空间有限），所以优秀的程序员应该能够设计出开销更小，效率更高的算法，这就需要一个衡量算法性能的标准。

那，程序员是怎样衡量算法的性能的呢？

比较评价算法的好坏，一个非常重要的标准是算法输出正确结果所需时间，这个指标一般被称作“时间复杂度”。还是举例说明，先来看看 C语言 的数组插入排序算法，假设数组长度为 N，循环中各条语句的执行时间分别是 c1, c2, c3, c4, c5 这样五个常数。

受操作系统影响，C 语言每条指令的严格执行时间不一定每次都一样，但是指令执行的上限时间一定是一个常数。

忽略 for 和 while 赋值表达式和条件判断消耗的时间，假设 while 循环 M 次，则上面的函数执行时间为 (N-1) * (c1+c2+c5+M * (c3+c4))。M 不是一个常数，那它和 N 有什么关系吗？

先来考虑需要排序的数组，如果输入的数组已经是拍好序的，那 while 一次也不执行，M = 0。函数执行时间 = aN + b，其中 a = c1+c2+c5，b = -(c1+c2+c5)，显然是线性函数。

那如果输入的数组是倒序排列的（最坏的情况），或者随意排序的，那每次循环都将已排序的数组元素与 cur 比较，这时 M 就与 N 有关系了，N 越大，M 也越大，M 差不多与 N 是正相关的关系，不管它俩关系到底如何，函数消耗的总时间为 aN^2+bN+c，是N的二次函数。

实际应用中，在分析算法的时间复杂度时，往往关心最坏的情况，因为最坏的情况确定了算法消耗时间的上界，这为进一步分析其他工作提供了可靠参考。比较线性函数 aN + b 和二次函数 aN^2+bN+c，往往关心的是自变量 N 的指数，系数不是太过需要关心的。例如 100N+1 和 N^2 + 1，虽然二次函数的系数比较小，但是如果数组元素超过 100 个，二次函数就会明显大于一次函数了。

所以，如果同一个问题可以用两种算法解决，其中一种算法的时间复杂度为线性函数，另一种算法的时间复杂度为二次函数，当问题的输入长度n足够大时，前者明显优于后者。因此我们可以用一种更粗略的方式表示算法的时间复杂度，把系数和低次幂项都省去，线性函数记作Θ(n)，二次函数记作Θ(n2)。

再来看看 C 语言的数组归并排序算法，按照同样的方法，可以得到它的时间复杂度为 Θ(nlgn)，当 n 非常大时，它的效率会远远高于插入排序算法。例如，N=1000时，lgN 大致为 10，N^2 已经很大了，而 N=100万时，lgN 也才为 20 左右。虽然对于小的输入规模，插入排序要比归并排序快，但是一旦输入规模 N 足够大，归并排序 lgN 对 N 的优点将足以补偿常熟因子的差别。

下面来看一个例子：为了对 1000 万个元素的数组排序，我们让世界上最精巧的程序员用机器码编写插入排序算法，结果代码需要 2N^2 条指令。让水平非常一般的程序员，用带有低效编译器的高级语言编写归并排序算法，结果代码需要 50 * NlgN 条指令。然后，在每秒能够执行百亿条指令的计算机A上运行插入排序算法，再在每秒仅能执行千万条指令的计算机B上运行归并排序算法，结果：

计算机A所花时间 = (2 x 1000万的平方)/100亿每秒 = 5.5 小时
计算机B所花时间 = (50 x 1000万 x lg1000万)/1000万每秒 = 20 分钟

可以看出，这样的情况下，归并排序还能比插入排序快 17 倍。事实上，如果需要排序的元素有 1 亿个，插入排序需要 23 天，而归并排序只需要不到 4 小时。

通过这几节介绍的例子，可以看出，我们应该像对计算机硬件一样，把算法也当作是一种技术。整个系统的性能不仅依赖于硬件的选择，也与依赖于有限算法的选择。当然了，作为程序员，应能够在没有现成的有效算法的情况下，设计出低开销，但是高效率的算法，这就是程序员的使命。