时间复杂度问题 BigO 表示法。 O(n) vs O(n log n)

Question

我刚刚进入大 O 表示法和时间复杂度，并且遇到了 O(n) 与 O(log n) 与 O(n log n) 的问题

具体来说，我正在将 O(5 log n) 与 O(n) 进行比较。我知道 O(log n) > O(n) > O(n log n)。我想我对 n 在 O(n log n) 中代表什么感到困惑

例如，O(5 log n) 将比 O(n) 更快，因为 5 在规模上并不重要。

我的理解正确吗？

这是我第一次在 stackoverflow 上发帖，所以如果这里有任何做得不对的地方，我很抱歉。

我最近正在研究这个问题，我想确保我理解。我觉得这是正确的，但我对此很陌生。

Answer 1

我在 AustinCommunityCollege 网站上发现此资源信息非常丰富。

适用于非常大的 n 值。这种“复杂性分析”试图用简单的公式近似来表征数据元素数量和资源使用（时间或空间）之间的关系。

符号涉及非常大的 N 值会发生什么

Answer 2

我对 n 在 0(n log n) 中代表什么感到困惑

这是输入的一些相关“措施”。它可能是字面上的输入，就像算法计算数字 𝑛 的阶乘一样。它可以是提供给算法的值的number，例如排序算法。它可以是树的高度、图中的节点数、一组输入值的范围（最大 - 最小）……等等，任何看起来对输入的size有用的指示。

0(5 log n) 将比 0(n) 更快，因为 5 在规模上并不重要。

确实，因子 5 与 Big Oh 表示法无关。但要小心有关“更快”的表述。复杂性与渐近行为有关，因此对于特定的输入大小范围，O(log𝑛) 算法实际上可能比 O(𝑛) 算法“慢”。您唯一可以确定的是，对于足够大的输入大小（但您不知道多大大），第一个算法会更快。

Answer 3

O(5 log n)

中，“5”只是一个可以忽略的常数因子，因此这与

O(1 log n)

相同，都是

O(log n)

。因此，使用

O(5 log n)

的算法与使用

O(log n)

的算法具有相同的复杂性。但这比拥有

O(n log n)

要好得多。（这与

O(5n log n)

相同，但我们再次忽略这里的 5）。

请注意，这仅适用于因子，不适用于所有常量：

O(n^2)

与

O(n^1)

明显不同。