ALG 2-1: Computational Tractability (计算复杂性理论)

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

ALG 2-1: Computational Tractability (计算复杂性理论)

ALG 2-1: Computational Tractability (计算复杂性理论)

 

 

上一篇:搭建longhorn报错“failed to set bridge addr”


下一篇:mysql主从配置