使用计算机计算各种问题，需要存储空间、计算时间。不同的算法计算所需要的时间和空间是不同的。所谓算法

的复杂性就是对算法计算所需要的时间和空间的一种度量。由于不同的计算机千差万别，运算速度和字长可以相差很大，因此，不可能用算法在某一台计算机上计算所需要的实际的时间和存储单元（空间）去衡量这个算法的复杂性。那么，怎样才能准确刻划算法的计算复杂性呢？

引入渐近增长率的概念来刻划算法的计算复杂性。渐进增长率用复杂性度量函数表示，该函数表示了算法随问题规模大小变化引起的算法中抽象的基本运算执行的次数或存储空间量的变化规律。如某个计算问题当输入规模分别为1，2，3，…，n时，经分析算法中抽象的基本运算次数分别为1，4，9，…，n2，那么，就可以用函数n2来刻划这个算法的时间复杂性，并称这个算法的时间复杂性度量为(n2)级。有了复杂性度量函数，一旦选定具体计算机，可以根据这台计算机对某个n值的实际运算速度比较准确地估算出对其他的n值完成计算所需要的时间。于是，对各种

算法的复杂性进行分析的关键是要设法去找出这样的函数，它涉及到与数学密切相关的算法的设计原理、思想和方法，算法分析是具有智力挑战性的研究课题。在算法计算复杂性的研究中，一个算法如果存在图灵机可计算的多项式时间计算复杂性算法，就将这个算法归入P类，如果存在非确定性图灵机可计算的多项式时间计算复杂性算法，就将其归入NP类。对大多数实际问题来说，找到一个解可能很难，检验一个解常常比较容易，所以都属于NP类。现在，计算科学研究中一个悬而未决的重要问题是P＝NP？。

P＝NP？ 这个问题不仅具有理论上的价值，而且具有重大实用价值。因为到目前为止，已经发现了一批可计算但有相当难度的问题是属于NP类的，并且常通过证明一个问题与已知

属于NP类中的某个问题（如可满足性问题，简称SAT问题）等价将其归入NP类。不过，该问题是否属于 P类，即是否能找到多项式时间计算复杂性算法求解该问题，或证明该问题不存在多项式时间计算复杂性算法求解，至今尚未解决。现在，很多人都猜测秋碧贞楠的看法是对的：求解一个问题总是比验证一个问题的解要难，用公式表示也就是P≠NP。70年代初，库克（S. A. Cook）和卡尔普（R. M. Karp）指出，NP类中有一小类问题具有以下性质：迄今为止，这些问题多数经过深思熟虑还没有人找到多项式时间计算复杂性算法。但是，一旦其中的一个问题找到了多项式时间计算复杂性算法，这个类中的其它问题也能找到多项式时间计算复杂性算法，那么就可以断定P＝NP。换句话说，如果确属这个类中的某个问题被证明不存在多项式时间计算复杂性算法，那么，就等于证明了P≠NP。通常，将这类问题称为NP完全性问题。