算法设计与分析

算法设计与分析的思维导图，如算法设计的考试提醒： 在思路描述上要抓住要点，可以分步骤阐述，可以结合实例说明过程，不能过于简单； 相关变量和数据结构描述清楚； 可以直接调用库函数； 伪代码一般以函数的形式出现，加入必要的注释； 看清题目要求，不要漏题。

算法设计与分析

• 算法评价
  • 算法的五个特征
    • 确定性
    • 可行性
    • 有穷性
    • 有0个或1个以上的输入
    • 有1个以上的输出
  • 算法分析的五个准则
    • 正确性
    • 简单性
    • 最优性
    • 时间复杂度
    • 空间复杂度
  • 算法的定义
    • 算法是一个有穷规则序列
  • 时间复杂度的分析方法
    • 非递归算法的分析方法
      • 统计算法执行的基本操作次数（计数法）
        • 平均时间复杂度
          • 确定基本操作
          • 分析有多少种输入并确定每种(类)输入出现的概率
          • 分析每种输入执行的基本操作次数
          • 按相关公式建立关于n的表达式
          • 化简函数，得到相对简单的结果
          • 用渐近符号表示(得到最高阶项，忽略系数和低阶项）
        • 最坏时间复杂度
          • 确定基本操作
          • 分析输入的最坏情况
          • 计算最坏情况输入下执行基本操作的次数
          • 化简函数
          • 用渐近符号表示(得到最高阶项，忽略系数和低阶项）
    • 递归算法的分析方法
      • 建立递推方程
      • 求解递推方程
        • 迭代法
          • 直接迭代
          • 换元迭代
          • 差消迭代
        • 递归树
          • 首先将递推方程的表达式分为递归项和自由项，递归项需要进一步递归求解，自由项是关于n的某种函数表达式或常数项
          • 将初始方程的自由项作为根节点，递归项作为叶子结点建树
          • 用当前叶子结点对应的方程表达式构成的子树替换叶子结点，直到树中所有结点都由自由项构成
          • 将每个结点的自由项相加，得到最终结果
        • 主定理
  • NP完全理论
    • 3个基本计算模型
      • 随机存取机RAM
      • 随机存取存储程序机RASP
      • 图灵机TM
    • 可计算问题（易解问题）
      • 在多项式时间内可解决的问题
    • 不可计算问题（难解问题）
      • 不存在多项式时间算法的问题
    • P类问题
      • 在多项式时间内可求解的判断问题
    • NP类问题
      • 在多项式时间内可验证的判定问题
    • NPC类问题
      • NPC问题是个NP问题，同时满足所有的NP问题都可以在多项式时间归约到该问题，这样的问题就是NPC问题
    • NP难问题
      • 该问题不一定是NP问题，但所有的NP问题能够在多项式时间归约到该问题
• 递归
  • 递归的概念
    • 递归是在其定义中直接或间接调用自身的一种方法
  • 递归的两个基本要素
    • 递归出口
    • 递归体
  • 递归算法的时间复杂度分析方法
    • • 建立递推方程
      • 求解递推方程
        • 迭代法
          • 直接迭代
          • 换元迭代
          • 差消迭代
        • 递归树
          • 首先将递推方程的表达式分为递归项和自由项，递归项需要进一步递归求解，自由项是关于n的某种函数表达式或常数项
          • 将初始方程的自由项作为根节点，递归项作为叶子结点建树
          • 用当前叶子结点对应的方程表达式构成的子树替换叶子结点，直到树中所有结点都由自由项构成
          • 将每个结点的自由项相加，得到最终结果
        • 主定理
  • 无典型例题
    • 可看看作业题，理解自己写的代码是什么意思
• 分治
  • 分治法的基本思想
    • 将一个难以解决的大问题，分割成一些规模较小的同类型问题，以便各个击破，分而治之
  • 分治法的解题步骤
    • 分解：将原问题分成一系列子问题
    • 解决：递归地解决各子问题。若子问题足够小，则可以直接求解
    • 合并：将子问题的结果合并成原问题的解
  • 可以使用分治法解决问题的关键
    • 针对该问题分解出的子问题的解可以合并为该问题的解
  • 分治法时间复杂度的分析方法
    • 建立并求解递归方程
    • 看书本P101的小结
  • 分治法设计的平衡原则
    • 使子问题的规模大致相同
  • 分治法的核心
    • 将问题分解为规模更小且性质相同的若干子问题
  • 无典型例题
• 动态规划
  • 动态规划的实质：分治思想和解决冗余
  • 动态规划的两个重要性质
    • 最优子结构性质
      • 问题的最优解包括其子问题的最优解
    • 重叠子问题性质
      • 问题依赖的子问题并不总是新问题，有些子问题会重复出现多次
  • 动态规划的解题步骤
    • 找到最优解的性质，并刻画其结构特征
    • 递归地定义最优值（建立动态转移方程）
    • 以自底向上的方式计算出最优值
    • 根据计算最优值时得到的信息，构造最优解
  • 动态规划算法思路描述重点
    • 建立动态转移方程，解释其含义
  • 动态规划复杂度分析方法
    • 时间复杂度：分析循环的嵌套次数及循环次数
    • 空间复杂度：取决于表的规模
  • 典型例题
    • 斐波那契数列
    • 数字三角形问题
    • 0-1背包问题
    • 矩阵连乘问题
    • 最长公共子序列
    • 最长不上升子序列
    • 最大连续字段和
• 贪心
  • 贪心法求解问题的两个性质
    • 最优子结构性质
      • 问题的最优解包括其子问题的最优解
    • 贪心选择性质
      • 问题的最优解可以通过一系列局部最优解得到
  • 贪心算法的思路描述重点
    • 确定贪心选择策略，描述具体过程
  • 贪心法时间复杂度分析方法
    • 是否需要排序
    • 处理过程的复杂度与具体问题相关
  • 典型例题
    • 活动安排问题
    • 过河问题
    • 哈夫曼编码
    • 最小生成树
• 回溯
  • 回溯法解题特征
    • 在搜索过程中动态产生问题的解空间
  • 回溯法的设计要素
    • 解向量
    • 解空间树
    • 深度优先搜索
    • 剪枝函数
  • 回溯法的解题步骤
    • 针对所给问题，定义问题的解空间
    • 确定易于搜索的解空间问题结构
    • 以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索
  • 回溯法思路描述重点
    • 给出解空间，确定是子集树还是排列树，设计剪枝函数
  • 回溯法时间复杂度分析方法
    • 取决于是子集树还是排列树
  • 典型例题
    • 0-1背包问题
    • 旅行售货员（TSP）问题
    • 符号三角形问题
  • 记一下ppt上排列数和子集树的代码框架
  • 重点复习思路
• 分支限界
  • 分支限界的基本思想/求解目标
    • P265小结
  • 分支限界的两种实现方式
    • 队列式分支限界
    • 优先队列式分支限界
• 概率算法
  • 舍伍德算法
  • 拉斯维加斯算法
  • 蒙特卡罗算法
  • 三个算法的特点和区别
• 特殊算法的异同
  • 分支限界与回溯的异同
  • 动态规划与贪心的异同
  • 分治与动态规划的异同
• 注意事项
  • 算法设计部分的时间复杂度均考虑最坏时间复杂度
  • 关于课后作业题
    • 模型跟典型例题差不多。考试也是，不会出原题，但是模型可能一样。
  • 考试题目中没有指明时间复杂度分析，而是说复杂度分析时
    • 时间复杂度和空间复杂度均要分析
  • 多看看老师发的第一次考试卷子题目的答案，里面有易错点
• 考试提醒
  • 算法设计
    • 在思路描述上要抓住要点，可以分步骤阐述，可以结合实例说明过程，不能过于简单
    • 相关变量和数据结构描述清楚
    • 可以直接调用库函数
    • 伪代码一般以函数的形式出现，加入必要的注释
    • 看清题目要求，不要漏题
  • 算法分析
    • 分析要有计算过程，不能只给结果