哪个更好：O(n log n)还是O(n^2)？

Question

哪个更好：O(n log n)还是O(n^2)？

algorithmtime-complexitybig-ocomplexity-theory

68

好的，我有一个项目需要完成，但我不理解它。问题是我有两个算法：O(n^2)和O(n*log₂n)。

无论如何，在项目信息中我发现如果n<100，那么O(n^2)更有效率，但如果n>=100，那么O(n*log₂n)更有效率。我应该使用数字、文字或绘制图片的方式演示一个例子。但问题是，我不懂这个算法，也不知道如何进行演示。

有人能帮助我理解这是如何工作的吗？

- user3579272

8个回答

50

如果你有疑问，只需询问wolframalpha。

在这种情况下，它显示：

     n log(n)
lim --------- = 0
       n^2

或者你也可以自行计算极限：

     n log(n)        log(n)   (Hôpital)       1/n          1
lim --------- = lim --------      =     lim ------- = lim --- = 0
       n^2             n                       1           n

这意味着n^2增长得更快，因此当n足够大时，n log(n)较小(更好)。

- Oriol

19

大O符号是渐进复杂度的一种表示方法。这意味着它在N趋于无穷大时计算复杂度。

对于小的N，会有许多其他因素影响。可能一个算法具有O(n^2)的循环迭代，但每次迭代非常短，而另一个算法具有O(n)的迭代，但每次迭代非常长。对于较大的N，线性算法将更快。对于小的N，二次算法将更快。

因此，对于小的N，只需测量两个算法并查看哪个更快即可。无需深入了解渐进复杂度。

顺便提一下，不要写对数的底数。大O符号忽略常数 - O(17 * N)与O(N)相同。由于log₂N只是ln N / ln 2，对数的底数只是另一个常数，并被忽略。

- zmbq

13

让我们比较一下，

一方面，我们有：

n^2 = n * n

另一方面，我们有：

nlogn = n * log(n)

将它们并排放置：

n * n    versus    n * log(n)

我们将除以一个常见的项n，得到：

n    versus    log(n)

让我们比较一下数值：

n = 10           log(n) ~ 2.3
n = 100          log(n) ~ 4.6
n = 1,000        log(n) ~ 6.9
n = 10,000       log(n) ~ 9.21
n = 100,000      log(n) ~ 11.5
n = 1,000,000    log(n) ~ 13.8

所以我们有：

n >> log(n) for n > 1

n^2 >> n log(n) for n > 1

- Khaled.K

2

@ Khaled，base的值是多少？我认为是2，但log 10（base 2）的值是3.32，你能确认一下吗？ - Nihar

@N.Nihar 我使用了沃尔夫拉姆阿尔法，它假设使用自然对数（即基数为e ~ 2.7）。如果你在处理二叉树，可以使用基数为2。如果你选用基数为10，那么你将得到 10^n，而 log10 将是最左边的数字后面的位数：1000 = 10^3 = 10*10*10, log10(1000) = log10(10^3) = 3。 - Khaled.K

3

无论如何，我在项目信息中发现，如果n < 100，则O(n^2)更有效率，但如果n >= 100，则O(n*log2n)更有效率。

让我们首先澄清当前上下文中的"大O符号"是什么意思。从（source）中可以读到：

"大O符号是一种数学符号，用于描述函数在自变量趋近于某个特定值或无穷大时的极限行为。（...）在计算机科学中，大O符号用于根据输入大小增长时运行时间或空间要求如何增长来对算法进行分类。"

"大O符号"不代表一个函数，而是一组具有特定渐进上界的函数集合；正如source所述：

“大O符号”用于表征函数的增长率：具有相同增长率的不同函数可以使用相同的“O”符号表示。在计算机科学中的时间复杂度和空间复杂度理论中，“大O符号”可以被视为一种算法分类，其最坏情况下的时间和空间分别与之相关。例如，“O(n)”表示：

“如果一个算法的时间/空间复杂度为O(n)，那么它被称为具有线性时间/空间复杂度或O(n)时间/空间复杂度。简单来说，这意味着运行时间/空间随着输入规模的增加最多呈线性增长。”（来源：source）。

