计算机算法设计与分析期末考试复习题.doc

根据提供的文档信息，我们可以归纳和展开以下几个重要的知识点： ### 一、算法设计的基本策略 1. **二分搜索算法**：二分搜索算法是一种典型的**分治策略**的应用，通过不断将查找区间减半的方式缩小查找范围，直到找到目标值或者确定目标值不存在于查找区间内为止。该算法的时间复杂度为O(log n)，适用于有序数组。 2. **动态规划算法**：动态规划算法是一种解决多阶段决策问题的有效方法。它通过将问题分解为多个子问题，并存储已解决子问题的答案以避免重复计算来提高效率。动态规划的核心是**最优子结构**和**重叠子问题**两个性质。选项A中的“找出最优解的性质”并非动态规划的基本步骤之一，而是该方法的一个前提条件。 3. **最大效益优先**：这是一种用于优化问题的搜索策略，常被用于**分支界限法**中。这种方法倾向于优先探索看起来最有可能产生较好解的空间。 4. **拉斯维加斯算法**：这类算法的结果是确定性的，但运行时间是随机的。也就是说，在某些情况下，这种算法可能无法在有限时间内找到问题的解。 5. **回溯法**：回溯法是一种基于试错的思想来寻找所有（或某个）解的算法。在解空间树上按广度优先策略或深度优先策略，从根节点出发搜索解空间树。旅行售货员问题是经典的NP完全问题，可通过回溯法求解。 ### 二、算法评估标准 - **时间复杂度**：衡量算法好坏的一个关键标准是其时间复杂度，即执行算法所需时间随着输入规模增长的变化情况。时间复杂度低意味着算法更高效。 ### 三、具体算法案例 1. **循环赛日程表**：可以通过**分治策略**来实现，即将问题分解为较小的子问题，然后递归地解决这些子问题。 2. **哈夫曼编码**：哈夫曼编码是一种基于贪心法的编码方式，它通过构造一棵特殊的二叉树来实现最优编码。哈夫曼编码广泛应用于数据压缩领域。 3. **矩阵连乘问题**：可以采用**动态规划算法**来设计实现，通过记录子问题的最优解来避免重复计算，从而达到优化目的。 4. **最长公共子序列问题**：这是一个经典的动态规划问题，其核心在于构建一个表示两个序列之间最长公共子序列长度的二维数组，并通过填充该数组来找到最终的解。 5. **Strassen 矩阵乘法**：这是一种快速矩阵乘法算法，利用了分治策略来减少乘法操作的次数，从而降低了算法的时间复杂度。 6. **分支限界法**：这是一种搜索算法，它通过维护一个活结点表来控制搜索过程。最大团问题的解可以通过使用最大堆作为活结点表的组织形式来实现。 7. **备忘录方法**：这是动态规划算法的一种变形，通过存储已解决的子问题结果来避免重复计算。 8. **贪心算法与动态规划算法的比较**：两者都可用于解决最优解问题，但贪心算法依赖于局部最优解能够导致全局最优解这一特性，而动态规划算法则基于子问题的最优性。贪心算法通常比动态规划算法更简单且更快，但在很多情况下无法保证得到最优解。 9. **NP 问题**：NP问题是指能在多项式时间内验证解的问题集合，而P类问题是指能在多项式时间内解决的问题集合。P类问题确实包含在NP类问题中，这也是NP问题的一个重要特性。 10. **概率算法**：蒙特卡罗算法和拉斯维加斯算法都是概率算法的不同变体。其中，拉斯维加斯算法的特点是在有限时间内可能成功也可能失败，但当算法成功时，其结果一定是正确的。 以上这些知识点覆盖了计算机算法设计与分析中的多个核心概念和技术，对于理解算法原理及其应用至关重要。