算法分析与设计 兴八 郭彦宏 2005年改 和数据
算法和数据结构 1 郭彦宏 2005年改
算法计与分析 程序=算法+数据结构 ◆软件:刻画现实世界,解决现实世界中 的问题 ◆语言:实现的工具 ◆算法:解的描述(程序的灵魂) 人·数据结构:现实世界的数据模型 ◆程序=算法+数据结构 2 算法设计与分析
算法设计与分析 2 程序=算法+数据结构 w 软件：刻画现实世界，解决现实世界中 的问题 w 语言：实现的工具 w 算法：解的描述（程序的灵魂） w 数据结构：现实世界的数据模型 w 程序=算法+数据结构
算法业计与分祈 算法 ◆定义 为了完成特定任务指令的有穷序列 好的算法的特性 确定性 有穷性 可行性 健壮性 输入、效率和存储要求 输出 算法设计与分析
算法设计与分析 3 算法 w 定义 – 为了完成特定任务指令的有穷序列 w 好的算法的特性 – 确定性 – 有穷性 – 可行性 – 健壮性 – 输入、效率和存储要求 – 输出
算法计与分析 算法的复杂度与评价 时间与空间 方法 1、事后分析 2、事前分析 算法设计与分析
算法设计与分析 4 算法的复杂度与评价 w 时间与空间 w 方法: 1、事后分析 2、事前分析
算法业计与分祈 几个例子(问题) ◆表达式解释 6+5*4=? ◆字符串匹配 串“ ABAC出现在另一个串“ ABCABCACAC的第几个位 置上 ◆排序 个序列,如何最快地对其进行排序 ◆压缩编码 AAAABBBCDDE→? ◆图的最短路径 地理研究中的交通网络 算法设计与分析
算法设计与分析 5 几个例子（问题） w 表达式解释 – 6+5*4=？ w 字符串匹配 – 串“ABCAC”出现在另一个串“ABCABCACAC”的第几个位 置上 w 排序 – 一个序列，如何最快地对其进行排序 w 压缩编码 – AAAABBBCDDE? w 图的最短路径 – 地理研究中的交通网络