计算机算法导论部分知识点_第1页
计算机算法导论部分知识点_第2页
计算机算法导论部分知识点_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

算法的概念 算法是解决问题的一种方法或者过程 算法是若干指令的有穷序列 包含以下 5 条性质 有 0 个或者多个输入 至少一个输出 有限性 确定性 可行性 算法复杂性 算法所需的计算机资源 算法复杂性是算法效率的度量 算法的时间复杂性和算法的空间复杂性 渐进上界 O 渐进下届 渐进下界 o 非近下界 w 渐进近界 分治法的设计思想 讲一个难以直接解决的大问题 分割成一些规模较小的相同问题 以 便各个击破之 分而治之 分治法所能解决的问题一般具以下几个特征 1 将问题的规模缩小到一定程度就可以容易地解决 2 该问题具有最优子结构性质 3 利用该问题分解出的子问题的解可以合并为该问题的解 4 子问题之间不包含公共的子问题 分治法的步骤 1 分解 将原问题分解为若干规模较小 相互独立 与原问题形式相同的子问题 2 解决 若子问题规模较小而容易被解决则直接解 否则递归的求解各个子问题 3 合并 将各个子问题合并为原问题的解 二分搜索技术 O logn 快速排序 O NLOGN 合并排序 O LOGN 2 动态规划算法的基本要素 1 最优子结构性质 2 重叠子问题性质 动态规划的基本步骤 1 找出最优解性质 并刻画其结构特征 2 递归地定义最优值 3 以自底向上的方式计算最优值 4 根据计算最优值时得到的信息 构造最优解 动态规划算法的基本思想 将待解决的问题分解成若干子问题 先求解子问题 然后从这些子问题的解得到原问题的 解 二分搜索算法是利用 动态规划算法 实现的算法 贪心算法的基本思想 1 最优子结构性质 2 贪心选择性质 贪心选择算法的步骤 1 从问题的某个初始解出发 2 采用循环结构 当可以向求解目标前进一步时 根据局部最优策略 得到一个部分解 缩小问题的范围或规模 3 将所有部分解综合起来 得到问题的最终解 贪心算法和动态规划算法的差别 相同点 具有最优子结构性质 不同点 贪心算法不能解决 0 1 背包问题 回溯法的基本思想 1 针对所给问题 定义该问题的解空间 2 确定易于搜索的解空间结构 3 以深度优先方式搜索解空间结构 并在搜索过程中用剪枝函数避免无效搜索 回溯法的搜索效率 1 产生 x k 的时间 2 满足显约数的 x k 值的个数 3 计算约束函数 constaint 的时间 4 计算上界函数 bound 的时间 5 满足约束函数和上界函数的所有 x k 的个数 最优子结构性质 某问题的最优解包含着其子问题的最优解 分支限界法的两种形式 队列式分支限界法 优先队列式分支限界法 分支限界法的基本思想 分支限
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论