文档介绍：第一章数据结构与算法
算法
算法的基本概念
算法是指对解题方案的准确而完整的描述。
对于一个问题,如果可以通过一个计算机程序,在有限的存储空间内运行有限长的时间而得到正确的结果,则称这个问题是算法可解的。但算法不等于程序,也不等于计算方法。程序作为算法的一种描述,因为在编写程序时要受到计算机系统运行环境的限制,通常还需考虑很多与方法和分析无关的细节问题。通常,程序的编制不可能优于算法的设计。
1)可行性(effectiveness)针对实际问题而设计的算法,执行后能够得到满意的结果。
2)确定性(definiteness)每一条指令的含义明确,无二义性。并且在任何条件下,算法只有唯一的一条执行路径,即相同的输入只能得出相同的输出。
3)有穷性(finiteness)算法必须在有限的时间内完成。有两重含义,一是算法中的操作步骤为有限个,二是每个步骤都能在有限时间内完成。
4)拥有足够的情报算法中各种运算总是要施加到各个运算对象上,而这些运算对象又可能具有某种初始状态,这就是算法执行的起点或依据。因此,一个算法执行的结果总是与输入的初始数据有关,不同的输入将会有不同的结果输出。当输入不够或输入错误时,算法将无法执行或执行有错。一般说来,当算法拥有足够的情报时,此算法才是有效的;而当提供的情报不够时,算法可能无效。
*:综上所述,所谓算法,是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,且是明确的,此顺序将在有限的次数下终止。
2. 算法的基本要素
(1)算法中对数据对象的运算和操作
算术运算
逻辑运算
关系运算
数据传输
(2)算法的控制结构
顺序
选择
循环
工具
传统流程图
N-S结构化流程图
算法描述语言
(1)列举法根据提出的问题,列举所有可能的情况,并用问题中给定的条件检验哪些是需要的,哪些是不需要的。因此列举法常用于解决“是否存在”或“有多少种可能”等类型的问题。
列举法的特点是算法比较简单。但当列举的可能情况较多时,执行列举算法的工作量将会很大。因此在设计算法时,使方案优化,尽量减少运算工作量应是重点。
(2)归纳法通过列举少量的特殊情况,经过分析,最后找出一般关系。归纳法要比列举法更能反映问题的本质,并且可以解决列举量为无限的问题。但是,从一个实际问题中总结归纳出一般的关系,并不容易,尤其要归纳出一个数学模型更为困难。
(3)递推法从已知的初始条件出发,逐次推出所要求的各中间结果和最后结果。其中初始条件或是问题本身已经给定,或是通过对问题的分析与化简而确定。递推本质上也属于归纳法。
(4)递归法人们在解决一些复杂问题时,为了降低问题的复杂程度,一般总是将问题逐层分解,最后归结为一些最简单的问题。这种将问题逐层分解的过程,实际上并没有对问题进行求解,而只是当解决了最后那些最简单的问题后,再沿着原来分解的逆过程逐步进行综合,这就是递归的基本思想。由此可以看出,递归的基础也是归纳。
有些实际问题既可以归纳为递推,也可以归纳为递归。通常递归算法要比递推算法清晰易读,其结构比较简练。但递归算法的执行效率比较低。
(5)减半递推技术实际问题的复杂程度往往与问题的规模有着密切的联系。因此,利用分治法解决这类实际问题是有效的。所谓分治法,就是对问题分而治之。工程上常用的分治法是减半递推技术。也是归纳法的一个分支。
(6)回溯法在工程上,有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤,并且也不能进行无限的列举。对于这类问题,一种有效的方法是“试”。通过对问题的分析,找出一个解决问题的线索,然后沿着这个线索逐步试探,对于每一步试探,若成功,就得到问题的解,若失败,就逐步回退,换别的线路再进行试探。这种方法称为回溯法。回溯法在处理复杂数据结构方面有着广泛的应用。
:是指执行算法所需要的计算工作量,可以用执行算法的过程中所需基本运算的执行次数来度量。
在同一问题规模下,如果算法执行所需的基本运算次数取决于某一特定输入时,可以用以下两种方法来分析算法的工作量:
(1)平均性态(average behavior)
(2)最坏情况复杂度(worst-plexity)
:是指执行这个算法所需要的内存空间。
算法的复杂度
选择题
( )2006年9月
,其时间复杂度也必定大
,其时间复杂度必定小
,其空间复杂度必定小
( )