जटिलता

Question

समारोह:

MAX-HEIGHT(node) 
    if(node == NIL) 
     return -1; 
    else 
    return max(MAX-HEIGHT(node.leftChild), MAX-HEIGHT(node.rightChild)) + 1; 

मान लीजिए कि हमें एन नोड्स है और हम साथ MAX-HEIGHT(root).

मुझे लगता है कि इस समारोह की जटिलता हे है (फ़ंक्शन को कॉल करें कि एन) क्योंकि हमें प्रत्येक नोड पर जाने की जरूरत है। हालांकि, मुझे यकीन नहीं है और मैं इसे दृढ़ता से साबित नहीं कर सकता। कृपया मुझे एक अच्छा स्पष्टीकरण दें कि यह ओ (एन) क्यों है, यदि यह ओ (एन) है, और क्यों नहीं यदि यह ओ (एन) नहीं है।

तो, जटिलता क्या है?

धन्यवाद।

Answer 1

औसत मामले में, एक संतुलित द्विआधारी पेड़

T(n) = 2T(n/2) + Θ(1); 

हर पुनरावर्ती कॉल आप आधे आकार के दो समस्याओं देता है के लिए। मास्टर प्रमेय द्वारा, यह टी (एन) = Θ (एन)

का सबसे खराब मामला है, जहां प्रत्येक नोड में केवल एक बच्चा होता है।

T(n) = T(n-1) + Θ(1) 

कौन सा टी (एन) का मूल्यांकन = Θ (एन)

Answer 2

सवाल आप से पूछना चाहिए:

• क्या एन मेरी डेटा संरचना में प्रतिनिधित्व करता है (एक द्विआधारी पेड़)
• मेरी संरचना की ऊंचाई निर्धारित करने से पहले मुझे कितने एन को जाना होगा।

यहां, एन आपके पेड़ में नोड्स की संख्या का प्रतिनिधित्व करता है, और आपको ऊंचाई लौटने से पहले उन सभी के माध्यम से जाना होगा।

कारण है कि (एन)