文档介绍：算法
考点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)：是对客观事物的符