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

标签 python time-complexity

给定一个列表,假设“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/

相关文章:

python - 使用 mitmproxy 内联脚本记录所有 http 请求

javascript - 在 JavaScript 中创建省略索引的数组结构

java - 查找已排序循环整数数组的起点索引

algorithm - 图算法的复杂性对边权重的依赖性?

python - 如何在 django 模板中对 strftime ('%I:%M %p' ) 的 Python 列表进行排序?

python - 如何根据某些条件连接 pandas 列中的两个单元格?

python - SqlAlchemy 的 models.Manager 的等价物

python django 从命令加载缓存 TfidfVectorizer 并在 View 中使用

math - 通过简化分母获得时间复杂度?

algorithm - 证明一般树的树遍历算法的时间复杂度