文档介绍：算法与算法分析

计算机与算法有着不可分割的关系，可以说，没有算法就没有计算机，计算机无法独立
于算法而存在，因此算法被誉为计算机的灵魂。但是， t←t*10 + a

s←s+t

i←i+1

输出 s

结束

图 1 例 2 的流程图由以上例子可以看出，一个算法由一些操作组成，这些操作是按一定的控制结构所规定
的次序执行的。
这些操作包括：①逻辑运算：与、或、非；②算术运算：加、减、乘、除；③数据比较：
大于、小于、等于、不等于；④数据传送：输入、输出、赋值。
算法中的每一步都必须能分解成这些基本操作，否则算法是不可行的。算法的功能不仅
取决于所选用的操作，还取决于各操作之间的执行次序，即控制结构。任何复杂的算法都可
以用顺序、选择、循环三种控制结构组合而成。用流程图可以形象地表示出算法的控制结构。
2. 算法的基本特性
著名计算机科学家 Knuth 把算法的性质归纳为以下五点。
（1）有穷性（Finiteness）
一个算法必须在执行有穷步之后结束，即任何算法必须在有限时间内完成。算法的执行
步数是有限的，解必须在有限步内得到，不能出现“死循环”，任何不会终止的算法都是没
有意义的。算法执行时间应该合理，这种合理性应该具体问题具体分析。如果一个算法在计
算机上要运行上千年，那就失去了实用价值，尽管它是有穷的。
（2）确定性（Definiteness）
组成算法的每个步骤都是确定的、明确无误的。也就是说，算法中的每一步必须有确切
的含义，理解时不能产生二义性，不能模棱两可，不能含糊不清。
例如，生活中假定照着菜谱学做菜，这道菜的做法是这样的：
第一步：锅中放入少许油，加花椒爆香；
第二步：放入切好的肉片，煎炒到适当的时候放水；
第三步：煮沸时，加入少量调味品；
第四步：淋入适量香油，出锅。
生活中可以按照这样的菜谱做菜，但让计算机执行这样的“算法”就不行，因为其中有
“少许”、“适当”、“少量”、“适量”等不确定性的词汇。如果把这个菜的做法看成一个“算