算法和复杂度.ppt
《算法和复杂度.ppt》由会员分享,可在线阅读,更多相关《算法和复杂度.ppt(24页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、算法和复杂度 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望算法:是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。一个算法通常具有五个重要特性:有穷性 有限步结束 确定性 唯一执行路径(无歧义)可行性 可以通过基本运算实现(理论上能够由人用纸和笔完成)输入 零个或多个输入 输出 一个或多个输出Al Khwarizmi(阿勒.霍瓦里松)首次提出算法概念,十分强调求解问题有条理的步骤。这是算法亘古不变的核心。1.3.1 算 法 的
2、 概 念2算法和复杂度算法和数据结构是两个不可分割的统一体程序=数据结构+算法数据结构通过算法实现操作算法根据数据结构设计程序注意:不要把算法和计算机程序等同起来,后者只是描述前者的手段之一,我们还可以用流程图、形式语言与自动机甚至自然语言描述一个算法。3算法和复杂度算法设计的要求:正确性 正确反映需求(通过测试)可读性 有助于理解、调试和维护 健壮性 完备的异常和出错处理 高效率与低存储的需求 时间、空间的要求4算法和复杂度1.3.2 算 法 设 计算法设计与分析算法设计与分析是计算机科学的核心问题。常用的算法设计方法有:穷举法穷举法将问题空间中的所有求解对象一一列举出来,逐一将问题空间中的
3、所有求解对象一一列举出来,逐一分析、处理,并验证结果是否满足给定的条件。分析、处理,并验证结果是否满足给定的条件。(例:(例:C+switch语句)语句)回溯法回溯法将问题的候选解按某种顺序逐一枚举和检验,来寻将问题的候选解按某种顺序逐一枚举和检验,来寻找一个满足预定条件的解。当发现当前候选解不可找一个满足预定条件的解。当发现当前候选解不可能是解时,就退回到上一步重新选择下一个候选解能是解时,就退回到上一步重新选择下一个候选解(回溯)。(例:八皇后、迷宫、深度优先搜索(回溯)。(例:八皇后、迷宫、深度优先搜索)5算法和复杂度分治法和递归法分治法和递归法遇到一个难以直接解决的大问题时,将其分割成
4、一些规模较小的子问题,以便遇到一个难以直接解决的大问题时,将其分割成一些规模较小的子问题,以便各个击破,分而治之,然后把各个子问题的解合并起来,得出整个问题的解。各个击破,分而治之,然后把各个子问题的解合并起来,得出整个问题的解。(例:快速排序、归并排序、二分检索等)(例:快速排序、归并排序、二分检索等)贪心法和动态规划法贪心法和动态规划法贪贪心心法法的的基基本本思思想想是是从从问问题题的的初初始始状状态态出出发发,依依据据某某种种贪贪心心标标准准,通通过过若若干干次次的的贪贪心心选选择择而而得得出出局局部部最最优优解解,寄寄希希望望于于局局部部的的最最优优解解构构建建最终的全局最优解。(最终
5、的全局最优解。(Prim和和Kruskal算法、算法、Dijkstra算法)算法)动动态态规规划划是是一一种种将将问问题题实实例例分分解解为为更更小小的的、相相似似的的子子问问题题,并并存存储储子子问问题题的的解解而而避避免免计计算算重重复复的的子子问问题题,以以解解决决最最优优化化问问题题的的算算法法策策略略。动态规划法和分治法相似?区别?(例:动态规划法和分治法相似?区别?(例:Floyd算法、矩阵连乘积)算法、矩阵连乘积)6算法和复杂度1.4 算法 分 析算法效率的衡量方法算法效率的衡量方法1事后统计利用计算机内记时功能。缺点:必须先运行依据算法编制的程序;所得时间统计量依赖于硬件、软件
6、等环境因素,掩盖算法本身的优劣7算法和复杂度1.4 算法 分 析算法效率的衡量方法算法效率的衡量方法2事前分析估计一个高级语言程序在计算机上运行所消耗的时间取决于:依据的算法选用何种策略问题的规模程序语言编译程序产生机器代码质量机器执行指令速度时间复杂度和空间复杂度8算法和复杂度算法的时间度量从算法中选取一种对于研究的问题来说是基本操作的原操作,以该基本操作重复执行的次数作为算法执行的时间度量。例,for (j=1;j=n;j+)X=X+1;for (i=1;i=n;i+)(c)for (i=1;i 时的时间复杂性,被称之为渐进时间复杂度。空间复杂度:算法的所需的空间和问题规模的函数。记为 S
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 复杂度
限制150内