计算机二级公共基础教程书稿.docVIP

1 数据结构与算法 1.1 算法的复杂度 1.1.1 算法的基本概念 所谓算法是指解决问题的方法和步骤。 利用计算机算法为计算机解题的过程实际上是在实施某种算法。 1.算法的基本特征 算法一般具有4 个基本特征：可行性、确定性、有穷性、拥有足够的情报。 （1）可行性：算法中有待执行的运算和操作必须是相当基本的，换言之，它们都是能够精确地进行的，算法执行者甚至不需要掌握算法的含义即可根据该算法的每一步骤要求进行操作，并最终得出正确的结果。如在算法中不允许出现分母为0的情况。 （2）确定性：算法的每一个步骤必须要确切地定义。即算法中所有有待执行的动作必须严格而不含混地进行规定，不能有歧义性。 （3）有穷性：一个算法在执行有穷步之后必须结束。也就是说，一个算法，它所包含的计算步骤是有限的。 （4）拥有足够的情报： 一个算法是否有效，还取决于为算法所提供的情报是否足够。通常，算法中的各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，这是算法执行的起点或是依据。因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。当输入不够或输入错误时，算法本身也就无法执行或导致执行有错。一般来说.当算法拥有足够的情报吋，此算法才是有效的，而当提供的情报不够时，算法可能无效。 2. 算法的基本要素 一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。 (1)算法中对数据的运算和操作 每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。因此，计算机算法就是计算机能处理的操作所组成的指令序列。 通常计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合,称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列。在一般的计算机系统中，基本的运算和操作有以下四类： ① 算术运算：主要包括加、减、乘、除等运算。 ② 逻辑运算：主要包括“与”、“或”、“非”等运算。 关系运算：主要包括“大于”、“小于”、“等于” 、“不等于“等运算。 数据传输：主要包括赋值、输入、输出等操作。 算法的设计一般都应从上述的四种操作考虑，通过对已知条件一步一步加工和变换，从而组成解题的操作序列。 （2）算法的控制结构 一个算法的功能不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。 算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、NS结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。 (a) 顺序结构 (b) 选择结构 (c)循环 图1.1 三种基本结构 3. 算法设计基本方法 计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。计算机算法不同于人工处理的方法。 算法基本设计方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。 （1）列举法 列举法的基本思是根据提出的问题,列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的，列举法常用于解决“是否否存”，或“有多少种可能”等类型的问题，例如求解不定方程的问题。 列举法的特点是算法比较简单。伹当列举的可能情况较多吋，列举算法的工作量将会很大。因此,在用列举法设计算法时,使方案优化,尽量减少运算工作量，是应该重点注意的。通常，在设计列举算法时，只要对实际问题进行详细的分析，将与问题有关的知识条理化、完备化、系统化，从中找出规律；或对所有可能的情况进行分类，引出-些有用的信息，是可以大大减少列举量的。 列举算法虽然是一种比较原始的方法，其运算量比较大，但在有些实际问题中（如寻找路径、査找、有哪些信誉好的足球投注网站等问题）、局部使用列举法却是很有效的，因此，列举算法是计算机算法中的一个基础算法。 （2） 归纳法 归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。显然,归纳法要比列举法更能反映问题的本质，并且可以解决列举量为无限的问题。但是，从一个实际问题中总结归纳出一般的关系，并不是一件容易的事情，尤其是要归纳出一个数学模型更为困难。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。 归纳是一种抽象，即从特殊现象中找出一般关系。但由于在归纳