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 小时。

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

阅读更多:   C语言
添加新评论

icon_redface.gificon_idea.gificon_cool.gif2016kuk.gificon_mrgreen.gif2016shuai.gif2016tp.gif2016db.gif2016ch.gificon_razz.gif2016zj.gificon_sad.gificon_cry.gif2016zhh.gificon_question.gif2016jk.gif2016bs.gificon_lol.gif2016qiao.gificon_surprised.gif2016fendou.gif2016ll.gif