文档介绍：1 一:算法
算法是指对解题方案准确而完整的描述。
(1)算法的基本特征。
可行性:针对实际问题而设计的算法,执行后能够得到满意的结果,
即必须有一个或多个输出。注意,对于某一算法,即使在数学理论上是正确
的,但如果在实际的计算工具上不能执行,则该算法也是不具有可行性的。
确定性:指算法中每一步骤都必须是有明确定义的。
有穷性:指算法必须能在有限的时间内做完。
拥有足够的情报:一个算法是否有效,还取决于为算法所提供的情报是否足够。
(2)算法的基本要素。
算法一般由两种基本要素构成:对数据对象的运算和操作;
算法的控制结构,即运算和操作时间的顺序。
算法中对数据的运算和操作:算法就是按解题要求从指令系统中选择合适的指令组成的指令序列。因此计算机算法就是计算机能执行的操作所组成的指令序列。不同的计算机系统,其指令系统是有差异的,但一般的计算机系统中都包括的运
算和操作有4类,即算术运算、逻辑运算、关系运算和数据传输。
算法的控制结构:算法中各操作之间的执行顺序称为算法的控制结构。算法的功能不仅取决于所选用的操作,还与各操作之间的执行顺序有关。基本的控制结构包括顺序结构、选择结构和循环结构。
(3)算法设计的基本方法。
算法设计的基本方法有列举法、归纳法、递推法、递归法、减半递推技术和回溯法。
算法的复杂度主要包括时间复杂度和空间复杂度。
(1)算法的时间复杂度。
所谓算法的时间复杂度,是指执行算法所需要的计算工作量。
一般情况下,算法的工作量用算法所执行的基本运算次数来度量,而算法所执行的基本运算次数是问题规模的函数,即算法的工作量=f(n)。其中n是问题的规模。这个表达式表示随着问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同。
在同一个问题规模下,如果算法执行所需的基本运算次数取决于某一特定输入时,可以用两种方法来分析算法的工作量:平均性态分析和最坏情况分析。
(2)算法的空间复杂度。
一个算法的空间复杂度,一般是指执行这个算法所需要的内存空间。算法执行期间所需要的存储空间包括3个部分:
算法程序所占的空间;
输入的初始数据所占的存储空间;
算法执行过程中所需要的额外空间。
在许多实际问题中,为了减少算法所占的存储空间,通常采用压缩存储技术。
二:数据结构的基本概念
数据结构是指相互有关联的数据元素的集合,即数据的组织形式。
(1)数据的逻辑结构。
所谓数据的逻辑结构,是指反映数据元素之间逻辑关系(即前、后件关系)的数据结构。它包括数据元素的集合和数据元素之间的关系。
(2)数据的存储结构。
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称为数据的物理结构)。数据结构的存储方式有顺序存储方法、链式存储方法、索引存储方法和散列存储方法。而采用不同的存储结构,其数据处理的效率是不同的。因此,在进行数据处理时,选择合适的存储结构是很重要的。
数据结构研究的内容主要包括3个方面:
数据集合中各数据元素之间的逻辑关系,即数据的逻辑结构;
在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;
对各种数据结构进行的运算。
数据元素之间最