算法在计算机中的作用#

什么是算法？为什么研究算法是值得的？算法在计算机使用的其他技术中扮演什么角色？本章将回答这些问题。

算法#

非正式地说，算法是任何定义明确的计算过程，它接收某个值或一组值作为输入，并在有限时间内生成某个值或一组值作为输出 。因此，算法是一系列将输入转化为输出的计算步骤。

您也可以将算法视为解决明确指定的计算问题的工具。问题的陈述通常以一般术语规定了问题实例所需的输入/输出关系 ，通常这些实例的规模可以任意大。算法则描述了一种具体的计算过程，用于实现所有问题实例的输入/输出关系。

例如，假设你需要将一组数字按单调递增的顺序进行排序。这个问题在实际中经常出现，并为引入许多标准设计技术和分析工具提供了丰富的素材。以下是我们对排序问题的正式定义：

• 输入：一个由 n 个数字组成的序列 \(a_1, a_2, ..., a_n\)。
• 输出：输入序列的一个排列（重新排序）为 \(a'_1, a'_2, ..., a'_n\)，使得\(a'_1 \leq a'_2 \leq ... \leq a'_n\)

因此，给定输入序列 {31; 41; 59; 26; 41; 58}，一个正确的排序算法将输出序列 {26; 31; 41; 41; 58; 59}。这样的输入序列被称为排序问题的一个实例。一般来说，一个问题的实例由输入组成（满足问题陈述中规定的各种约束），这些输入是计算问题解决方案所需的。

评论