算法复杂度的定义

算法是一组规则，提供了解决某个特定问题的运算序列。算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。同一问题，使用不同的算法，过程中消耗的资源与时间会有很大的差异，算法复杂度就是用来衡量算法之间的优劣。

衡量算法复杂度的维度主要分了两个方面，时间、空间。也叫时间复杂度和空间复杂度。当然，还有网络消耗等。尤其是现在的机器硬件性能呈指数级增长，于是算法关注时间复杂度就更多一些。

• 时间维度：是指执行当前算法所消耗的时间，这时间不指具体耗费的时间，而是用各算法中语句执行次数来比较。
• 空间维度：是指执行当前算法需要占用多少内存空间，同样不直接用具体的空间消耗来比较，而是运行过程中临时占用存储空间大小的一个量度。

分析算法的要从大局出发，关注最显著的变量。忽略依赖环境的常量，并将关注点放在增长的趋势，重点看最坏、平均、最佳这三类情况。

大 O 表示法

因算法消耗的时间与空间都无法精确地来计算，在算法中用大O表示法来描述一个算法的运行时间和占用空间的相对概念，它将算法的比较简化为单一变量，并且只关注其中最重要的部分或者最显著的部分。如只关注语句执行次数；n * n + 2n在n无穷大时2n无关紧要，所以简化为n * n。

大O符号是用于描述函数渐进行为的数学符号，关注无穷大与无穷小渐近，即关注数据量比较大的情况。德国数论学家保罗·巴赫曼（Paul Bachmann）在其1892年的著作《解析数论》（Analytische Zahlentheorie）首先引入，在另一位德国数论学家艾德蒙·朗道（Edmund Landau）的著作中推广的。

分析算法的时候常见的函数分类列表，算法的效果由好到坏：

• O(1)，常数，最好的情况，与数据量无关。
• O(log*n)，迭代对数。
• O(log n)，对数，相当好的情况，每次循环都能将数据量显著的减少。
• O[(log n)^c]，多对数。
• O(n)，线性，次线性，不错的情况，计算量线性增长。
• O(n log n)，线性对数、或对数线性、拟线性、超线性
• O(n^2)，平方。
• O(n^c),Integer(c>1)，多项式，有时叫作“代数”（阶）。
• O(c^n)，指数，有时叫作“几何”（阶）。
• O(n!)， 阶乘，有时叫做“组合”（阶），非常慢的情况。

时间复杂度

在大O符号表示法中，时间复杂度的公式是： T(n) = O( f(n) )，其中f(n) 表示每行代码执行次数之和，而 O 表示正比例关系，随着n增大消耗的时间也增长f(n)，这个公式的全称是：算法的渐进时间复杂度。

常见的时间复杂度量级在下面用代码表示：

• 常数阶O(1)

int i = 1;

这里指的是没有循环递归等复杂结构，忽略固定的执行次数，都是常数量级。

• 线性阶O(n)

for(i=1; i<=n; ++i) {...}

for循环里面的代码会执行n遍，那么消耗的时间就是线性增长的。递归也算此类。

• 对数阶O(logN)

for(i=1; i<=n; i = i * 2) {...}

for循环中有另外一个变量将加倍地加速循环的退出，让n变成对数级的增长。

• 平方阶O(n^2)

for(i=1; i<=n; ++i) {
    for(j=1; j<=n; ++j) {...}
}

两次for循环，且都需要次，则为平方阶增长。嵌套代码的复杂度等于嵌套内外层代码复杂度的乘积。

空间复杂度

用 S(n) 来表示空间占用趋势，公式是：S(n) = O( f(n) )。比较常用的有：O(1)、O(n)、O(n2)。只关注与算法执行相关的空间消耗，一般指内存空间。现如今，多数情况下完全可以用空间来换时间。