Big O符号中的复杂度阶是什么？

Question

Big O符号中的复杂度阶是什么？

algorithmsortingcomplexity-theorybig-o

5

问题

大家好，我正在尝试理解'大O符号'中的复杂度顺序。我阅读了许多文章，但还没有找到任何解释'复杂度顺序'的内容，即使在这里有用的大O描述也是如此。

我已经理解的关于大O的部分

我已经理解的部分是，我们通过输入大小n的增长来衡量算法的时间和空间复杂度。我也知道某些排序方法对于大O有最佳、最坏和平均情况，例如O(n)、O(n^2)等，其中n是输入大小（要排序的元素数量）。

希望能够提供简单的定义或示例，非常感谢。

- Luke

8个回答

6

说一个函数 f(n)在O(g(n)) 中，当且仅当存在一个C和n0, 使得对于所有大于n0的n, 都有 f(n) < C*g(n)。

这是一种相当数学化的方法。所以我来给一些例子。最简单的情况是O(1)，这意味着"常数"。所以不管程序的输入(n)有多大，它都需要相同的时间完成。一个常数程序的例子是取一个整数列表并返回第一个。无论列表有多长，你只需取第一个并立即返回。

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

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

- Noctua

谢谢您的回答，这是否意味着复杂度顺序是从最简单的类型到更复杂的类型，例如：O(1)，O(log n)，o(n)，O(n log n)，O(n^2)等等...我一直在使用的一个好资源是http://www.leepoint.net/notes-java/algorithms/big-oh/bigoh.html我认为这个页面上的表格描述了复杂度顺序？ - Luke

6

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

考虑矩阵乘法，朴素算法的复杂度为O(n^3)。使用Strassen算法可以将其降为O(n^2.807)。现在甚至有算法可以得到O(n^2.3727)。

你可能会被诱惑选择具有最低大O的算法，但实际上，朴素的O(n^3)方法胜出。这是因为其他方法的主导项常数要大得多。

因此，仅仅看复杂度中的主导项可能会误导人。有时候必须考虑所有项。

- Z boson

1

你说得完全正确，很好有人提到这一点。谢谢。不过很抱歉我不能点赞，因为这并不是被问到的问题。 - Noctua

从实际角度来看，O(n^3) 算法胜出。但这取决于你的实际需求。如果你需要计算两个1000 x 1000的矩阵相乘，那么其他算法比朴素的乘法更有效率。大O符号并不能告诉你对于给定的n，哪种算法最有效；它只能告诉你在非常大的n值下哪种算法最有效。 - Peter Webb

@PeterWebb，那是不正确的。对于大矩阵，朴素乘法仍然胜出。大O告诉你在n趋近于无穷大时哪个更好，但在这种情况下，对于所有实际值的n，朴素算法仍然是最好的。 - Z boson

2

大O符号是关于找到某个函数增长上限的概念。在维基百科上可以看到正式定义http://en.wikipedia.org/wiki/Big_O_notation。

如果你有一个排序大小为n的数组的算法，它只需要常量级别的额外空间，并且完成所需步骤数量为(例如)2n² + n，那么你会说它的空间复杂度是O(n)或O(1)（取决于是否计算输入数组的大小），时间复杂度是O(n²)。

仅凭这些O符号，你就大致可以确定从n到n+100或2n等需要多少更多的空间和时间。这就是一个算法“可扩展性”的好坏。

更新

大O符号和复杂性实际上只是同一概念的两个术语。你可以用“线性复杂度”代替O(n)，用“二次复杂度”代替O(n²)，以此类推。

- Jonas Bötel

谢谢，我想我明白了那一部分，我正在尝试弄清楚“复杂度阶数”在大O符号中的确切含义。 - Luke

2

我看到你在评论中想要了解与Big-O相关的特定顺序术语。

假设f（n）= O（n ^ 2），我们说顺序是n ^ 2。

- Ryan Hallberg

1

请注意，这里有一些微妙之处。你说“我们通过输入大小n的增长来衡量算法的时间和空间复杂度”，这是人们通常处理它的方式，但实际上并不正确。相反，使用O(g(n))，我们确定g(n)在适当缩放后是算法所有输入大小大于某个特定n'的时间和空间复杂度的上界。同样，使用Omega(h(n))，我们确定h(n)在适当缩放后是算法所有输入大小大于某个特定n'的时间和空间复杂度的下界。最后，如果上下界都是相同的复杂度g(n)，则复杂度为Theta(g(n))。换句话说，Theta表示算法的复杂度程度，而大O和大Omega则将其上下限制定。

- pjs

1

常量增长：O(1)
线性增长：O(n)
二次增长：O(n^2)
三次增长：O(n^3)
对数增长：(log(n)) 或 O(n*log(n))

- Rahul Vishwakarma

0

大 O 使用数学定义复杂度。
工业中使用的复杂度顺序。

- Iftakhar alam

1

那没有回答问题。OP 想知道 "复杂度顺序" 在大 O 复杂度分析的背景下意味着什么。 - joanis

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pramod Bhat · Accepted Answer

大 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

找到一个能够在超线性时间或更短时间内运行的算法，可以极大地提高应用程序的性能。