笔记: 算法图解:像小说一样有趣的算法入门书 (By Aditya Bhargava)
  1. 算法简介
  2. 递归,栈,分治,快排与散列
  3. 图,队列与树
  4. 贪婪算法与动态规划
  5. 贪婪算法与动态规划
贪婪算法与动态规划

Last updated by Yarco on Tue, 12 Feb 2019 06:25:45 +0000

贪婪算法

#### 教室调度问题 #### 背包问题

局部最优解 得到 全局最优解 的近似值.

### NP 完全问题

元素较少时算法的运行速度非常快,但随着元素数量的增加,速度会变得非常慢。
涉及“所有组合”的问题通常是 NP 完全问题。
不能将问题分成小问题,必须考虑各种可能的情况。这可能是 NP 完全问题。
如果问题涉及序列(如旅行商问题中的城市序列)且难以解决,它可能就是 NP 完全问题。
如果问题涉及集合(如广播台集合)且难以解决,它可能就是 NP 完全问题。
如果问题可转换为集合覆盖问题或旅行商问题,那它肯定是NP完全问题。 (个人认为 指的是 当增加一个条件时, 将影响所有可能的已知答案 -- 点~全局 关联时, 是NP问题)

动态规划

(个人思考, 适合的情况属于)

  • 近似的离散型数据/整型(子问题独立)
  • 具有聚合值, 而根据这个聚合值判断优先

### 最长公共子串 #### 最长公共子序列

comments powered by Disqus