python - python 中算法的时间复杂度 O(n log n)

Question

给定一个列表，假设“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) 但不幸的是它不是。

Answer 1

您正确地识别出它是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)。