我正在为软件开发面试做准备,总是很难区分O(logn)和O(nLogn)之间的差异。有人可以用一些例子或资源与我分享吗?我没有任何代码可展示。我理解O(Logn),但我还没有理解O(nlogn)。
我正在为软件开发面试做准备,总是很难区分O(logn)和O(nLogn)之间的差异。有人可以用一些例子或资源与我分享吗?我没有任何代码可展示。我理解O(Logn),但我还没有理解O(nlogn)。
把它看做是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)
次。
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