概念

一般用大O表示法来描述复杂度，它表示的是数据规模n 对应的复杂度。

举个例子:

常见复杂度.png

解析：

O(1)
O(1)表示该算法的执行时间（或执行时占用空间）总是为一个常量，不论输入的数据集是大是小。

O(N)
O(N)表示一个算法的性能会随着输入数据的大小变化而线性变化。下面的例子同时也表明了大O表示法其实是用来描述一个算法的最差情况的：在for循环中，一旦程序找到了输入数据中与第二个传入的string匹配时，程序就会提前退出，然而大O表示法却总是假定程序会运行到最差情况（在这个例子中，意味着大O会表示程序全部循环完成时的性能）。

O(N^2)
O(N^2)表示一个算法的性能将会随着输入数据的增长而呈现出二次增长。最常见的算法就是对输入数据进行嵌套循环。如果嵌套层级不断深入的话，算法的性能将会变为O(N3)，O(N4)，以此类推。

O(2^N)
O(2N)表示一个算法的性能将会随着输入数据的每次增加而增大两倍。O(2N)的增长曲线是一条爆炸式增长曲线——开始时较为平滑，但数据增长后曲线增长非常陡峭。一个典型的O(2^N)方法就是裴波那契数列的递归计算实现。

对数
要说明对数情况，稍稍有点复杂，因此我将使用一个非常通用的示例：
二分查找是一种用来在有序集合中进行查找的高效算法。二分查找从数据集的中间位置开始，然后用这个中间值和一个目标值进行比较。如果比较结果为相等，则程序返回成功。如果目标值大于中间值，程序会截取从中间值开始到最大值的那段数据集，并重复执行同样的查找方法。想死的，如果目标值小于中间值，程序将会继续在数据集中较小的那一半执行二分查找。二分查找程序会持续的将数据集对等分，以进入下一次循环，直到最终找到与目标值相等的数据后，程序就退出。
这类算法的性能就会被描述为O(logN)。正是通过这种不断对数据进行对等分的二分查找操作，使得二分查找算法的曲线从一个峰值开始，随着输入数据集的增长而慢慢的变得平缓。用例子来说明的话，例如一个包含10个输入数据的程序需要耗时一秒完成，则一个包含100个输入数据的程序就需要耗时两秒，然后一个包含1000个输入数据的程序就耗时三秒。加倍的输入数据对这类算法的性能结果影响非常小。基于如此，类似于二分查找的对数级算法在处理大量数据集时非常高效。

以上情况的执行速度等级如下：
速度： 常数 > logn > O(n) > O(nlogn) > O(n^2)

注意：大O表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率。