C公共基础知识.docVIP

第1章 数据结构与算法 1.1 算法 1.1.1 算法的基本概念 算法是指对解题方案的准确而完整的描述。简单地说，就是解决问题的操作步骤。 值得注意的是，算法不等于数学上的计算方法，也不等于程序。在用计算机解决实际问题时，往往先设计算法，用某种表达方式（如流程图）描述，然后再用具体的程序设计语言描述此算法（即编程）。在编程时由于要受到计算机系统运行环境的限制，因此，程序的编制通常不可能优于算法的设计。 1.1.1.1 算法的基本特征 一般来说，一个算法应具有以下4个基本特征。 （1）可行性（Effectiveness）：算法在特定的执行环境中执行，应当能够得出满意的结果，即必须有一个或多个输出。 （2）确定性（Definiteness）：算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。 （3）有穷性（Finiteness）：算法必需在有限时间内做完，即算法必需能在执行有限个步骤之后终止。 （4）拥有足够的情报：要使算法有效必需为算法提供足够的情报。当算法拥有足够的情报时，此算法才是有效的；而当提供的情报不够时，算法可能无效。 1.1.1.2 算法的基本要素 通常，一个算法由两种基本要素组成。 ? 对数据对象的运算和操作； ? 算法的控制结构，即运算或操作时间的顺序。 （1） 算法中对数据的运算和操作 在一般的计算机系统中，基本的运算和操作有以下4类，如表1-1所示。 表1-1 4类基本的运算和操作 （2） 算法的控制结构 一个算法的功能不仅仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。 算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。 1.1.1.3 算法设计的基本方法 虽然设计算法是一件非常困难的工作，但是算法设计也不是无章可循，人们经过实践，总结和积累了许多行之有效的方法。常用的几种算法设计方法有列举法、归纳法、递推法、递归法、减半递推技术和回溯法。 1.1.1.4 算法设计的要求 通常一个好的算法应达到如下目标： （1）正确性（Correctness） 正确性大体可以分为以下4个层次： ①程序不含语法错误； ②程序对于几组输入数据能够得出满足规格说明要求的结果； ③程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果； ④程序对于一切合法的输入数据都能产生满足规格说明要求的结果。 （2）可读性（Readability） 算法主要是为了方便人的阅读与交流，其次才是其执行。可读性好有助于用户对算法的理解；晦涩难懂的程序易于隐藏较多错误，难以调试和修改。 （3）健壮性（Robustness） 当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。 （4）效率与低存储量需求 效率指的是程序执行时，对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高；存储量需求指算法执行过程中所需要的最大存储空间。 1.1.2 算法的复杂度 算法的复杂度是算法效率的度量，是评价算法优劣的重要依据。 算法复杂度包括算法的时间复杂度和算法的空间复杂的。 1.1.2.1 算法的时间复杂度 算法的时间复杂度是指执行算法所需要的计算工作量。 为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。 算法的计算工作量是用算法所执行的基本运算次数来度量的，而算法所执行的基本运算次数是问题规模（通常用整数n表示）的函数。即 算法的工作量=f（n） 例如，在N×N矩阵相乘的算法中，整个算法的执行时间与该基本操作（乘法）重复执行的次数n3成正比，也就是时间复杂度为n3，即 f（n）=O（n3） 在有的情况下，算法中的基本操作重复执行的次数还随问题的输入数据集不同而不同。例如在起泡排序的算法中，当要排序的数组a初始序列为自小至大有序时，基本操作的执行次数为0；当初始序列为自大至小有序时，基本操作的执行次数为n（n－1）/2。对这类算法，可以采用平均性态和最坏情况复杂性两种方法来分析。 1.1.2.2 算法的空间复杂度 算法的空间复杂度是指执行这个算法所需要的内存空间。 一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执