算法分析复习资料.ppt

1 算法的五个基本特征包括输入 输出 能行性和 2 算法分析时通常只考虑三种情况下的时间复杂性 实践表明可操作性最好且最有实用价值的是情况下的时间复杂性 3 将复杂问题按照某种方式分解成若干个规模较小 相互独立且与原问题类型相同的子问题进而求解的方法称为法 4 利用最优子结构 自底向上从子问题的最优解逐步构造出整个问题的最优解 这种算法称为法 5 动态规划算法的两个基本要素是和 6 在解决最优化问题的求解过程中 采用一种局部最优策略 把问题范围和规模缩小 最后把每一步的结果合并起来得到一个全局最优解 这种算法称为法 7 法在问题的解空间树中 按深度优先策略 从根结点出发搜索解空间树8 法在问题的解空间树中 按广度优先策略 从根结点出发搜索解空间树 1 请回答 什么是算法 算法应具有哪些重要特性 2 阐述算法与程序的联系与区别 3 影响一个程序运行时间的因素有哪些 4 简述贪心算法的思想策略 算法特点 以及它所具有的两种性质各是什么 5 简要说明贪心算法的两个基本要素 6 请说明回溯法和分支限界法的不同之处 7 设计一个动态规划算法 通常采用的步骤有哪些 渐近时间复杂度使用O o等记号表示的算法时间复杂度函数的数量级别 称为算法的渐近时间复杂度 2 2 1大O记号 定义2 1设函数f n 和g n 是定义在非负整数集合上的正函数 如果存在两个正常数c和n0 使得当n n0时 有f n cg n 则称当n充分大时 函数f n 上有界 且g n 是它的一个上界 也可以说f n 的阶不高于g n 的阶 记做f n O g n 称为大O记号 bigOhnotation 2 2 2 记号 定义2 2设有函数f n 和g n 是定义在非负整数集合上的正函数 如果存在两个正常数c和n0 使得当n n0时 有f n cg n 则称当n充分大时 函数f n 下有界 且g n 是它的一个下界 也可以说f n 的阶不低于g n 的阶 记做f n g n 称为 记号 omeganotation 2 2 3 记号 定义2 3设有函数f n 和g n 是定义在非负整数集合上的正函数 如果存在正常数c1 c2和n0 使得当n n0时 有c1g n f n c2g n 则记做f n g n 称为 记号 Thetanotation g n 代表一类函数 表示所有与g n 增长阶数相同的函数 如果一个算法的时间复杂度f n g n 说明当n足够大时 该算法的运行时间大约为g n 的某个常数倍 证明 1 f n 20n logn g n n log3n 确定函数f n 和g n 的渐进关系 用O 表示 2 f n n2 logn g n nlog2n 练习 1 求函数的渐进表达式 1 3n2 10n 2 n2 10 2n 3 21 1 n 4 logn3 5 10log3n 2 确定函数f n 和g n 的渐进关系 用O 表示 1 f n logn2 g n log n 5 2 f n logn2 g n n1 2 O 3 f n n g n log2n O 4 f n nlogn n g n logn 5 f n 10 g n log10 6 f n log2n g n logn 7 f n 2n g n 100n2 8 f n 2n g n 3n O 9 f n 20n logn g n n log3n O 贪心法 P1206 1 一 背包问题 n 5 m 11 p0 p4 8 6 15 6 3 w0 w5 2 3 5 2 3 最优量度标准 优先选择单位重量收益最大的物品放入背包 p0 w0 p1 w1 p2 w2 p3 w3 p4 w4 4 2 3 3 1 最优解为 x0 x1 x2 x3 x4 x5 x6 1 2 3 1 1 0 最大收益为 8 6 2 3 15 6 33 D 0 0 S 0 1扩展0 1 2 3 D 1 2 S 1 0 D 2 8 S 2 0 D 3 5 S 3 0扩展1 2 3 4 D 2 min 8 2 3 5 S 2 1 D 4 5 S 4 1扩展2 3 4 5 D 5 D 2 4 9 S 5 2扩展3 4 5 D 5 min 9 D 3 6 9 S 5 2 D 6 D 3 9 14 S 6 3扩展4 5 D 5 min 9 D 4 5 9 S 5 2 D 6 min 14 D 4 7 12 S 6 4扩展5 D 6 min 12 D 5 2 11 S 6 5最短路径为 0 1 2 5 6最短路径长度为11 分枝限界法 动态规划法 P1597 5 设4个矩阵连乘积A0A1A2A3 设它们的维数分别为A0 20 10A1 10 8 A2 8 5 A3 5 40 矩阵连乘AiAi 1 Aj简记为A i j m i j 表示AiAi 1 Aj最少计算量 s i j 表示AiAi 1 Aj最少计算量的断开点 采用动态规划法确定矩阵连乘积的最优计算次序 要求写出计算最优解的递推关系式 递推运算过程和完全加括号的矩阵运算表达式 1 递推关系式 2 p0 20 p1 10 p2 8 p3 5 p4 40 m i i 0 s i i i i 0 1 2 3 m 0 1 min m 0 0 m 1 1 20 10 8 1600 s 0 1 0 m 1 2 min m 1 1 m 2 2 10 8 5 400 s 1 2 1 m 2 3 min m 2 2 m 3 3 8 5 40 1600 s 2 3 2 2 p0 20 p1 10 p2 8 p3 5 p4 40 m 0 2 min m 0 0 m 1 2 20 10 5 m 0 1 m 2 2 20 8 5 min 400 1000 1600 800 1400 s 0 2 0 m 1 3 min m 1 1 m 2 3 10 8 40 m 1 2 m 3 3 10 5 40 min 1600 3200 400 2000 2400 s 1 3 2 m 0 3 min m 0 0 m 1 3 20 10 40