第一节算法和数据结构的基本概念.doc

第一节 算法和数据结构的基本概念 一、算法 (一)算法的基本概念 算法是指解题方案的准确而完善的描述。通常，程序的编制不可能优于算法的设计。 算法的基本特征： 1可行性(effectiveness)：算法受计算机工具的限制，使执行结果产生偏差。在设计一个算法时，必须要考虑它的可行性，否则是不会得到满意结果的。 2确定性(definiteness)：算法的确定性，是指算法中的每一个步骤都必须有明确定义，不允许有歧义和多义。 3有穷性(finiteness)：算法的有穷性是指计算时间和计算程序的有穷性。 4拥有足够的情报：初始数据的积累运用，避免输错或漏输。 b.算法的基本要素： 一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。 通常，计算机可以执行的基本操作是以指令的形式描述的。 一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。 在一般的计算机系统中，基本的运算和操作有以下几种： 1算术运算：主要包括加、减、乘、除等运算； 2逻辑运算：主要包括“与”“或”“非”等运算； 3关系运算：主要包括“大于”“小于”“等于”“不等于”等运算； 4数据传输：主要包括赋值、输入、输出等运算. 计算机程序也可以作为算法的一种描述，但由于在编制计算机程序时通常要考虑很多与方法和分析无关的细节问题（如语法问题），因此，在设计算法的一开始，通常并不直接用计算机程序来描述算法。 算法的主要特征着重于算法的动态执行，它区别于传统的着重于静态描述或按演绎方式求解问题的过程。传统的演绎数学是以公理系统为基础的，问题的求解过程是通过有限次推演来完成的，每次推演都将对问题作进一步描述，如此不断推演，直到直接将解描述出来为止。而计算机算法则是使用一些最基本的操作，通过对已知条件一步一步地加工和交换，从而实现解题目标。这两种解题方法的思路是不同的。 一个算法的功能不仅取决于所选用的操作，而且还和各操作之间的执行顺序有关。算法各操作之间的执行顺序称为算法的控制结构。 算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、循环、选择三种控制结构组合而成。 c.算法设计的基本方法： 1列举法：通常用于解决“是否存在”或“有多少种可能”等类型的问题，例如求解不定方程的问题。同时列举算法在寻找路径、查找、有哪些信誉好的足球投注网站等实际问题中是很有效的。因此，列举算法是计算机算法中的一个基础算法。 2归纳法：要比列举法更能反映问题的本质，并且可以解决列举量为无限的问题。其基本思想为通过列举少量的特殊情况，经过分析，最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。但由于在归纳过程中不可能对所有情况进行列举，因此，最后由归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的证明。 3递推：是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。其工程上很多递推关系式实际上是通过对实际问题的分析和归纳得到的，因此，递推关系式往往是归纳的结果。 递推算法在数值计算中是常见的。但是，对于数值型的递推算法必须要注意数值计算的稳定性问题。 4递归：现将问题分解为许多简单的问题，解决后再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。递归在可计算性理论和算法设计中占有很重要的地位。递归分为直接递归和间接递归两种。如果一个算法P显式地调用自己则称为直接递归。如果算法P调用另一个算法Q,而算法Q又调用算法P，则称为间接递归调用。递归是很重要的算法设计方法之一。 递推与递归的异同点： 递推是从初始条件出发，逐次推出所需要的结果；而递归则是从算法本身到达递归边界的。通常，递归算法要比递推算法清晰易读，其结构比较简练。特别是在许多比较复杂的问题中，很难找到从初始条件推出所需结果的全过程，此时，设计递归算法要比递推算法容易的多。但递归算法的执行效率比较低。 5减半递推技术：所谓“减半”，就是讲问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。 6回溯法：在处理复杂数据结构方面有着广泛的应用。 (二)算法的复杂度 算法的复杂度主要包括时间复杂度和空间复杂度。 算法的时间复杂度：是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数。即： 算法的工作量=f(n)其中n是问题的规模。 b.算法的空间复杂度：一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占用的存储空间以及算法执行过程中所需要的额外空间。 二、数据结构的基本概