算法分析和设计总结

《算法分析和设计总结》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第一章算法概述1•算法：解决问题的一种方法或过程；由若干条指令组成的有穷指令。2.算法的性质：1)输入：有零个或多个输入2)输出：有至少一个输出3)确定性：每条指令是清晰的、无歧义的4)有限性：每条指令的执行次数和时间都是有限的3.算法与程序的区别>程序是算法用某种程序设计语言的具体实现>程序可以不满足算法的有限性4.算法复杂性分析1)算法的复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要空I'可资源的量称为空问复杂性2)三种时间复杂性：最坏情况、最好情况、平均情况3)可操作性最好且最有实际价值的是最坏情况下的时间复杂性第二章递归与

2、分支策略1.递归概念：直接或间接调用自身的算法2.递归函数：用函数自身给出定义的函数3.递归要素：边界条件、递归方程4.递归的应用◊汉诺塔问题voidHanuo(intn,inta,intb,intc){if(n~l)return;Hanuo(n-1,a,c,b);move(a,b)Hanuo(n~l,c,b,a);}◊全排列问题voidPerm(Typelist[],intk,intm){//产生list[k,m]的所有排列if(k==m){for(inti=0;I<=m;i++)cout«list[i];cout«endl;}else{for(inti=j

3、;i"m;i++)Swap(list[k],list[i]);Perm(list,k+1;m);Swap(list[k],list[i])5.分治法的基本思想：将一个规模较大的问题分成若干个规模较小的子问题，这些子问题互相独立且与原问题相同。1.分治法的使用条件：/问题的规模缩小到一定程度可以容易地解决/问题可以分解为若干个规模较小的相同问题/利用原问题分解出的子问题的解可以合并为原问题的解“各个子问题是相互独立的2.分治法的吋间复杂度&分治法的应用I二分搜索1）时间复杂度O（logn）2）参考算法丄快速排序1）快排的运行吋I'可与划分是否对称有关2）时间复杂

4、度O（nlogn）丄合并排序1）基本思想：将待排元素分成大小大致相同的两个子集合，分别对两个子集合进行排序，最总将排序好的子集合合并成所要求的排序好的集合。2）吋I'可复杂度0（nlogn）4棋盘覆盖I大整数乘法IStrassen矩阵乘法第三章动态规划1.基本思想：将待求解问题分解成若干个子问题，先求解子问题，再从这些子问题的解得到原问题的解。2.动态规划与分治法的区别：与分治法不同，适合于动态规划求解的问题，经分解得到的子问题往往是不独立的。3.动态规划算法求解步骤1）找出最优解性质，并刻画其结构特征2）递归地定义最优值3）自底向上求最优值4）构造最优解4.

5、基本要素：>最优子结构性质：问题的最优解包含子问题的最优解>子问题重卷性质：在递归法自顶向下求解问题时，每次产生的子问题并不总是新的问题，有些子问题被反复计算多次。5.动态规划、递归、备忘录的区别◊备忘录的递归方式是自顶向下的，动态规划的递归方式是自底向上的◊备忘录与直接递归的控制结构相同，区别在于备忘录给子问题的解建立了备忘录,以备查看。6.算法应用I矩阵连乘I最大字段和丄最大公共子序列丄0-1背包第四章贪心算法1.基本思想：总是做出当前看来最好的选择即使贪心算法不能得到整体最优解，但最终结果却是最优解的很好的近似解2.基本要素贪心选择性质所求问题的整体最优

6、解可以通过一系列局部最优解的选择即贪心选择来达到。◊最优子结构性质一个问题的最优解包括子问题的最优解。3.分治、贪心和动态规划>动态规划以自底向上的方式求解，贪心选择以自顶向下方式求解>贪心和动态规划都有最优子结构性质>背包问题可以用贪心算法，而0-1背包问题不能用贪心算法求解分治动态规划贪心算法适用类型通用问题优化问题优化问题子问题结构每个子问题不同很多子问题重复（不独立）只有一个子问题最优子结构不需要必须满足必须满足子问题数全部子问题都要解决全部子问题都要解决只要解决一个子问题子问题在最优解里全部部分部分选择与求解次序先选择后解决子问题先解决子问题后选择先

7、选择后解决子问题4.算法应用£活动安排问题结束吋间早的优先4背包问题为什么0-1背包用贪心算法不能求得最优解？主要原因在于无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空I'可的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。丄最优装载问题丄哈夫曼编码问题计算平均码长丄单源最短路径问题4最小生成树问题Prim和Kruskal算法£多机调度问题第五章回溯法1.基本思想：以深度优先方式系统搜索问题解的算法2.解题

8、步骤：1）针对所给问题，定义问题解空间