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