而“O(n log n)”则表示：

如果某个算法的时间/空间复杂度为T(n) = O(n log^k n)，其中k是正常数，则称其在准线性时间/空间内运行；当k = 1时，称其在线性对数时间/空间内运行（source）。

从数学角度来看，语句“O(n log n)与O(n^2)哪个更好”并不准确，因为如前所述，大O符号表示一组函数。因此，更准确的说法应该是“O(n log n)包含O(n^2)吗？”尽管如此，通常这种放松的措辞通常用于量化（针对最坏情况）一组算法相对于另一组算法在其输入大小增加方面的行为。要比较两类算法（例如，O(n log n)和O(n^2)），而不是...

无论如何，我在项目信息中发现，如果n < 100，则O(n^2)更有效率，但如果n >= 100，则O(n*log2n)更有效率。您应该分析两类算法在最坏情况下随着输入规模（即n）增加时的行为；分析当n趋近于无穷大时的情况。

正如 @cem 所指出的，在图片中，“big-O”表示绘制函数的渐近最小上界之一，而不是指集合 O(f(n))。

从图像中可以看到，在某个输入后，O(n log n)（绿线）增长速度比O(n^2)（橙线）要慢。这就是为什么（对于最坏情况）O(n log n)比O(n^2)更理想的原因，因为你可以增加输入大小，而前者的增长速度比后者慢。

- dreamcrash

0

我们有两种比较两个算法的方法 -> 第一种方法非常简单，只需进行比较并应用限制条件

T1(n)-Algo1

T2(n)=Alog2

  lim  (n->infinite) T1(n)/T2(n)=m

(i)如果m=0，Algo1比Algo2更快。

(ii)m=k 两者相同

(iii)m=无穷大，Algo2更快。

*第二种方法与第一种方法相比较简单，只需对两者取对数，但不要忽略多个常数。

             Algo 1=log n

             Algo 2=sqr(n)

             keep log n =x

             Any poly>its log


   O(sqr(n))>o(logn)

- MAYANK TYAGI

0

首先，将渐近复杂度与 N 约束混合比较并不完全正确。例如，我可以说：

O(n^2) 比 O(n * log(n)) 更慢，因为大 O 符号的定义将包括 n 无限增长。
对于特定的 N，只需比较 N^2 * ALGORITHM_CONSTANT 和 N * log(N) * ALGORITHM_CONSTANT 即可确定哪个算法更快，其中 ALGORITHM_CONSTANT 取决于算法。例如，如果我们需要遍历数组两次才能完成工作，则渐近复杂度将为 O(N)，而 ALGORITHM_CONSTANT 将为 2。

此外，我想提到 O(N * log2N)（我假设基数为 2 的对数是 log₂N）实际上与 O(N * log(N)) 相同，因为它们具有相同的对数属性。

- Alexey Malev

0

我是一名数学家，所以我将尝试解释为什么对于小的n值，n^2比nlogn更快，使用一个简单的极限，当n-->0时：

lim n^2 / nlogn = lim n / logn = 0 / -inf = 0

因此，对于小的n值（在这种情况下，“小值”是存在于[1,99]中的n），nlogn比n^2更快，因为我们看到极限=0。但为什么n-->0？因为算法中的n可以取“大”值，所以当n<100时，它被认为是非常小的值，因此我们可以取极限n-->0。

- Κριτολαος Ψαρουδακης

在你的第一句话中，你是不是想说"对于小的n值为什么n^2比nlogn更快"？有些情况下（尤其是使用特定排序方法时），一种通常因为最坏情况下的N^2而在大N值下表现极差的排序方法，在某些小于特定数字的N值下实际上是首选方法。举一个非常简单的例子，一个最坏情况下是N^2的函数在N=1时可能比一个nlogn函数快100倍，所以在N达到某个特定值之前，nlogn不能成为首选方法。 - Jason Baumgartner

是的，谢谢您的纠正。我尝试从数学上找出为什么会发生这种情况，但像您提到的那样找到算法是证明它的更好方法。 - Κριτολαος Ψαρουδακης

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

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