使用yield的树遍历的时间复杂度是多少？

Question

深度优先树遍历的示例:

class Node:
    def __init__(self, value):
        self._value = value
        self._children = []

    def add_child(self, child):
        self._children.append(child)

    def __iter__(self):
        return iter(self._children)

    def depth_first(self):
        yield self
        for c in self:
            yield from c.depth_first()

据我所知,yield from它不会立即消耗发生器,而是yield向上传递给它的调用者.

但是这个传递过程仍然存在,因此yield将从每个节点一直传递到它的根,我们可以通过重复来描述运行时间(假设它是一个简单的二叉树,但想法是一样的):

T(n)= 2*T(n/2)+Θ(n)

?(n)存在是因为此节点必须yield将从其后代传递的所有内容传递给其父节点.从上面的公式得出的时间复杂度是:

O(nlogn)

然而,树遍历的时间复杂性只有O(n)在我不使用yield或根本不使用yield from时.

我想知道我是否误解了如何yield工作或者编写这样的递归生成器根本不可行.

Answer 1

来自官方 Python 3.3 版本yield from：https://www.python.org/dev/peps/pep-0380/

当存在长链生成器时，使用专门的语法为优化提供了可能性。例如，当递归遍历树结构时，可能会出现此类链。在链中上下传递next () 调用和生成值的开销可能会导致本应是 O(n) 的操作在最坏的情况下变成 O(n**2)。

一种可能的策略是向生成器对象添加一个槽来保存被委托的生成器。当对生成器进行next () 或 send() 调用时，首先检查此槽，如果它非空，则恢复它引用的生成器。如果它引发 StopIteration，则槽被清除并恢复主生成器。

这将减少不涉及 Python 代码执行的 C 函数调用链的委托开销。一种可能的增强是在循环中遍历整个生成器链并直接恢复最后的生成器，尽管 StopIteration 的处理更加复杂。

看来yield from还是需要遍历树。但这种遍历是由 C 语言而不是 Python 中的解释器完成的。因此从技术上讲，它仍然是 O(n) 开销，但并不像听起来那么糟糕。