伪·从零开始学算法 - 1.1 - 算法的简述

算法的定义

按照一定规则解决某一类问题的明确和有限的步骤。（人教版高中数学必修 3）

任何良定义的具体计算步骤的一个序列。（《算法导论》原书第 3 版. 北京: 机械工业出版社. 2013 年 1 月）

算法的特征

高德纳在他的著作《计算机程序设计艺术》里对算法的特征有如下归纳：

  • 输入
    一个算法必须有零个或以上输入量。
  • 输出
    一个算法应有一个或以上输出量，输出量是算法计算的结果。
  • 明确性
    算法的描述必须无歧义，以保证算法的实际执行结果是精确地匹配要求或期望，通常要求实际运行结果是确定的。
  • 有限性
    依据图灵的定义，一个算法是能够被任何图灵完备系统模拟的一串运算，而图灵机只有有限个状态、有限个输入符号和有限个转移函数（指令）。而一些定义更规定算法必须在有限个步骤内完成任务。
  • 有效性
    又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

简要来说，一个算法的描述是准确的；输入可有可无，但必须要有输出；要在有限步骤内完成；能够准确解决特定问题。

算法的表现形式

算法的表现形式有自然语言、流程图、伪代码等。

自然语言就是将算法的各个步骤直接写出来。

流程图通过特定的图形符号、连接线和文字说明，叙述算法步骤。

伪代码通过介于编程语言和自然语言的形式（更类似于编程语言），描述算法步骤。

自然语言和伪代码均无特定形式，能够解释清楚意思即可。

比如说计算三个数 、、 中的最大值的算法，用三种形式表现如下：

自然语言：

第一步：若 ，则 ；否则，。

第二步：若 ，则 。 即为它们中的最大值。

流程图：

流程图

伪代码：

1
2
3
4
5
input a, b, c
if a >= b {max = a} else {max = b}
if c >= max {max = c}
print max
end

因为不是现有代码，所以伪代码的格式并非统一。以能够精确描述，让人准确理解、无歧义为准。

在后面的示例中，我主要使用流程图。

参考资料