深度优先树遍历的一个例子:
我知道
我想知道我是否误解了
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
的工作方式,或者编写这样的递归生成器是否可行。