O(logn)和O(nlogn)的区别

Question

我正在为软件开发面试做准备，总是很难区分O(logn)和O(nLogn)之间的差异。有人可以用一些例子或资源与我分享吗？我没有任何代码可展示。我理解O(Logn)，但我还没有理解O(nlogn)。

- Vagabond

---

这与O(1)和O(n)之间的差异或O(n)和O(n^2)之间的区别相同。 - melpomene

请查看 https://www.quora.com/How-are-O-logn-and-O-nlogn-calculated - B. Shefter

你仍需要学习很多。O(..) 描述了你的算法复杂度。简单来说，你可以将其想象为完成 n 个输入的算法所需的时间，如果是 O(n)，则需要 n 秒完成，如果是 O(logn)，则需要 logn 秒完成，而 O(nlogn) 则需要 n*logn 秒。O(1) 表示无论 n 多大，算法的成本都是恒定的。 - Khoa Nguyen

Answer 1

把它看做是O(n*log(n))，即“进行log(n)次n的工作”。例如，在长度为n的排序列表中搜索元素的时间复杂度是O(log(n))。如果在n个不同的排序列表中搜索元素，每个列表都有长度n，则时间复杂度为O(n*log(n))。

请记住，O(n)相对于某个实际数量n被定义。这个数量可以是列表的大小，也可以是集合中不同元素的数量。因此，O(...)中出现的每个变量都代表着一些交互作用来增加运行时间。O(n*m)可以写成O(n_1+n_2+...+n_m)，并表示同样的含义：“进行n和m次操作”。

让我们以mergesort为例说明。对于n个输入元素：在我们排序的最后一个迭代中，我们有两个大小为n/2的输入半部分，并且每个半部分都已经排序好了。我们所要做的就是将它们合并在一起，这需要n个操作。在倒数第二个迭代中，我们有两倍的块（4个），每个大小为n/4。对于我们的两对n/4大小的对，我们将它们合并在一起，这需要一对n/2次操作（与之前一样，每个对中的每个元素都需要1个操作），即两对需要n次操作。

从这里，我们可以推断出每个归并排序级别需要n个操作来合并。因此，大O复杂度为n乘以级别数。在最后一层中，我们要合并的块的大小是n/2。在此之前，是n/4，再之前是n/8，以此类推，一直到大小为1。你必须将n除以2多少次才能得到1呢？log(n)次。所以我们有log(n)级别。因此，我们的总运行时间是O(n (每个级别的工作量) * log(n) (级别数))，n次工作log(n)次。

- MyStackRunnethOver

---

谢谢你的回答。我有一个跟进问题要问你。你可以证明归并排序的时间复杂度是O(nLogn)吗？请在解释原因时不要使用主定理。如果你认为有用的话，请分享任何资源。 - Vagabond

不用谢。我可以直接证明，但这并不适用于此问题，并且在Google上有成千上万的其他证明。相反，我会在我的问题中加入归并排序作为一个例子，我认为这将有助于向您展示如何证明其运行时间。 - MyStackRunnethOver

是的，我觉得没有必要了。我的基础知识已经掌握得不错了。我会从这里开始工作。非常感谢你的帮助。 - Vagabond

我也在努力理解这个问题。也许是因为很多人说O(n log n)可以简化为O(log n)，所以我不理解。但我不同意，因为O(n log n)的时间复杂度比O(n)高，而(log n)的时间复杂度比O(n)低。例如，考虑O(1000 * log base 2 1000)，它将是(1000 * 10)，即10,000。因此，在这种情况下，O(n)是1000，O(log n)是10，而O(n log n)是10,000。对我来说，这是一个显著的差异。 - FernandoZ

@FernandoZ "因为很多人认为O(n log n)可以简化为O(log n)" -> 他们是错的。你的直觉不错，但实际上，并非对于任何给定的 n 值差异使他们错误。问题在于当 n 趋近无穷大时 (n*log(n) / log(n)) 的极限值是无穷大而非常数。这意味着随着 n 趋近无穷大，n*log(n) 将会比 log(n) 要快速增长。任何特定值无关紧要的原因是 O(n + 999,999,999) == O(n * 999,999,999) == O(n) - 差异值可能由常数引起，因为它们不会改变极限计算。 - MyStackRunnethOver