`yield from` 的时间复杂度是 O(1) 吗？

Question

考虑以下代码片段。

from typing import Iterable


def geometric_progression(
    start: float, multiplier: float, num_elements: int
) -> Iterable[float]:
    assert num_elements >= 0
    if num_elements > 0:
        yield start
        yield from geometric_progression(
            start * multiplier, multiplier, num_elements - 1
        )

该函数返回以start为起始点，每次乘以multiplier的等比数列中的前num_elements个元素。很容易看出，最后一个元素将通过一个yield语句和num_elements-1个yield-from语句传递。这个函数的时间复杂度是O(num_elements**2)还是O(num_elements)？这取决于嵌套了深度为0、1、2......num_elements-2、num_elements-1的yield-from语句的“梯形”结构。

---

编辑：我已经想出了一个更简单的代码片段来说明我的问题。

from typing import Iterable, Any

def identity_with_nested_yield_from(depth: int, iterable: Iterable[Any]) -> Iterable[Any]:
    assert depth >= 1
    if depth == 1:
        yield from iterable
    else:
        yield from identity_with_nested_yield_from(depth-1, iterable)

这个函数的时间复杂度是O(depth + iterable的长度)还是O(depth * iterable的长度)？

- CrabMan

Answer 1

我本以为有一种优化方法可以捷径这些yield from链，但测试结果表明没有这样的优化方法。在我认为已经实施了这种优化方法的地方，我也无法找到任何相关信息。

在yield from链的每个级别上，生成器必须单独暂停和恢复以传递yield和send值。你的函数时间复杂度为O(num_elements**2)，并且在调用栈深度达到1000时会导致堆栈溢出。

- user2357112

Answer 2

yield from等同于一个包含response = yield child.send(response)的循环，再加上错误传播和处理。在迭代时，response始终是None，不会传播或处理任何错误。这相当于一个for循环。

# `yield from child` without error handling/response
for x in child:
    yield x

因此，每个yield from都具有迭代其参数的时间/空间复杂度。将大小为n的yield from堆叠m次，因此具有O(nm)的时间复杂度。

- MisterMiyagi