《算法分析与设计》讲义（郭彦宏）

算法分析与设计 兴八 郭彦宏 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 图的最短路径 – 地理研究中的交通网络

算法业计与分祈 例1.1 ◆A[1.101={1,3,56,7,10,2,273456} ◆在A中搜索x=22 算法设计与分析

算法设计与分析 6 w A[1…10]={1,3,5,6,7,10,22,27,34,56} w 在A中搜索x＝22 例1.1

算法计与分祈 算法1.1 ◆/ Linearsearch j←1 ◆ While(j<n)and(X≠A[j ◆1←j+1 ◆ End while -Ifx=AlI then return j else return 0 算法设计与分析

算法设计与分析 7 算法1.1 w Linearsearch w j←1 w While（j<n) and (x≠A[ j]) w j ← j+1 w End while w If x=A[j] then return j else return 0

算法业计与分析 例1.2 template int Max(t al, int n) W寻找a[0:n-1中的最大无素 Int pos=0, fr(inti=1;i<n;计+) 八( alpos]< a[ POs =I, return pos 算法设计与分析

算法设计与分析 8 例1.2 template int Max(T a[], int n) {// 寻找a [ 0 : n - 1 ]中的最大元素 int pos = 0; for (int i = 1; i < n; i++) if (a[pos] < a[i]) pos = i; return pos; }

算法业计与分祈 二分搜索 算法12) inarysearch 0 W<l, high←n←0 while(lowshigh)and(=g mdL( thigh)/2」 ifx=A[mid] then J←mid else if X<A[mid] then high +-mid-4 else low←mid+1 end while return 算法设计与

算法设计与分析 9 w 算法1.2 binarysearch w low ←1;high ←n;j ←0 w while (low≤high) and (j=0) w mid ← (low+high)/2 w if x=A[mid] then j ←mid w else if x<A[mid] then high ←mid-1 w else low ←mid+1 w end while w return j 二分搜索

算法业计与分析 23 15 32 12 22 35 ◆Logn+1 10 算法设计与分析

算法设计与分析 10 1 10 27 4 5 7 22 8 9 15 23 12 32 35 w Logn +1