Big O表示法的复杂程度是多少？

比如,f(n) in O(g(n))当且仅当存在C和n0时,f(n) < C*g(n)所有n大于n0.

现在这是一种相当数学的方法.所以我举一些例子.最简单的情况是O(1).这意味着"不变".因此,无论程序的输入(n)有多大,都需要相同的时间才能完成.常量程序的一个例子是获取整数列表并返回第一个整数.无论列表有多长,您都可以先拿下第一个并立即归还.

接下来是线性的,O(n).这意味着如果程序的输入大小加倍,执行时间也会增加.线性程序的一个例子是整数列表的总和.你必须看一次每个整数.因此,如果输入是大小为n的列表,则必须查看n个整数.

直观的定义可以将程序的顺序定义为输入大小和执行时间之间的关系.

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

找到一个在超线性时间或更好的时间内工作的算法可以对应用程序的执行情况产生巨大的影响.