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

Question

题

嗨,我试图了解Big O表示法的复杂程度.我已经阅读了很多文章,但我还没有找到任何解释'复杂程度'的内容,即使是在这里对Big O的有用描述.

我对大O的了解

我已经理解的部分.关于Big O表示法是我们根据输入大小n的增长来测量算法的时间和空间复杂度.我也理解某些排序方法具有Big O的最佳,最差和平均场景,例如O(n),O(n ^ 2)等,并且n是输入大小(要排序的元素的数量).

任何简单的定义或示例都将非常感谢,谢谢.

Answer 1

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

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

Answer 2

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

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

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

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

Answer 3

其他人在这里很好地解释了大 O 符号。我想指出，有时过分强调大 O 符号。

考虑矩阵乘法，朴素算法有 O(n^3)。使用 Strassen 算法，它可以作为 O(n^2.807) 完成。现在甚至有算法可以得到 O(n^2.3727)。

人们可能会倾向于选择具有最低大 O 的算法，但对于所有实际目的而言，天真的 O(n^3) 方法胜出。这是因为对于其他方法，支配项的常数要大得多。

因此，仅查看复杂性中的主导术语可能会产生误导。有时必须考虑所有术语。

Answer 4

Big O 是关于寻找某些函数增长的上限。请参阅维基百科上的正式定义http://en.wikipedia.org/wiki/Big_O_notation

\n\n

因此，如果您有一个对大小数组进行排序的算法n，并且它只需要恒定量的额外空间，并且需要（例如）2 n\xc2\xb2 + n步骤来完成，那么您会说它的空间复杂度是O(n)或O(1)（取决于是否计算输入数组的大小），其时间复杂度为O(n\xc2\xb2)。

\n\n

仅知道这些数字，您就可以粗略地确定从到或或您感兴趣的任何内容O需要多少空间和时间。这就是算法的“扩展”程度。nn + 1002 n

\n\n

更新

\n\n

Big O 和复杂性实际上只是同一事物的两个术语。你可以说“线性复杂度”而不是O(n)，二次复杂度而不是O(n\xc2\xb2)，等等......

\n