गहराई-प्रथम पेड़ ट्रेवर्सल का एक उदाहरण:उपज का उपयोग करके पेड़ के ट्रैवर्सल की समय जटिलता क्या है?
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 नीचे से ऊपर तक उसकी जड़ के लिए हर नोड से पारित हो जाएगा, और हम (पुनरावृत्ति से चल रहा है समय का वर्णन कर सकते यह सादगी के लिए एक द्विआधारी पेड़ है मान , लेकिन यह विचार एक ही है):
टी (एन) = 2 * टी (एन/2) + Θ (एन)
Θ(n) मौजूद है क्योंकि इस नोड सभी yield पारित करने के लिए है अपने संतानों से अपने माता-पिता को पास कर दिया। और समय जटिलता उपरोक्त सूत्र से प्राप्त होता है:
ओ (nlogn)
हालांकि, पेड़ ट्रेवर्सल के समय जटिलता केवल O(n) है अगर मैं yield या yield from बिल्कुल प्रयोग नहीं करते।
मुझे आश्चर्य है कि क्या मुझे गलत लगता है कि yield काम करता है या इस तरह एक पुनरावर्ती जनरेटर लिखना संभव नहीं है।
आपके फॉर्मूला में Θ (एन) नहीं होना चाहिए Θ (1)? एक संतुलित पेड़ स्थिर में एक नोड की संतान की संख्या नहीं है? – DyZ
@DYZ मुझे लगता है कि यह Θ (एन) होना चाहिए। यह संतानों की संख्या को पारित नहीं करता है, लेकिन अपने सभी संतानों से 'उपज' बयान पास करता है। –
क्या 'इसके सभी संतान' में संतान की संतान शामिल है, आदि? (मुझे लगता है कि यह नहीं करता है।) यदि नहीं, तो यह अभी भी स्थिर है। – DyZ