时间复杂性问题:为什么它是O(n log n)

Question

有人能解释为什么这是O(n log n)而不是O(n^2)吗？我的想法是，if语句是n倍，else是log n，所以你在两者之间选择最坏的情况，在这种情况下是O(n)，所以将它与外循环O(n)相乘，使其成为O(n^2)，但显然是O(n log n)，我不知道怎么做。

for i in range( len(nums_lst)):
if i < 10:
for k in range( len(nums_lst)):
print(nums_lst[0])
else:
j = 1
while j < len(nums_lst):
print(nums_lst[0])
j *= 2

Answer 1

如果用这种方式重写，会更容易看到发生了什么，这在n≥10:时是等效的

for i in range(10):
for k in range(len(nums_lst)):
print(nums_lst[0])
for i in range(10, len(nums_lst)):
j = 1
while j < len(nums_lst):
print(nums_lst[0])
j *= 2

步骤数为10n+(n−10(logn-。

Answer 2

对于较大的n值，将忽略if:条件。在else:内部，同时循环继续运行-

j=1，j=2，j=4。。。并且j＝2^m，其中2^m<＝n

因此循环总数为m+1。m=log n

现在时间复杂度是O(n * log n)

for i in range( len(nums_lst)):  # Time complexity O(n)
if i < 10:
...
else:
j = 1
while j < len(nums_lst):  # Time complexity O(logn)
print(nums_lst[0])
j *= 2

Answer 3

Big-O时间复杂度是算法如何缩放的渐近度量。它关注的是算法如何随着n接近无穷大而缩放，而不是n的特定值。

当nums_list包含的项目少于10个时，复杂性为O(n^2(，但由于nums_list的大小可忽略不计。

大得多的样本将由j指数接近len(nums_list)的其他分支表示。因此，内部循环的复杂性是O(logn(。

因此，将两者相乘，我们得到O(n*logn(。

Answer 4

对于较大的输入，渐近符号始终是性能的度量。因此，如果你要计算时间复杂性，请选择Big-O(即最坏情况(。

由于i<10很小，我们可以忽略并取其他部分，其时间复杂度为O(log n到基数2(，并且循环的外部具有O(n(的T.C。

因此O(n log n(。

Answer 5

此算法将为O(nlog(n((，因为执行if块的几率非常低，因为在大多数情况下，列表将包含10个以上的元素。只有在少数更糟糕的情况下，列表的元素将少于10个，时间复杂性将为O(n^2(。因此，总的来说，该算法将具有O(nlog(n((的时间复杂度。