文档介绍：算法
考点1 算法的基本概念
电脑解题的过程实际上是在实施某种算法，这种算法称为电脑算法。
算法(algorithm)是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，同时是明确的；此顺序将在有限的次数后一个好的算法应到达如下目标：
(l)正确性(correctness)
正确性大体可以分为以下4个层次：
①程序不含语法错误；
②程序对于几组输入数据能够得出满足规格说明要求的结果；
③程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；
④程序对于一切合法的输入数据都能产生满足规格说明要求的结果。
(2)可读性(readability)
算法主要是为了方便入的阅读与交流，其次才是其执行。可读性好有助于用户对算法的理解；晦涩难懂的程序易于隐藏较多错误，难以调试和修改。
(3)健壮性(robustness)
当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
(4)效率与低存储量需求
效率指的是程序执行时，对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高；存储量需求指算法执行过程中所需要的最大存储空间
考点2 算法的复杂度
1算法的时间复杂度
算法的时间复杂度，是指执行算法所需要的计算工作量。同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的电脑上运行，效率均不同。这说明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与电脑硬件、软件有关的因素，可以认为一个特定算法
“运行工作量”的大小，只依赖于问题的规模(通常用整数n表示)，它是问题的规模函数。即
算法的工作量=f(n)
例如，在N×N矩阵相乘的算法中，整个算法的执行时间与该基本操作(乘法)重复执行的次数n3成正比，也就是时间复杂度为n3，即
f(n)=O(n3)
在有的情况下，算法中的基本操作重复执行的次数还随问题的输入数据集不同而不同。例如在起泡排序的算法中，当要排序的数组a初始序列为自小至大有序时，基本操作的执行次数为氏当初始序列为自大至小有序时，基本操作的执行次数为n(n- 1)/2。对这类算法的分析，可以采用以下两种方法来分析。
(1)平均性态(Average Behavior)
所谓平均性态是指各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。
设x是所有可能输入中的某个特定输入，p(x)是x出现的概率(即输入为x的概率)，t(x)是算法在输入为x时所执行的基本运算次数，则算法的平均性态定义为
其中Dn表示当规模为n时，算法执行的所有可能输入的集合。
(2)最坏情况复杂性(Worst-case Complexity)
所谓最坏情况分析，是指在规模为n时，算法所执行的基本运算的最大次数。
2算法的空间复杂度
算法的空间复杂度是指执行这个算法所需要的内存空间。
一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数，则称该算法是原地(in place)工作的。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。
考点3 数据结构的定义
数据结构(data structure)是指相互之间存在一种或多种特定关系的数据元素的集合，即数据的组织形式。
数据结构作为电脑的一门学科，主要研究和讨论以下三个方面：
(l)数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构；
(2)在对数据元素进行处理时，各数据元素在电脑中的存储关系，即数据的存储结构；
(3)对各种数据结构进行的运算。
讨论以上问题的日的是为了提高数据处理的效率，所谓提高数据处理的效率有两个方面：
(l)提高数据处理的速度；
(2)尽量节省在数据处理过程中所占用的电脑存储空间。
数据(data)：是对客观事物的符号表示，在电脑科学中是指所有能输入到