big-o - O(logn)和O(nlogn)之间的区别

Question

我正在为软件开发面试做准备，在区分O(logn)和O(nLogn)之间的区别时，我总是遇到问题。谁能通过一些例子向我解释或与我分享一些资源。我没有要显示的代码。我了解O(Logn)，但我不了解O(nlogn)。

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操作。在倒数第二次迭代中，大小为n/4的片段(4)的数量是其两倍。对于两对大小为n/4的每对，我们将其合并在一起，这需要一对对的n/2操作(对中每个元素一个，就像之前一样)，即两对的n操作。

从这里，我们可以推断出我们的mergesort的每个级别都需要n操作进行合并。因此，big-O复杂度是n乘以级别数。在最后一级，我们要合并的块的大小为n/2。在此之前，它是n/4，在该n/8之前，依此类推。您必须将1除以2多少次才能获得n？ 1。所以我们有log(n)级别。因此，我们的总运行时间为log(n)，O(n (work per level) * log(n) (number of levels))工作n倍。