1. 简介
在计算理论中；有一种理论称作‘计算复杂性理论’（computational complexity theory ）,专门研究计算问题时所需的资源，比如时间和空间，以及如何尽可能地节省这些资源。
2. Polynomial-Time
Brute force. For many non-trivial problems, there is a natural brute force search algorithm that checks every possible solution.
(暴力求解。许多大的问题，通常可以用暴力求解检查每一个可能的解决方案。)
- Typically takes 2^n time or worse for inputs of size N. (对于大小为n的输入，通常要花费2^n的时间，甚至更糟) Unacceptable in practice. (在实践中, 这是不可接受的)
- n! for stable matching with n men and n women
Desirable scaling property. When the input size doubles, the algorithm should only slow down by some constant factor C.
(理想状况: 当输入大小翻倍时，算法只会减慢某个常数因子C。)
- There exists constants c > 0 and d > 0 such that on every input of size N, its running time is bounded by cN^dsteps.
- (存在常数c > 0和d > 0，使得对于每一个大小为N的输入，其运行时间不超过 cN^d 步)
Def. An algorithm is poly-time if the above scaling property holds. （choose C = 2^d）
定义：如果上述属性成立，则算法是poly-time的. （choose C = 2^d）
3. Worst-Case Analysis
Worst case running time. Obtain bound on largest possible running time of algorithm on input of a given size N.
（最坏情况下运行时间。求算法在给定大小N的输入下最大运行时间的界）
- Generally captures efficiency in practice. （通常在实践中获得效率）
- Draconian view, but hard to find effective alternative. （严厉的观点，但很难找到有效的替代方案。）
Average case running time. Obtain bound on running time of algorithm on random input as a function of input size N.
（平均情况运行时间。得到随机输入作为输入大小N的函数时算法运行时间的上界。）
- Hard (or impossible) to accurately model real instances by random distributions. 很难(或不可能)通过随机分布精确地建模真实实例。
- Algorithm tuned for a certain distribution may perform poorly on other inputs. 针对某一分布优化的算法在其他输入上的性能可能较差。
4. Worst-Case Polynomial-Time
Def. An algorithm is efficient if its running time is polynomial. （定义：如果一个算法的运行时间是多项式的，那么它就是有效率的。）
Justification: It really works in practice! （理由:它在实践中确实有效!）
- Although 6.02 ×10^23×N^20 is technically poly-time, it would be useless in practice. （虽然6.02×10^23×N^20在技术上是多时间的，但在实践中是没有用的。）
- In practice, the poly-time algorithms that people develop almost always have low constants and low exponents. （在实践中，人们开发的多时间算法几乎总是有低常数和低指数。）
- Breaking through the exponential barrier of brute force typically exposes some crucial structure of the problem. （突破暴力求解的指数障碍通常会暴露问题的一些关键结构。）
Exceptions
- Some poly-time algorithms do have high constants and/or exponents, and are useless in practice. (一些多时间算法有高常数和/或指数，所以在实践中是无用的。)
- Some exponential-time (or worse) algorithms are widely used because the worst-case instances seem to be rare. （一些指数时间(或更糟的)算法被广泛使用，因为最坏情况的实例似乎很少。）
- simplex method
- Unix grep
5. Why It Matters
