首页 > Python算法 > 认识算法 阅读数:27

算法与程序的区别

算法和程序的定义有很大交集。通常来说,(计算机)程序指一组计算机能识别和执行,并有一定功能的指令。后者的定义似乎和算法很相似,但两者最大的区别在于程序是以计算机能够理解的各式各样的编程语言编写而成的,而算法是可以通过编程语言、图绘、口述等人能够理解的方式来描述的,不一定局限于编程语言的诠释,如图 2 所示。

算法和程序的关系
图 2:算法和程序的关系

不过,算法和程序之间并没有明确的分界线,理解二者的意思就足够了。

刚才曾提过,算法是一种以数学为本质的计算方法。然而作为方法,则必有正确(可行)、不正确(不可行),高效、低效之分。若一个算法对每一个恰当的输入(严格地符合问题的前提条件,且可以为空)都以正确的输出终止程序,则可以称该算法是正确的,并正确地解决了给定的问题。若算法以不正确的输出而终止程序,或根本无法终止程序(如程序陷入死循环),则这个算法是不正确的。

但显而易见,不是所有的算法都可以通过输入和输出的正确和不正确而简单地分为两大类。譬如人们要预测未来特定事件发生概率,而这种问题无法用结果来检验解决方法正确与否。因此,算法的正确性的检验也可以回溯到其本质,就是数学的检验,也就是说用数学来证明算法的正确性或可行性。

对算法至关重要的不只有其正确性,还有它的效率。人类至今的发展,提高最迅速的可以说就是计算的效率了。从原始人的结绳计数,到现在的超级计算机,计算能力的提升不是区区几个数量级能说明的。

但很不幸,当今计算机的运算速度不是无限快,存储器也不是免费的,所以如何高效地利用好有限的时间和空间就是算法存在的意义。有趣的是,求解相同问题而设计的不同算法在效率方面通常有显著的差异,而这些算法效率上的差异要比在硬件或者软件效率上的差异大得多。

回到 1+2+3+…+n 这个求和问题中。一定程度上说,逐个数相加也可以被看作一种解决求和问题的算法,一种简单、低效的算法。相反,求和公式则是一种较复杂、高效的算法。但如何来评判一个算法是否高效?时间复杂度和空间复杂度就是很好的丈量工具。