yield from在树遍历中的时间复杂度是多少？

Question

yield from在树遍历中的时间复杂度是多少？

5

深度优先树遍历的一个例子：

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)

如果我根本不使用yield或yield from，那么树遍历的时间复杂度只有O(n)。

我想知道我是否误解了yield的工作方式，或者编写这样的递归生成器是否可行。

- Justin Li

你的公式中 Θ(n) 不应该是 Θ(1) 吗？在平衡树中，一个节点的子节点数量不是恒定的吗？ - DYZ

@DYZ 我认为它应该是Θ(n)。它并没有传递子代的数量，而是从所有子代中传递了“yield”语句。 - Justin Li

“所有后代”是否包括后代的后代等？（我认为不包括。）如果不包括，则仍然是一个常量。 - DYZ

@DYZ它包括子节点的后代，因为每个节点都会做两件事：(1)将自己提供给其调用者 (2)将其子节点及其子节点的后代提供给其调用者等等... - Justin Li

哦，你说得对。那么确实是O(n log n)，因为你基本上将遍历结果委托给了根节点，而不是在本地使用它们。 - DYZ

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Omada · Accepted Answer

从官方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)的开销，但并没有听起来那么糟糕。