大O表示法
概念
一般用大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表示法仅仅是一种粗略的分析模型,是一种估算,能帮助我们短时间内了解一个算法的执行效率。