为什么O(n)比O(nlog(n))更好？

Question

我刚刚发现了一个奇怪的事实，在普通的数学中，n*logn 将小于 n，因为 log n 通常小于 1。

那么为什么 O(nlog(n)) 大于 O(n) 呢？（即为什么认为 nlogn 花费的时间更长）

大 O 表示法遵循不同的系统吗？

- Ritveak

---

对于每个n>10（以10为底），log n都大于1。 - Bernhard Barker

基本上，nlogn 中的 log 是以 2 为底的。因此对于任何 n >= 2，都有 logn >= 1。就是这样... - Redu

Answer 1

原来，我误以为Logn小于1。

后来问了一些前辈，我今天才知道，如果n的值很大（通常在我们考虑最坏情况即Big O的时候），logn可能大于1。

所以，O(1) < O(logn) < O(n) < O(nlogn)是正确的。

（我本来认为这是个愚蠢的问题，准备把它删除，但是我后来意识到，没有愚蠢的问题，可能还有其他人会感到困惑，所以我把它留在这里。）

- Ritveak

---

这绝不是一个愚蠢的问题！我一直对此感到困惑，直到现在。看起来关键在于“基础”。 - Naseem Ahamed

这在长时间离开数学后学习算法时特别有意义。 - sankar

将以下与编程有关的内容从英语翻译成中文。仅返回已翻译的文本：这不是一个有用的答案。应该编辑原始问题并提供相关信息。 - PeJota

谢谢你发表这个问题。我也有同样的问题，所以来谷歌搜索了一下。多亏了你，我的搜索没有花费太多时间。 - undefined

Answer 2

...因为log n始终小于1是一个错误的前提。

事实上，对于所有n > b，log_b n > 1。例如，log₂ 32 = 5。

口语化地讲，您可以将log n视为 n 的位数。如果 n 是一个8位数字，则 log n ≈ 8。对于大多数的 n 来说，对数通常大于1，因为大多数数字都有多个位数。

- John Kugelman

Answer 3

以下是常见时间复杂度的图表

O(n*log(n)) 在 n>2 (以2为底的对数)时明显大于 O(n)

一个简单的记忆方法可能是，举两个例子

1. 想象一下具有对数 N 时间复杂度的二分查找算法：O(log(N))
2. 如果在二分查找的每个步骤中，您需要遍历包含 N 个元素的数组
3. 该任务的时间复杂度将为 O(N*log(N))
4. 这比遍历数组一次的工作量更大：O(N)

- Caleb Hillary

Answer 4

在 Desmos (https://www.desmos.com/calculator) 或任何其他网站上画出函数图像并查看 n 较大时的结果 (y=f(n))。建议查看较大的 n 值，因为对于较小的 n 值，程序不会有时间问题。方便起见，我在下面附上了一个图表，您可以尝试其他以 log 为底数的情况。

其中红色代表时间 = n，蓝色代表时间 = nlog(n)。

- randomUser

Answer 5

在计算机领域，对数的底数为2而非10。因此log(2)等于1，而对于n>2时，log(n)是大于1的正数。 只有在log(1)的情况下，其值小于1，否则它的值都大于1。

- Amit

Answer 6

如果 n 大于 b，那么 log(n) 可能大于 1。但这并不能回答你的问题，为什么 O(n*logn) 大于 O(n)。

通常情况下，底数小于 4。所以对于更大的 n 值，n * log(n) 就变得比 n 更大了。这就是为什么 O(nlogn) > O(n) 的原因。

- Ujjawal Kumar

---

通常基数始终小于4。例如，在八叉树中，基数是8。我承认，在计算机科学课程中，你将使用的最常见的数据结构的基数都小于或等于4，但现实世界是不同的。无论如何，当你谈论算法分析时，基数通常比你考虑的项数要小得多，因此可以假设log（n）大于1，无论基数为何。 - Jim Mischel

Answer 7

这张图可能会有所帮助。log(n) 的增长速度比 n 更快，并且对于大于对数的底数的 n，它大于 1。 https://dev59.com/4Wsz5IYBdhLWcg3wiIWe#7830804

- sxpg

Answer 8

无论两个函数在小的 n 值上表现如何，当 n 足够大时，它们将相互比较。理论上，存在一个 N，对于每个给定的 n > N，则有 nlogn >= n。如果选择 N=10，那么 nlogn 总是大于 n。"Original Answer" 翻译成 "最初的回答"。

- agtabesh

Answer 9

断言并不总是准确的。当n很小时，(n^2)需要比(log n)更多的时间，但当n很大时，(log n)更为有效。对于小值，(n^2)的增长速率小于(n)和(log n)，因此我们可以说(n^2)更有效，因为它需要比(log n)更少的时间，但随着n的增加，(n^2)急剧增加，而(log n)的增长速率小于(n^2)和(n)，因此(log n)更有效。

- Shravel Sharma

Answer 10

对于log n的较高值，它变得大于1。由于我们考虑了所有可能的n值，我们可以说在大多数情况下log n大于1。因此，我们可以说O(nlogn) > O(n)（假设有更高的值）。

- vihaan nama