邹恒明 著
无限容积的罐子和无限个球，球从 1 开始连续编号。
过 1 秒后，在罐子中放 1~10 个球，并将 10 号球取出；
再过 1/2 秒，在罐子中放 11~20 个球，并将 20 号球取出；
再过 1/4 秒，在罐子中放 21~30 个球，并将 30 号球取出；
...
再过 1/2^n 秒，在罐子中放 10*n+1~10*(n+1)个球，并将 10*(n+1) 号球取出；
就这样将游戏进行下去。
假定放球和取球不占时间。当时间达到 2 秒时，罐子里还有多少球？ 答案是：无穷。
现在改变策略。将每次拿 10、20、30...号球变为拿 1、2、3...号球，即第 x 次拿球，所拿的球的编号是 x，罐子里还有多少球？ 答案是：无有（即 0）。
再改变策略，球还是这样放，但是取球是随机拿出一球。罐子里还有多少球？ 答案是：无有。
为什么？ 个人理解：如果放球和取球能够建立一一映射的关系，则罐子里就没球。
型如
T(n)=a*T(n/b)+f(n)
的递归函数，计算时间复杂度。
| 条件 | 复杂度 |
| ---------------- | ----------------------- |
| f(n)<n^(logb(a)) | T(n)=n^(logb(a)) |
| f(n)=n^(logb(a)) | T(n)=n^(logb(a)) * logb(n) |
| f(n)>n^(logb(a)) | T(n)=f(n) |
| 无法比较 | 没有规律，靠猜 |
动态规划策略是一种分治策略，即将问题分解为一个或多个子问题。
动态规划的策略的特点就是根据问题的具体情况，对选择进行动态调整，并且在每一步的调整中做出的都是一个最优的选择（因为做出选择所需的信息都已经知道）。而且该最优选择与对子问题的最优解组合，获得原问题的最优解。
动态规划要能够成功，需要注意： （1）最优子结构 （2）重叠子问题
在考虑使用动态规划策略时，一般战略如下： （1）证明问题的解决方案中包括一个选择，选择之后将留下一个或多个子问题 （2）设计子问题的递归描述形式 （3）证明对原问题的最优解里包括对所有子问题的最优解（通常使用反证法） （4）证明子问题之间重叠（保证效率。如果没有重叠子问题，则动态规划与一般的递归算法别无二致）
动态规划的时间成本可以简单表述为：全部子问题数量 X 选择数量
一步一步地构建问题的最优解决方案，其中每一步均只需眼前的最佳选择，即希望通过局部最优达到全局最优。
贪婪策略想要获得最优解，必须满足以下 2 个条件： （1）每个大问题的最优解里面，包括下一级小问题的最优解 （2）每个小问题可由贪婪选择获得（如果没有该属性，则贪婪选择将不能保证得到最优解）
| 类型 | 标准分治 | 动态规划 | 贪婪选择 |
|---|---|---|---|
| 适用类型 | 通用问题 | 优化问题 | 优化问题 |
| 子问题结构 | 每个子问题不同 | 很多子问题重复 | 只有一个子问题 |
| 最优子结构 | NA | 必须满足 | 必须满足 |
| 子问题数 | 全部子问题都要解决 | 全部子问题都要解决 | 只要解决一个子问题 |
| 子问题在最优解里 | 全部 | 部分 | 部分 |
| 选择与求解次序 | 先选择后解决子问题 | 先解决子问题后选择 | 先选择后解决子问题 |
满足以下条件的算法称为在线算法： （1）一次只提供一个操作序列 S 里面的一个操作 （2）对于每个操作，算法必须立即执行所需的操作（在不知道将来的操作是什么的情况下）
满足如下条件的算法称为离线算法：离线算法可以事先看到整个操作序列
离线方式下，最优是可能的；而在线方式下，最优即使在理论上也是不可能的
决策问题讨论的是“一个特定的表述”是否为真，而优化问题讨论的则是寻找一个最好或得分最高的解答。
优化问题又可以分为 2 种类型：最小优化问题和最大优化问题。前者试图找出一种成本最低的解答，而后者试图找出一个收益最高的解答。
优化问题和决策问题是相伴而行的，即有一个优化问题，就有一个对应的决策问题，而每一个决策问题也对应一个优化问题。
搜索问题、决策问题和最优化问题之间是等价的。
易解问题存在多项式时间解；NP 完全问题到目前尚未找到多项式时间解；而难解问题则不存在多项式时间解。
找不到或不存在多项式时间解，并不说明这些问题没有解。这三类问题都有解，即都存在解决方案，只不过这些算法解决方案的时间或空间效率不怎么样，没有实际价值。从这个角度来说，这些问题都是可决定的问题：只要给出足够的时间，总能算出解。
但这个世界上还存在一类问题，它们是无解的，即不可能找到时间解，哪怕花费的时间成本是指数级或指数的指数级都无济于事。这些问题呗称为不可决定问题。
不可决定问题的一个根本特性是算法解决方案不存在，不论我们愿意花费多少时间和精力都无济于事。
| 问题类型 | 描述 | 有理论解 | 有实际解 | 潜在证人有限 |
|---|---|---|---|---|
| 易解问题 | 多项式时间解决方案已知 | 是 | 是 | 是 |
| NP 完全问题 | 多项式时间解决方案未知 | 是 | 是/否 | 是 |
| 难解问题 | 多项式时间解决方案不存在 | 是 | 否 | 是 |
| 部分不可决定问题 | 算法解决方案不存在，但证人数量有限 | 未知 | 否 | 是 |
| 高度不可决定问题 | 算法解决方案不存在，且证人数量无限 | 未知 | 否 | 否 |
| 不可解问题 | 任何解决方案都不存在 | 否 | 否 | 没有证人 |
图灵的停机问题，就是一个不可解问题。