수확량을 이용한 트리 순회의 시간 복잡도는 얼마입니까?

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)이 노드는 모든 yield을 통과하기 때문에

Θ(n) 존재 그것의 자손에서부터 부모에게 전달되었다. 그리고 위의 공식에서 파생 된 시간 복잡도는 다음과 같습니다

O (nlogn) 나는 모든 yield 또는 yield from를 사용하지 않는 경우

그러나, 트리 탐색의 시간 복잡도는 O(n)입니다.

내가 yield의 작동 방식을 잘못 이해했는지 또는 이처럼 재귀 적 생성기를 작성하는 것이 쉽지 않은지 궁금합니다.

yield from의 공식 파이썬 3.3 릴리스에서

Answer 1

: 발전기의 긴 체인이있는 경우 특수 구문을 사용 https://www.python.org/dev/peps/pep-0380/

최적화 에 대한 가능성을 열어. 이러한 체인은 반복적으로 트리 구조를 탐색 할 때 인스턴스에 대해 발생할 수 있습니다. 오버 헤드 을 다음()을 호출하고 체인을 아래로 올린 후 은 최악의 경우 인 O (n ** 2)가되는 O (n) 연산이 될 수 있습니다.

가능한 전략은 생성기에 위임 대상을 보유하기위한 개체 인 개체를 추가하는 것입니다. 다음() 또는 send() 호출이 생성기에서 이루어지면이 슬롯이 먼저 검사되고 비어있는 경우 이면 참조하는 생성기가 으로 대신 재개됩니다. StopIteration을 발생 시키면 슬롯이 지워지고 기본 생성기가 다시 시작됩니다.

이렇게하면 파이썬 코드를 실행하지 않는 C 함수 호출 체인의 위임 오버 헤드가 줄어 듭니다. 가능성이있는 향상은 루프에서 발전기의 전체 체인을 통과하여 끝에있는 타이머를 직접 재개하는 것이지만 StopIteration 처리가 더 복잡합니다.

yield from은 아직 트리를 가로 지르는 과정이 필요합니다. 그러나이 이동은 파이썬 대신 C로 된 인터프리터에 의해 수행됩니다.기술적으로는 여전히 O (n) 오버 헤드이지만 소리가 나쁘지는 않습니다.