Python 生成器时间复杂度 log(n)

Question

在 python3 范围内借助发电机构建

对数时间 — O(log n) 当算法在每个步骤中减少输入数据的大小时，据说该算法具有对数时间复杂度。例如，如果我们首先在生成器的帮助下打印前 10 位数字，我们将得到一个元素，因此必须处理剩余的 9 个元素，然后是第二个元素，因此必须处理剩余的 8 个元素

for index in range(0, len(data)):
    print(data[index])

当我检查 url 它说 O(n).

因为每次它只生成一个输出，因为我们需要做 __next__ 它将是每次 1 单位成本。

我能得到解释吗

Answer 1

对数时间复杂度的解释是错误的。

如果将输入的大小减少一小部分，而不是固定数量，您将获得对数复杂度。例如，二进制搜索在每次迭代时将大小除以 2，因此它是 O(log n)。如果输入大小为 8，则需要 4 次迭代，将大小加倍至 16 只会将迭代次数增加至 5。