`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
        )

此函数返回num_elements几何级数的第一个开始start并乘以multiplier每次。很容易看出最后一个元素将通过一个 yield-statement 和num_elements-1yield-from-statements传递。这是否有功能O(num_elements)的时间复杂度，还是有O(num_elements**2)时间复杂度由于嵌套产量从语句深度0，1，2，...，的“阶梯” num_elements-2，num_elements-1？

---

编辑：我想出了一个更简单的代码片段来演示我的要求。

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 + length of iterable)，还是O(depth * length of iterable)？

Answer 1

我可以发誓有一个优化来缩短这些类型的yield from链，但测试显示没有这样的优化，而且我在我认为实现优化的地方也找不到任何东西。

链的每一层上的生成器yield from必须单独暂停和恢复，以在链上和下传递值yield。send你的函数有O(num_elements**2)时间复杂度。此外，一旦调用堆栈深度达到 1000，就会发生堆栈溢出。