【精品】算法分析

《【精品】算法分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法解题步骤1、问题分析2、数学模型建立3、算法设计与选择4、算法表示5、算法分析6、算法实现7、程序调试8、结果整理文档编制什么是算法？算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。算法的3要素：操作，控制结构，数据结构算法的控制结构：顺序结构，选择结构，循环结构算法的基本特征：1、有穷性2、确足性3、口J行性4、算法有零个或多个的输入5、算法有一个或多个输出算法的6种表示方式：自然语言，流程图，盒图，PAD图，伪代码,计算机程序设计语言动态规划法的使用条件：最优化原理和无后效性。时间复杂度：是指执行算法所需要的计算工作量。空间复杂度：算法在执行

2、过程中所占辅助存储空间的大小，用s(n)表/JOP类问题：存在多项式时间的算法的i类问题NP问题：可以在多项式时间内验证一个解是否正确的问题常用的存储结构：连续存储和链式存储两种存储的优缺点比较：1、基于存储的考虑顺序表的存储空间是静态分配的，在程序执行之前在程序执行之前必须明确规定它的存储模式，也就是说事先对“MAXSIZE—要有合适的规定，过大造成浪费，过小造成溢出。可见对线性表的长度或存储规模难以估计时，不益采用顺序；链表不用事先估计存储规模，但链表的存储密度较低，存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元Z比。显然链式存储的存储密度是小

3、于1的。2、基于运算的考虑在顺序表屮按序号访问a的时间性能0（1）时，而链表屮按序号访问的时间性能O（n）,所以如果经常做的运算是按序号访问数据元索,显然顺序表优于链表；而在顺序表中做插入、删除时平均移动表中的一半元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的；在链表中作插入、删除，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然是后者优于前者。3、基于环境的考虑顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，和对来讲前者简单些，也是用户考虑的一个因素。总之，通常较稳定的线性表选择顺序存储，而频繁作插入、删除的即动态性较强的线性

4、表宜选择链式存储。枚举法枚举法是蛮力策略的一种表现形式，也是一种使用非常普遍的思维方式。它是根据问题中的条件将可能的情况一一列举出來，逐一尝试从中找出满足问题条件的解。分治法的思想将整个问题分解成若干个小问题后分而治之，主要有3个步骤：1、分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；2、解决：若子问题规模较小而容易被解决则直接解决，否则再继续分解为更小的子问题，直到容易解决；3、合并：将已解决的各个了问题的解，逐步合并为原问题的解。贪婪法贪焚法又叫登山法，它的根本思想是逐步到达山顶，即逐步获得最优解，是解决最优化问题时的一种简单但适用范围有限的

5、策略。分支界限法把问颗的可行解屣开如树的分枝，冇经由各个分枝中寻栈最佯解c分枝界限法也能够仲甲在混合整数珈划问顾h,其汨一•种系统化的解法，以一般线件规划之单形法解得最住解后，将非整数侑步决策变量分割成为最接圻的两个整数，分列条件，加入原间星页中，形成两个子问颍（或分枝）分别求解，如业伸可求得目标函数值的上限（上界）或下限（下界），从其中寻得最佳解。动态规划的基本思想把求解的问题分成许多阶段或多个子问题，然后按顺序求解各个了问题。前一了问题的解，为后一了问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其它局

6、部解。依次解决各个子问题，最后一个子问题就是初始问题的解。回溯法基本思想冋溯法是在包含问题的所有解的解空间树中。按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否满足问题的约束条件。如果满足进入孩子树，继续按深度优先的策略进行搜索。否则，不去搜索以该结点为根的子树，而是逐层向其祖先结点回溯。其实回溯法就是对隐式图的深度优先搜索算法。图搜索搜索分为两种：不考虑给定问题的特有性质，按图形特点事先定好的顺序，一次运用规则，即盲目搜索（穷举搜索）；另一种则考虑问题给定的特有性质，选用合适的规则，提高搜索的效率，即启发式搜索。耒语树中

7、的每一个结点确定所求解问题的一个问题状态。由根结点到其他结点确定所有路径，就确定了这个问题的状态空间。解状态是这样一些问题状态S,对于这些问题状态，由根到S的那条路径确定了该解空间中的一个元组。答案状态是这样的一些解状态S,对于这些解状态而言，由根到S的这条路径确定了该问题的一个解。解空间的树结构称为状态空间树。搜索状态空间树一般都是从根结点开始然后生成其它结点，如果己生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。当前止在生成其儿子结点的活结点叫做E・结点。不再进一步扩展或者其儿子结点已全部生成的生成结点