时间负责度被分为两个级别: 多项式级复杂度和非多项式级复杂度
多项式级复杂度: O(1) O(log(n)) O(n^a)
非多项式级复杂度: O(a^n) O(n!)
当我们在解决一个问题的时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度计算机往往不能承受，除非数据量非常少。
P问题: 一个可以找到在多项式时间内解决它的算法的问题
NP问题: 可以在多项式时间里验证一个解的问题
NPC问题: 是一类特殊的NP问题。需满足如下两个条件:
- 它得是一个NP问题
- 所有的NP问题都可约化到它
NPC问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。
| 题目 | 时间复杂度 |
|---|---|
| 在一个无序序列中寻找最大值或最小值 | O(n) |
| 在一个无序序列中寻找任意值 | O(n) |
| 在一个无需序列中寻找第k大的值 | O(n) |
| 在一个有序序列中寻找最大值或最小值 | O(1) |
| 在一个有序序列中寻找任意值 | O(lgn) |
| 在一个有序序列中寻找第k大的值 | O(1) |
| 在两个有序序列中寻找第k大的值 | O(lg(m+n)) |