第一部分
计算机公共基础
第 1 章 数据结构与算法
1.1 算法的基本概念
1．算法的定义及特性
算法是对特定问题求解步骤的一种描述，是指令的有限序列。程序是算法在计算机中的
实现。
一个算法必须满足以下 5个重要特性。
(1)有限性：一个算法必须总是在执行有穷步后结束， 且每一步都必须在有穷时间内完成。
(2)确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，不会产生疑义，
使算法的执行者或阅读者都能明确其含义及如何执行。
(3)可行性：算法中的每一步操作都应该能有效执行。
(4)输入：一个算法有零个或多个输入。当用函数描述算法时，输入往往是通过形参来表
示，在它们被调用时，从主调函数获得输入值。
(5)输出：一个算法有一个或多个输出，它们是算法进行信息加工后得到的结果，无输出
的算法没有任何意义。当用函数描述算法时，输出多用返回值或引用类型的形参表示。
2．算法的基本要素
算法的功能取决于两方面因素：选用的操作和各个操作之间的顺序。因此，一个算法通
常由以下两种基本要素组成。
(1)对数据对象的运算和操作(包括算术运算、逻辑运算、关系运算、数据传输)。
(2)算法的控制结构。
3．算法设计基本方法
虽然算法设计是一件非常困难的工作，但是算法设计也不是无章可循的，人们经过实践，
总结和积累了许多行之有效的方法。常用的算法设计方法有列举法、归纳法、递推法、递归
法、减半递推法和回溯法 6种。
4．算法设计要求
一个算法的优劣应该从以下几方面评价。
(1)正确性：不含有语法错误，对于各种合法的输入数据能够得到满足要求的结果。
(2)可读性：要求程序有较好的人机交互性，有助于人们对算法的理解。
(3)健壮性：对输入的非法数据能做出适当的响应或处理。
(4)高效率与低存储量：主要针对算法的执行时间和所需的存储空间，这两方面主要和问
题的规模有关。
5．算法复杂度
一个算法复杂度的高低体现在运行该算法所需要的计算机资源的多少，所需的资源越多，
1? ôlr08¥
3
就说明该算法的复杂度越高；反之，所需的资源越少，则该算法的复杂度越低。计算机的资
源，最重要的是时间和空间(即存储器)资源。因此，算法复杂度包括算法的时间复杂度和算
法的空间复杂度。
1)算法的时间复杂度
算法的时间复杂度是指执行算法所需要的计算工作量。
值得注意的是，算法程序执行的具体时间和算法的时间复杂度并不一致。算法程序执行
的具体时间受到所使用的计
《实用软件高级应用教程》.pdf