"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语句和num_elements-1yield from语句传递。该函数是否具有O(num_elements)时间复杂度，还是由于深度为0、1、2…的语句的嵌套收益率的"阶梯"而具有O(num_elements**2)时间复杂度。。。，num_elements-2，num_elements-1？

---

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

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的深度，它就会发生堆栈溢出。

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)的时间复杂度。