Имеет ли `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 прогрессии геометрии c, начиная с start и умножая на multiplier каждый раз. Легко видеть, что последний элемент будет пропущен через один оператор yield и num_elements-1 yield-from-операторов. Имеет ли эта функция O(num_elements) временную сложность или O(num_elements**2) временную сложность из-за "лестницы" вложенных операторов yield-from-глубин 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.

Answer 2

yield from является формально эквивалентным для l oop из response = yield child.send(response), плюс распространение ошибок и обработка. При использовании в итерации response всегда равно None, и ошибки не распространяются / обрабатываются. Это эквивалентно for l oop.

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

Таким образом, каждый yield from имеет временную / пространственную сложность повторения своего аргумента. Таким образом, сложение yield from размером n потомка всего m раз имеет временную сложность O(nm).