算法分析习题课.ppt

练习题 令A[1…n]是一个包含n个整数的已排序数组(非降序)。给定一个整数x。设计一个时间复杂度为O(n)的算法,来确定A中是否存在这样两个整数，它们的和恰好等于x. 输入：已经排序(非降序)的整型数组A[1…n]，整数x 输出：若A中存在两个整数的和恰好为x，返回true; 否则返回false 1. return sumX(1,n) Procedure：sumX(s,t) 1. if s = t or s t 2. ; 3. else if A[s] + A[t] = x 4. ; 5. else if A[s] + A[t] x 6. ; 7. else 8. ; 输入：已经排序(非降序)的整型数组A[1…n]，整数x 输出：若A中存在两个整数的和恰好为，返回true; 否则返回false 1. return sumX(1,n) Procedure：sumX(s,t) 1. if s = t or s t 2. return false; 3. else if A[s] + A[t] = x 4. return true; 5. else if A[s] + A[t] x 6. return sumX(s,t-1); 7. else 8. return sumX(s+1,t); 时间复杂度分析 排列问题 算法的一个Java实现如下: 分析 在正整数K的所有划分中，将最大加数(k1)不大于(小于等于)m的划分数记做p(K,m) 那么当m=K时，就是问题的解。 例如p(6,1) =1; p(6,2)=4; p(6,3)=7; p(6,4)=9; p(6,5)=10; p(6,6) =11 动态规划 动态规划-编辑距离 设 A 和 B 是 2 个字符串。要用最少的字符操作将 字符串 A 转换为字符串 B 。字符串操作包括： (1) 删除一个字符； (2) 插入一个字符； (3) 将一个字符改为另一个字符。 将字符串 A 变换为字符串 B 所用的最少操作次数称为字符串 A 到 B 的编辑距离，记为 d (A,B) 。 请设计一个有效算法， 对于给定的任意两个字符串 A 和 B ，计算其编辑距离 d (A,B) 。 分析 假设A=a1a2….an的长度为n, B=b1b2….bm的长度为m。 如果d[i,j]表示a1a2….ai和b1b2….bj 之间的编辑距离。 集合划分问题 给定一个集合X，且集合中元素互不相同。集合P由X的子集构成。若P中的元素满足以下性质： 1. P 中的任一元素不是空集。 2. P 中的元素的并集等于 X。 3. P 中的任何两个元素的交集为空。 那么称P是X的一个划分。 设计一个算法，求一个包含n个元素的集合，一共有多少种划分？ 连续子序列的最大和 给定一个连续的整数序列A[1],A[2],A[3],……….,A[n]。计算它的连续序列和的最大值。 例如：?? 整数数组 A={-4 , 3 ,56 , -15 , 34 , 0 , -14 , 4} ; 连续序列： A[1]A[2]，其和 A[1]+A[2] = -1 。 …… 连续序列： A[2]A[3]A[4]A[5] ，其和