计算复杂性

所谓"计算复杂性"，通俗说来，就是用计算机求解问题的难易程度。其度量标准：一是计算所需的步数或指令条数(这叫时间复杂度)，二是计算所需的存储单元数量(这叫空间复杂度)。我们当然不可能也不必要就一个个具体问题去研究它的计算复杂性，而是依据难度去研究各种计算问题之间的联系，按复杂性把问题分成不同的类:

常见的时间复杂度按数量级递增排列依次为：常数0(1)、对数阶0(logn)、线形阶0(n)、线形对数阶0(nlogn)、平方阶0(n2)立方阶0(n3)、…、k次方阶0(n^k)、指数阶0(2^n)。显然，时间复杂度为指数阶0(2^n)的算法效率极低，当n值稍大时就无法应用。

类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。算法的时间复杂度和空间复杂度合称为算法的复杂度。

注:为了表达的方便,计算机上的复杂度分析中使用的对数函数log(n)一般指取以2为底的对数.