第1章　二级公共基础知识

1.1　数据结构与算法

1.1.1　算法

1.算法的定义

所谓算法是指解题方案的准确而完整的描述，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的、明确的，此顺序将在有限的次数后终止。

2.算法的基本特征

作为一个算法，一般应具有以下几个基本特征：

（1）可行性

针对实际问题设计的算法，人们总希望能够得到满意的结果。但一个算法又总是在某个特定的计算工具上执行的，因此，算法在执行过程中往往要受到计算工具的限制，使执行结果产生偏差。在设计一个算法时，必须考虑它的可行性，否则不会得到满意的结果。

（2）确定性

算法中的每个步骤都必须有明确定义，不允许有模棱两可的解释，也不允许有多义性。

（3）有穷性

算法的有穷性是指算法必须在有限的时间内做完，即算法必须能在执行有限个步骤后终止。

（4）输入/输出性

输入/输出性又称拥有足够的情报，即一个算法是否有效，还取决于为算法所提供的输入信息是否足够。

3.算法的基本要素

一个算法通常由两个基本要素组成：对数据的运算和操作、算法的控制结构。

（1）算法中对数据的运算和操作

算法中对数据的基本运算和操作有以下四类：

①算术运算：主要包括加、减、乘、除等运算。

②逻辑运算：主要包括“与”“或”“非”等运算。

③关系运算：主要包括“大于”“小于”“等于”“不等于”“大于等于”“小于等于”等运算。

④数据传输：主要包括赋值、输入、输出等操作。

（2）算法的控制结构

算法的控制结构是指算法中各操作之间的执行顺序。它包含顺序结构、选择（分支）结构和循环（重复）结构三种，如图1-1-1所示。

4.算法设计基本方法

算法设计基本方法有列举法、归纳法、递推法、递归法和回溯法。

（1）列举法

列举法的基本思想是根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。

（2）归纳法

归纳法的基本思想是通过列举少量的特殊情况，经过分析，最后找出一般的关系。归纳法要比列举法更能反映问题的本质，并且可以解决列举量为无限的问题。归纳是一种抽象，即从特殊现象中找出一般关系。

（3）递推法

所谓递推是指从已知的初始条件出发，逐次推出所要求的中间结果和最后结果。其中初始条件或是问题本身已经给定，或是通过问题的分析与化简而确定。

（4）递归法

在工程实际中，有许多问题就是用递归来定义的，数学中的许多函数也是用递归来定义的。递归分为直接递归与间接递归两种。

（5）回溯法

在工程上，有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤，并且也不能进行无限的列举。对于这类问题，一种有效的方法是“试”。通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解；若试探失败，就逐步回退，换别的路线再进行试探，这种方法称为回溯法。

5.算法的复杂度

算法复杂度主要包含时间复杂度与空间复杂度。

（1）算法的时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运算次数来度量，即算法的时间复杂度是指算法执行过程中所需要的基本运算次数。

①平均性态分析：是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。

②最坏情况分析：是指在规模一定时，算法所执行的基本运算的最大次数。

③例题分析：

【例1-1-1】

x=x+1

基本运算：x增加1。

基本运算的执行次数：1。

时间复杂度：O（1）。

【例1-1-2】

基本运算：x增加1。

基本运算的执行次数：n。

时间复杂度：O（n）。

【例1-1-3】

基本运算：x增加1。

基本运算的执行次数：

i=2　　0次

i=3　　1次

i=4　　2次

︙　　︙

i=n　　n-2次

总次数=1+2+3+…+（n-2）=（n-1）（n-2）/2=（n*n-3*n+2）/2

时间复杂度：O（（n*n-3*n+2）/2），即O（n2）。

（2）算法的空间复杂度

一个算法的空间复杂度一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占用的空间、输入的初始数据所占用的存储空间以及算法执行过程中所需要的额外空间。