Độ phức tạp thời gian của việc chuyển cây bằng cách sử dụng năng suất từ ​​đâu?

Question

Một ví dụ về chiều sâu-đầu tiên cây traversal:

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() 

Tôi hiểu rằng yield from không tiêu thụ máy phát điện ngay lập tức, nhưng thay vì vượt qua yield lên để gọi nó.

Nhưng quá trình này của qua vẫn còn tồn tại, và do đó yield sẽ được truyền từ mỗi nút tất cả các con đường lên đến gốc của nó, và chúng ta có thể mô tả thời gian chạy bởi sự tái diễn (giả định nó là một cây nhị phân vì đơn giản , nhưng ý tưởng là như nhau):

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

Θ(n) tồn tại vì nút này phải vượt qua tất cả các yield được chuyển từ phần offsprings sang cha mẹ của nó. Và mức độ phức tạp thời gian bắt nguồn từ công thức trên là:

O (nlogn)

Tuy nhiên, mức độ phức tạp thời điểm duyệt cây chỉ O(n) là nếu tôi không sử dụng yield hoặc yield from ở tất cả.

Tôi tự hỏi liệu tôi có hiểu lầm cách hoạt động của yield hay không đơn giản là không thể viết một trình tạo đệ quy như thế này.

Answer 1

Từ chính thức Python 3.3 phát hành cho yield from: https://www.python.org/dev/peps/pep-0380/

Sử dụng một cú pháp đặc biệt mở ra những khả năng để tối ưu hóa khi có một chuỗi dài của máy phát điện. Các chuỗi như vậy có thể phát sinh, trong trường hợp , khi đệ quy đi qua một cấu trúc cây. Các chi phí trên khi chuyển các cuộc gọi tiếp theo() và giảm giá trị chuỗi có thể khiến hoạt động O (n) trở thành trường hợp xấu nhất , O (n ** 2).

Một chiến lược có thể là thêm một khe vào máy phát điện các đối tượng để giữ máy phát được ủy nhiệm. Khi một cuộc gọi tiếp theo() hoặc send() được thực hiện trên máy phát, trước tiên, vị trí này được chọn và nếu nó không trống, máy phát mà nó tham chiếu được tiếp tục thay thế. Nếu nó tăng StopIteration, khe sẽ bị xóa và máy phát điện chính được tiếp tục.

Điều này sẽ làm giảm chi phí của ủy quyền đối với một chuỗi cuộc gọi hàm số không liên quan đến việc thực thi mã Python. A có thể tăng cường sẽ là để đi qua toàn bộ chuỗi các máy phát điện trong một vòng lặp và trực tiếp tiếp tục một ở cuối, mặc dù việc xử lý StopIteration là phức tạp hơn sau đó.

Có vẻ như yield from vẫn yêu cầu vượt qua cây. Nhưng việc duyệt ngang đó được thực hiện bởi trình thông dịch trong C thay vì bằng Python.Vì vậy, về mặt kỹ thuật nó vẫn là một O (n) trên không, nhưng nó không phải là xấu như nó âm thanh.