第二讲 算法效率分析

算法设计与分析——时间复杂度分析、问题分类、NPC、NP-hard问题，介绍详细，知识全面，希望可以对大家有所帮助！

第二讲 算法效率分析

• 时间复杂度分析
  • 时间复杂度的渐进表示符号
    • 小o表示法：严格渐进上界
    • 大O表示法：渐进上界
    • 大θ表示法：紧界
    • 大Ω表示法：渐进下界
    • 小w表示法：严格渐进下界
  • 递归算法的时间复杂度分析：主定理（Master定理）
• 问题分类
  • 可计算问题
    • 可以用算法解决的问题
  • 不可计算问题
    • 任何具备一定算术表达能力的、自洽的形式系统F是不完备的：即存在一个语句在F中既不能被证明，也不能被证伪
    • 无法用算法解决的问题（停机问题、哥德尔不完备定理）
  • 查找问题（搜索问题）
    • 找出可行解的问题
      • N皇后问题、路径规划问题
      • 查找问题的特例：最优查找问题（属于最优化问题）
      • AI中的搜索问题定义
  • 博弈
    • 在一定条件下，遵守一定的规则，一个或几个拥有绝对理性思维的参与者，从各自允许选择的行为或策略进行选择并加以实施，并从中各自取得相应结果或收益的过程
  • 判定性问题
    • 返回“是”或“否”的问题
  • 最优化问题
    • 寻找使得目标函数取极值的解的问题
      • 单目标优化问题
      • 多目标优化问题
      • 线性规划问题
        • 求线性目标函数在线性约束条件下的最大值或最小值的问题
        • 整数线性规划问题——决策变量只能取整数的线性规划问题
      • 非线性规划问题
        • 求非线性目标函数或非线性约束条件的最优化问题
• NPC、NP-hard问题
  • P问题——一个问题如果存在多项式时间复杂度的算法，则称该问题为P 问题
  • NP问题——任给一个解，如果存在多项式时间的算法来验证所给的解是问题的正确解，则称该问题为NP问题
  • p问题是NP问题，但NP问题不一定是P问题
  • NP完全性
    • 具有传递性
    • #P（sharp-P问题）
      • 通常，#P问题比NP问题难
      • 寻找一个NP问题的解的数量的问题
    • coNP问题
      • NP问题的补问题，定义：给定一个问题的一个解实例，如果该解实例不是问题的解，则存在多项式时间算法给出证明
        • 若一个问题既是NP问题，又是coNP问题，则存在多项式时间算法判断任意解是否是问题的解
    • NPC问题（NP完全问题）
      • NP中最难的一类
      • 具有传递性
      • （1）是一个NP问题；（2）所有的NP问题都可以在多项式时间规约成该问题
        • 只要解决一个NPC问题，那么所有NP问题都将解决
        • （1）SAT问题；（2）3SAT问题；（3）旅行商问题；（4）哈密尔顿回路问题；（5）哈密尔顿路径问题；（6）子集和问题；（7）0-1背包问题；（8）独立集问题；（9）团问题；（10）顶点覆盖问题；（11）支配集问题；（12）集合覆盖问题；（13）恰切覆盖问题
    • NP-hard问题
      • 所有的NP问题都可以在多项式时间规约成NPC问题
• 证明问题X为NPC问题的思路
  • 证明问题X是NP问题
  • 证明一个已知的NPC问题Y
  • 证明问题Y可以在多项式时间规约到问题X，即证明Y£þX。
• 重要结论
  • 如果已经发现一个问题Y是难的（即不存在多项式时间算法），并且已经证明Y£þX。那么难度将被“传播”给问题X，因此，问题X也是难的，不存在多项式时间算法，否则，可以用它求解Y