《算法设计与分析》复习题(总9页).doc

填空1直接或间接地调用自身的算法称为 递归 。2算法的复杂性是 算法效率 的度量，是评价算法优劣的重要依据。3以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。4回溯法解题的显著特点是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为 o(h(n) 。5人们通常将问题的解决方案分为两大类：一类是可以通过执行若干个步骤就能得出问题结论的，叫做 算法方案 方案；另一类是不能通过若干个步骤直截了当地得出结论，而是需要反复验证才能解决的，叫做 启发式方案 方案。6算法就是一组有穷的 规则 ，它们规定了解决某一特定类型问题的 一系列运算 。7在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3个基本计算模型是 随机存取机、 随机存取存储程序机 、 图灵机 。8快速排序算法的性能取决于 划分的对称性