|
基本概念 1、算法：规则的有序有限集合; 规则是有确切含义而无二义性. 2、算法的基本特征： 可终止性;算法必须在有限时间内终止; 正确性;算法必须正确描述问题的求解过程; 可行性：算法必须是可实施的; 算法可以有0个或0个以上的输入; 算法必须有1个或1个以上的输出 算法的描述规则采用自然语言或算法流程控制采用结构化程序的基本控制结构(顺序、 选择 、重复)描述.形式语言描述; 算法与程序的关系1.程序可以不一定满足可终止性。但算法必须在有限时间内结束; 2.程序可以没有输出,而算法则必须有输出; 3.算法是面向问题求解的过程描述，程序则是算法的实现. 复杂度算法复杂度：评价算法优劣的唯一标准。由时间复杂度和空间复杂度构成. 时间复杂度:算法执行所花费的时间; 空间复杂度:算法执行所占用的内存. 设n为问题的大小(即问题所处理元素的 个数),则时间复杂度函数记为T(n),空间复杂读S(n)。 复杂度分析事前分析是算法分析的重要步骤，是在算法实现之前进行时间和空间复杂度分析。 时间复杂度分析：就是对已设计好的算法进行有效的时间。 采用的基本方法是按照算法的控制结构进行分析，首先确定问题求解的基本操作，然后按照三种控制结构分别进行基本操作数与问题处理量的关系，确定出问题的时间复杂度函数。 时间复杂度分析时间复杂度分为最坏情况的复杂度和平均情况的复杂度。 在这里对时间复杂度分析我们只进行最坏情况的复杂度分析，基本方法如下所述： 每条规则的时间复杂度直接确定 顺序结构：采用加法法则；重复结构：采用乘法法则；分支结构：采用取最大值法则。 最坏情况和平均情况分析最坏情况分析：在时间复杂度分析中，最坏情况是指在所有大小为n的输入中，选择代价最大的状态进行分析而获得的时间复杂度; 平均情况分析：平均情况分析是指在所有大小为n的输入中，首先确定每个输入出现的概率，针对每个输入及其出现的概率的进行分析而获得的时间复杂度. 基本运算 定义：如果算法中的一个元运算具有最高频度，所有其它元运算频度均在它的频度的常数倍数之内，则称这个元运算为基本运算。 在分析搜索和排序算法时，若元素比较为元运算，则为基本运算。 时间复杂度描述时间复杂度采用量级关系描述。 设时间复杂度函数为T(n), 则将T(n)描述为T(n) =O(f(n))，其含义为当n趋于无穷大时，T(n)和f(n)的比为一个不等于0的常数。 一般情况下f(n)为一个简单函数，通常有以下形式：C,n,long(n),n!,n的幂等等一些描述简单的函数. 递归方程求解的方法展开递推式； 代入法；利用已知方程的解代入； 利用生成函数求解；生成函数是组合数学的一种方法； 归纳法在算法复杂度分析中是一种常用的求解方法，根据算法的流程，可构造复杂度函数。 分治方法的基本思想当被求解的问题规模n较大，不能直接求解时，可以将该问题分成若干个规模较小的子问题； 若子问题仍不能求解，则继续进行划分，直到子问题可直接求解； 最后由子问题的解归并出原问题的解。 分治方法的基本模式Divde & conquer(n) {if (n<=n0) qwt(n); else {Divide n into subinstances n1,n2,…,nm; for ( i=1,i<=m,i++) yi=Divde & conquer(ni);} return merge(y1,y2,…,ym);} 动态规划动态规划和分治法相似,也是把待求解问题划分成若干个子问题,先求解子问题,然后,从这些子问题的解得到原问题的解.所不同的是动态规划所分解的子问题不是独立的. 动态规划通常用于求解最优性质的问题 最佳原理:不论以前状态如何,当前状态的值取决于它的所有直接前驱的状态; 最优化原理：给出一个最优的决策序列，每一个子序列自身必须上最优的决策序列 基本思想动态规划采用最佳原理,对问题从初始状态逐步求解,找出最优解.描述如下: 1)找出最优解的性质,并描述其结构; 2)递归地定义最优值; 3自底向上计算最优值，记录相关信息，最终构造最优最优解； 4）根据记录信息，最终构造最优最优解； 最优策略动态规划可以找出问题的最幼解，但是获取最佳解的计算过程复杂且计算量很大，几乎是列出所有解，才能找出最佳解。 对于任意问题，通常会存在一类约束条件和一些输入，任何满足这些约束条件的子集可以称为问题的一个可能解。最佳解则是满足目标函数达到最大值或最小值的一个可能解。 基本思想最优策略也是一个多步决策方法.每一步的选择都使得能构成问题的一个可能解，同时使目标函数值的增速加快(目标函数最大)或减小(目标函数最小),这种选择过程以一些最优化度量为根据. 最优化度量的选择方法也称为贪心法. 回溯法一般方法:回溯法的基本策略是搜索(按深度优先进行). 回溯法将问题的解表示成一个n元式(x1,x2,…,xn),其中每个xi取自某一初值集合si，称(x1,x2,…,xn)为问题的解向量. 回溯法求解问题的过程需要满足某种条件(称为约束条件)或者使问题的解满足判定函数B(x1,x2,…,xn)极大化(或极小化),希望求出约束条件或者判定函数某个解向量或所有解向量. 解空间:包含问题所有解的一棵树称为解的状态空间树; 从根结点出发搜索解的状态空间树,对于每一个结点,判定该结点是否满足约束条件和判定函数,若满足,则进入一个孩子树继续搜索,否则返回其双亲结点,进入其另一个孩子树进行搜索,直到求出问题所要求的解. 算法描述 1）对于n元式(x1,x2,…,xn),定义每一个分量的取值范围； 2）定义约束条件P(X)和判定函数B(X)； 3）设i=1; 4)对第i个元素赋一个可能值;使X =( x1,x2,…,x i);若所有可能值已经全部使用,则 i --; 重复4; 5)当P(X)和B(X)为真时. i ++;进入6,否则i --: 返回4: 6)由X =(x i)构造x i +1:返回5: 7)直到求出一个(或所有)满足约束条件P(X)和判定函数B(X)的解。 递归算法Backseach(i) {if (i>n) output(X); else {X=(xi); while B(X)&&P(X) i++;Backseach(i)} 分支限界对于回溯法而言，是要对解的状态空间树的所有分支进行搜索，这样时间复杂度是一个与树上的结点总数和树的深度的乘积。 分支限界的目的是通过一个限界函数选取合适的活结点，进行搜索，以加快速度，提高算法的效率。 基本思想定义一个限界函数 1、从初始结点开始，先计算该结点的限界值; 2、以该结点为当前活结点，生成它的所有可能的后继结点，计算各结点的限界值，按某个(升/降)序列进入活结点队列; 3、取活结点队列队头元素为当前活结点，返回2; 4、直到队空(找出问题的一个解或无解).
| 
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
淘帖
顶
踩
