算法分析习题课PPT课件.ppt

练习题 令A 1 n 是一个包含n个整数的已排序数组 非降序 给定一个整数x 设计一个时间复杂度为O n 的算法 来确定A中是否存在这样两个整数 它们的和恰好等于x a a xa xa x 1 输入 已经排序 非降序 的整型数组A 1 n 整数x输出 若A中存在两个整数的和恰好为x 返回true 否则返回false1 returnsumX 1 n Procedure sumX s t 1 ifs tors t2 3 elseifA s A t x4 5 elseifA s A t x6 7 else8 2 输入 已经排序 非降序 的整型数组A 1 n 整数x输出 若A中存在两个整数的和恰好为 返回true 否则返回false1 returnsumX 1 n Procedure sumX s t 1 ifs tors t2 returnfalse 3 elseifA s A t x4 returntrue 5 elseifA s A t x6 returnsumX s t 1 7 else8 returnsumX s 1 t 3 时间复杂度分析 注意 默认A 1 n 是非降序 如果是非升序 上述算法还对么 如果不对 该怎么修改 4 排列问题 已知集合R r1 r2 rn 且集合中没有相同的元素 请设计一个算法生成集合R中n个元素的全排列 解 我们记集合X中元素的全排列记为perm X 那么 a perm X 表示在全排列perm X 的每一种排列前加上前缀a所得到的排列 记Rj R rj 所以 R的全排列可归纳定义如下 当n 1时 perm R r 其中r是集合R中唯一的元素 当n 1时 perm R 由 r1 perm R1 r2 perm R2 rn perm Rn 构成 5 k m 6 算法的一个Java实现如下 publicclassPerm publicstaticvoidperm Object a intk intm if k m for inti 0 i a length i System out print a i System out println else for inti k i m i swap a k i perm a k 1 m swap a k i publicstaticvoidmain String args Integer a newInteger 6 for inti 0 i a length i a i newInteger i perm a 0 5 publicstaticvoidswap Object a inti intj Objecttemp a i a i a j a j temp 7 整数划分问题 将正整数K表示为p个整数的和 K k1 k2 kp 其中 k1 k2 kp 正整数K的这种表示叫做正整数划分 partition 正整数K的不同的划分的个数叫做的划分数 记做p K 比如对于6 可以进行如下不同的划分 6 最大加数为65 1 最大加数为54 2 4 1 1 最大加数为43 3 3 2 1 3 1 1 1 最大加数为32 2 2 2 2 1 1 2 1 1 1 1 最大加数为21 1 1 1 1 1 1 最大加数为1因此 p K 11 也就是说 6的划分数是11 请设计一个分治算法 对于一个给定的整数 输入 求出该整数的划分数 输出 8 分析 在正整数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 K k1 k2 kp 其中 k1 k2 kp 比如对于6 可以进行如下不同的划分 6 最大加数为65 1 最大加数为54 2 4 1 1 最大加数为43 3 3 2 1 3 1 1 1 最大加数为32 2 2 2 2 1 1 2 1 1 1 1 最大加数为21 1 1 1 1 1 1 最大加数为1 9 6 最大加数为65 1 最大加数为54 2 4 1 1 最大加数为43 3 3 2 1 3 1 1 1 最大加数为3m2 2 2 2 2 1 1 2 1 1 1 1 最大加数为21 1 1 1 1 1 1 最大加数为1 10 那么 可以按照如下关系来建立p K m 的递归关系式 1 当m 1时 最大加数不大于1的时候 p K 1 1只有1种划分形式 也即1 1 1 1 2 当m K时 等价于m K 即p K m p K K 3 当m K的时候 正整数K的划分数 最大加数为K的划分数 1 最大加数不大于K 1的划分数 p K K 1 4 当K m 1的时候 正整数K的最大加数不大于m的划分数 最大加数为m的划分数 最大加数不大于m 1的划分数 p K m 1 p K m m 11 子问题重复 直接上述递归 性能不高 怎么办 12 动态规划 123456 1 2 3 4 5 6 m K p K m p K K 111111 1 1 1 1 1 P K m 1 p K K 1 当m KP K m p K m m P K m 1 当K m 1 13 14 动态规划 编辑距离 设A和B是2个字符串 要用最少的字符操作将字符串A转换为字符串B 字符串操作包括 1 删除一个字符 2 插入一个字符 3 将一个字符改为另一个字符 将字符串A变换为字符串B所用的最少操作次数称为字符串A到B的编辑距离 记为d A B 请设计一个有效算法 对于给定的任意两个字符串A和B 计算其编辑距离d A B 15 分析 假设A a1a2 an的长度为n B b1b2 bm的长度为m 如果d i j 表示a1a2 ai和b1b2 bj之间的编辑距离 16 17 集合划分问题 给定一个集合X 且集合中元素互不相同 集合P由X的子集构成 若P中的元素满足以下性质 1 P中的任一元素不是空集 2 P中的元素的并集等于X 3 P中的任何两个元素的交集为空 那么称P是X的一个划分 以集合X 1 2 3 4 为例 P 1 2 3 4 不是X的划分 因为存在空集P 1 2 3 不是X的划分 因为子集的并不是原集合P 1 2 3 2 4 也不是X的划分 因为两子集的交集不是空集P 1 2 3 4 符合上述三点 是X的一个划分P 1 2 3 4 符合上述三点 是X的一个划分P 1 2 3 4 符合上述三点 是X的一个划分 18 设计一个算法 求一个包含n个元素的集合 一共有多少种划分 用F i j 表示一个包含前i个元素的集合 划分为j个子集所具有的划分数 那么原问题的解 F n 1 F n 2 F n n 下面关键的问题 是怎么求F i j 1 2 3 i 1 i 19 F i j j F i 1 j F i 1 j 1 1 2 3 i 1 i 划分为j个子集 选一个子集放入 可以有j种选择 1 2 3 i 1 i 划分为j 1个子集 20 连续子序列的最大和 给定一个连续的整数序列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 其和A 2 A 3 A 4 A 5 78 实际上 在A的所有连续子序列中 连续子序列A 2 A 3 A 4 A 5 的和是最大的 21 解决方法 用b j 表示A 1 A 2 A j 的所有包含A j