数据与算法精品教学（陈健生）15 算法设计基础.pdfVIP

数据与算法 2014-2015年秋季学期 陈健生 jschenthu@tsinghua.edu.cn 清华大学电子工程系 1 Previously …  优化问题  凸优化  最速下降法  牛顿法 2 《 数 据 结 构 与 算法设计基础 算 法 》 1.4.3 2.4.3 分治 5.5.4 5.6.4 贪心 动态规划 3 • 蛮力法 • 递归与分治 • 贪心法 • 动态规划 4  蛮力法(brute-force)思想 ◦ 基于问题的定义描述，直接求解问题； 例：计算 ⋯ 蛮 总共1次乘法，更好的方法？ 力 ◦ 蛮力法一般采用遍历，依次处理每个元素； 法 ◦ 虽然蛮力算法通常效率不高，但也是一种重要的算 法设计技术：  理论上蛮力法可以解决可计算领域的各种问题；常用来解 决一些较小规模的问题。  对于一些重要的问题蛮力法可以产生一些合理的算法，具 备一定实用价值，且不受问题规模的限制；  可作为问题时间性能的底限来衡量更高效的算法. 5  例：顺序查找 ◦ 顺序查找从表的一端向另一端逐个将元素与给定值 进行比较，若相等，则查找成功，给出该元素在表 中的位置；若整个表检测完仍未找到与给定值相等 蛮 的元素，则查找失败，给出失败信息。 力 0 1 2 3 4 5 6 7 8 9 法 10 15 24 6 12 35 40 98 55 查找方向 i 平均比较次数 折半查找平均比较次数 6  例：模式串匹配 ◦ 将模式串T和主串S每个位置开始的子串都进行比 较；最坏比较次数 蛮 如 何 有 效 地 减 少 比 较 次 数 力 如 何 有 效 地 提 高 法