给定一个列表,假设“x”的长度为n,以下算法的时间复杂度是多少?
def foo(x):
n = len(x)
if n <= 1:
return 17
return foo(x[:n//2]) + foo(x[n//2:])
答案是:
O(n log n)
但我不明白为什么? 我很难计算出我们使用递归的最后一行,我知道它每次都会将列表的长度减半,因此它的 O(log n) ,但它会在每次迭代中添加另一个递归,这也是 O(log n )每次我都认为它是 O(log n log n) 但不幸的是它不是。
最佳答案
您正确地识别出它是O(log n),但您无法识别它是什么。 it 是达到基本情况所需的步骤数。由于每次将列表切成两半时,每次调用 foo
时,您所使用的列表的大小都是刚刚的列表的一半。因此,需要 O(log n) 步骤才能达到基本情况。
下一个问题是:每一步做了多少工作?第一步,列表被分成两半,这需要 n
内存副本。在第二步中,两个大小为n/2
的列表被分成两半。完成的工作量保持不变!从一步到下一步,您要削减的每个列表的大小一半(由于调用foo(n//2)
),但您必须的列表数量对 double 执行此操作(因为您递归地调用foo
两次)。因此,对于每一步,您总是要做 O(n) 的工作。
O(log n) 步骤 * 每一步工作 O(n) = 总共 O(n log n)。
关于python - python 中算法的时间复杂度 O(n log n),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51080783/