Big-O 分析是运行时分析的一种形式,它根据算法运行所需的时间(作为输入大小的函数)来衡量算法的效率。它不是一个正式的基准,只是在处理非常大的输入大小时根据相对效率对算法进行分类的简单方法。
更新:
任何运行时分析的最快可能运行时间为 O(1),通常称为恒定运行时间。具有恒定运行时间的算法总是花费相同的时间
无论输入大小如何,都可以执行。这是算法的理想运行时间,但很少可以实现。
大多数算法的性能取决于输入的大小 n。算法可以按照性能从最好到最差进行如下分类:
O(log n) — 如果算法的运行时间与输入大小成对数比例增加,则该算法被称为对数算法。
O(n) — 线性算法的运行时间与输入大小成正比。
O(n log n) — 超线性算法介于线性算法和多项式算法之间。
O(n^c) — 多项式算法根据输入的大小快速增长。
O(c^n) — 指数算法的增长速度甚至比多项式算法还要快。
O(n!) — 阶乘算法增长最快,即使 n 值很小,也会很快变得无法使用。
随着 n 变大,不同阶算法的运行时间迅速分开。考虑每个算法类的运行时间
n = 10:
log 10 = 1
10 = 10
10 log 10 = 10
10^2 = 100
2^10= 1,024
10! = 3,628,800
Now double it to n = 20:
log 20 = 1.30
20 = 20
20 log 20= 26.02
20^2 = 400
2^20 = 1,048,576
20! = 2.43×1018
找到一种在超线性时间内或更好的算法可以对应用程序的性能产生巨大的影响。