大 O 运行效率疑惑

Question

O(n) 相对于 O(n log n) 是被认为更快的吗？如果我有一个包含循环的函数，其时间复杂度为 O(n)，然后在循环外使用归并排序（O(n log n)），那么总运行时间是否应该是 O(n log n)？

- xonegirlz

---

你的问题里有错别字吗？不太清楚 O(n log n) 是什么意思。 - Dusty

抱歉，我让问题有点不清楚。 - xonegirlz

Answer 1

“O(n)和O(n log n)哪个更快？”

直接来说不是，大O符号是关于算法的极限因素的，这与算法的可扩展性更有关系，而非速度。对于一个特定的数据集，您可以有一个时间复杂度为O(1)的例程，它比O(n ^ 2)的例程需要更长的时间，但前者的扩展性会更好。

话虽如此，一般而言，O(n)当然将比O(n log n)具有更好的可扩展性，并可能被认为是“更快”或“更好”的。

“如果我有一个O(n)和O(n log n)的循环函数，运行时间会是O(n log n)，我猜对吗？”

这里不太清楚您的意思 -

如果您的意思是您有一个带有2个函数的循环，例如：

Loop over N elements
    - Call O(n) function
    - Call O(n log n) function

那么总的限制因素将会是O(n^2 log n)。

(来自评论)

我的意思是归并排序（nlogn）在循环外面，所以仍然是O(nlogn)。

如果你想做这样的事情：

- Call O(n log n) function
- Loop over N elements
     - Process each element using O(1) algorithm

那么总体复杂度仍然是O(n log n)，因为这是限制因素。这是因为“O(n + n)”仍然是O(n)。

- Reed Copsey

Answer 2

O(n)在渐进上比O(n log n)“更好”或“更快”，没错。如果你有一个函数进行循环，而循环体调用了一个O(n log n)的函数n次，整体的复杂度就是O(n^2 log n)...除非我误解了你的问题。换句话说，对一个O(n log n)的操作进行n次会得到O(n * n log n) = O(n^2 log n)的复杂度。

- Patrick87

---

我的意思是归并排序（n log n）在循环外部，因此仍然是O（n log n）。 - xonegirlz

@xonegirlz：你能发一些代码让我理解你在说什么吗？抱歉我有点笨。 - Patrick87

Answer 3

O(n * log n)当然比O(n)更大。

O(n * n * log n) > O(n * n) > O(n * log n) > O(n) > O(1)

如此类推。

O(n + 1) = O(n)

O(2 * n) = O(n)

O(n + log n) = O(n)

O(n + n * log n) = O(n * log n)，这就是您的情况。

- Salvatore Previti

Answer 4

当N趋近于无穷大时，O(N)渐进地比N更快--但对于任何有限的N值，它可能会更慢、更快或相等。

我不太确定你在第二句话中想要问什么。如果你的意思是算法的一部分与N log N成正比，而另一部分与N成正比，那么是的，大O表示你可以忽略其他部分，只要它们被加到主要部分上，而不是乘以它。

- Jerry Coffin

Answer 5

随着n的增大，log n会无限增加。这意味着：

• O(log n) > O(1)，因此O(log n + 1) = O(log n)
• O(n log n + n) = O(n (log n + 1)) = O(n log n)

O()符号的整个概念是通过忽略除最大组件以外的所有内容来简化您的运行时公式。

另一方面，它还允许您忽略较大组件中的常数因子。因此，仅仅因为一个算法在大问题上渐进地更快，并不意味着它对于任何特定问题实际上更快...

- comingstorm