算法补充资料20120903.ppt

算法补充资料 * 算法 对特定问题求解过程的描述，是指令的有限序列，也即，为解决某一特定问题而采取的具体有限的操作步骤。 程序是算法的一种实现，计算机按照程序逐步执行算法，实现对问题的求解。 算法 用计算装置能够理解的语言描述的解题过程，具有如下性质： 将它作用于所求解的问题的给定输入集上，或作用于问题自身的描述上，将产生唯一确定的动作序列，此序列是有限的； 此序列或终止于给出问题的解，或终止于指出问题对此输入无解 有穷性；确定性； 可行性； 输入； 输出 算法的特性 通用性 对于符合输入类型的任意输入数据，都能根据算法进行问题求解，并保证计算结果的正确性 有效性 组成算法的每一条指令都必须是能够被（人或机器）确切执行的，且指令的类型应该明确规定，其结果应具有确定的数据类型，是能够预期的 确定性 保证每一步之后都有关于下一步动作的指令，不能缺乏下一步指令（被锁住）或仅仅含有模糊不清的指令 有穷性 算法的执行必须在有限步内结束。换句话说，算法不能含有死循环 算法分类 算法设计与算法分析是计算机科学的核心问题 常用的设计方法 穷举法　(百钱买百鸡) 贪心法　(Huffman树、Prim等) 递归法, 分治法(二分检索、快速排序等) 回溯法(树、图等的深度优先有哪些信誉好的足球投注网站） 动态规划法(最佳二叉排序树) α-β裁剪和分枝界限法 并行算法 * 计算复杂性和算法的效率 根据计算理论，存在着一类问题虽然能够被准确定义，但却不存在能够解决该问题的算法。称为不可解问题 计算复杂性理论指出，理论上存在一大类难解问题，它们虽然存在着求解算法，但在算法的计算时间上，都是组合爆炸型的求解算法 随着问题的规模 n 的增大，算法的时间开销不能约束在 n 的 k 阶多项式数量范围内。（其中 k是任意不依赖于 n 的常数） 比较常见的难解问题有：图论中的求最优巡游路径问题，判定命题逻辑公式是否为恒真等 算法的执行效率及其度量 解决同一个问题存在多种算法，如何评估各算法的好坏？或据此设计出更好的算法？ 运行该算法所需要的计算机资源的多寡，所需越大复杂性越高 最重要的资源：时间（处理器）和空间（存储器） 评价一个算法优劣的重要依据是看执行该算法的程序需要占用多少机器资源： 程序所用算法运行时所要花费的时间代价 程序中使用的数据结构占有的空间代价 算法的执行效率及其度量 需要明确： 如何表达一个算法的复杂性 怎样计算一个算法的复杂性 算法时间复杂性 不能用诸如微秒、纳秒这样的真实时间单位 一个运行在Cray机上的算法若放在PC机会慢很多 一个运行在Cray机上的效率极差的算法也许比一个运行在PC上的效率很高的算法花费更少的时间 同样的算法运行在同样的机器上也会因使用不同的程序语言而存在差异 C vs LISP 两个不同的算法也许在输入规模为100时表现不相上下，而在输入规模扩大10倍后却表现迥异 算法复杂性分析 算法分析感兴趣的不是具体的资源占用量，而是与具体的平台无关、具体的输入实例无关，且随输入规模增长的值是可预测的 与问题的规模之间的关系，用一定“规模(size)”的数据作为输入时程序运行所需的“基本操作(basic operation) ” 数来描述时间效率。 完成一个“基本操作”所需的时间应该与具体的被操作的数无关 算法的渐进分析 asymptotic analysis，简称算法分析 由于算法的复杂性与其所求解的问题规模直接有关，因此通常将问题规模 n 作为一个参照量，求算法的时空开销和 n 的关系 一般这种函数关系都相当复杂，计算时只考虑可以显著影响函数量级的部分，即结果为原函数的一个近似值 对资源开销的一种不精确估计，提供对于算法资源开销进行评估的简单化模型 算法的渐进分析 算法的渐进分析就是要估计，当数据规模 n逐步增大时，资源开销f(n)的增长趋势 得到如此精确的一个界相对比较费时费力，且没有必要 从数量级大小的比较来考虑，当n增大到一定值以后，资源开销的计算公式中影响最大的就是n的幂次最高的项，其他的常数项和低幂次项都是可以忽略的 算法渐进分析：大Ｏ表式法 假设f 和g为从自然数到非负实数集的两个函数 　定义1：如果存在正数c和N，使得对任意的n?N，都有 f(n) ? cg(n)， 则称f(n)在集合O(g(n))中，或简称f(n)是O(g(n))的 说明了函数 f 和 g 关系：函数g(n) 是函数 f(n) 取值的上限（upper bound），或说函数f的增长最终至多趋同于g的增长 大O表示法提供了一种表达函数增长率上限的方法 一个函数增长率的上限可能不止一个。大O表示法给出了所有上限中最“紧”（也即最小）的那个上限 * 大Ｏ表式法的性质 若符号a是不依赖于n的任意常数 如果函数 f(n) 是O(g(n)