कैसे बाइनरी सबट्री

Question

यह समस्या पुस्तक कोडिंग साक्षात्कार क्रैकिंग से है ढूँढना के लिए अंतरिक्ष जटिलता की गणना करने के लिए। मुझे समाधान की अंतरिक्ष जटिलता को समझने में परेशानी है।

समस्या:
आप दो बहुत बड़ी द्विआधारी पेड़: टी 1, नोड्स के लाखों लोगों के साथ, और टी 2, नोड्स के सैकड़ों के साथ। यह निर्धारित करने के लिए एक एल्गोरिदम बनाएं कि टी 2टी 1 का उपखंड है।

समाधान (जावा में):

public static boolean containsTree(TreeNode t1, TreeNode t2) { 
    if (t2 == null) 
     return true; // The empty tree is a subtree of every tree. 
    else 
     return subTree(t1, t2); 
} 

/* Checks if the binary tree rooted at r1 contains the binary tree 
* rooted at r2 as a subtree somewhere within it. 
*/ 
public static boolean subTree(TreeNode r1, TreeNode r2) { 
    if (r1 == null) 
     return false; // big tree empty & subtree still not found. 
    if (r1.data == r2.data) { 
     if (matchTree(r1,r2)) return true; 
    } 
    return (subTree(r1.left, r2) || subTree(r1.right, r2)); 
} 

/* Checks if the binary tree rooted at r1 contains the 
* binary tree rooted at r2 as a subtree starting at r1. 
*/ 
public static boolean matchTree(TreeNode r1, TreeNode r2) { 
    if (r2 == null && r1 == null) 
     return true; // nothing left in the subtree 
    if (r1 == null || r2 == null) 
     return false; // big tree empty & subtree still not found 
    if (r1.data != r2.data) 
     return false; // data doesn’t match 
    return (matchTree(r1.left, r2.left) && 
      matchTree(r1.right, r2.right)); 
} 

किताब में लिखा इस समाधान का अंतरिक्ष जटिलताहे (लॉग (एन) + लॉग (एम)) जहां मीटर है टी 1 में नोड्स की संख्या (बड़ा पेड़) और टी 2 में नोड्स के एन संख्या।

मेरे लिए, यह प्रतीत होता है समाधान है, क्योंकि "सबट्री" समारोह लॉग (एन) पुनरावर्ती कॉल है हे (लॉग (एम) * लॉग (एन)) अंतरिक्ष जटिलता है और प्रत्येक पुनरावर्ती कॉल निष्पादित करता है "matchTree कि "फ़ंक्शन जो लॉग (एम) रिकर्सिव कॉल को ट्रिगर करता है।

क्यों इस समाधान हे (लॉग (एन) + लॉग (एम)) जटिलता है?

Answer 1

चूंकि हम ढेर पर कोई वस्तु नहीं बना रहे हैं, इसलिए अंतरिक्ष जटिलता ढेर का आकार है। तो सवाल यह नहीं है कि कितने कुल कॉल होते हैं, लेकिन ढेर कितना बड़ा हो सकता है।

containsTree() केवल कॉल कर सकते हैं subTree(), subTree() खुद या matchTree() कॉल कर सकते हैं, और matchTree() केवल खुद फोन कर सकते हैं। किसी भी बिंदु जहां matchTree() बुलाया गया है पर तो, ढेर इस तरह दिखता है:

[containsTree] [subTree] ... [subTree] [matchTree] ... [matchTree] 

यही कारण है कि आप अंतरिक्ष जटिलताओं यहाँ गुणा नहीं है: matchTree() छुट्टी करने के लिए उन कॉल जबकि subTree() की प्रत्येक कॉल matchTree() कॉल कर सकते हैं, subTree() से पहले ढेर recursing जारी है।

"सही जवाब"

तो सवाल है, तो पेड़ संतुलित हैं निर्दिष्ट नहीं करता है, तो की तर्ज पर

विश्लेषण एक असली बुरी से बुरी हालत विश्लेषण ग्रहण करेंगे वे नहीं हो सकता है। हालांकि, आप और पुस्तक मान रहे हैं कि वे हैं। हम एक तरफ टी 1 की गहराई कह कर बाद के लिए इस सवाल का सेट कर सकते हैं ग है, और टी 2 की गहराईघ है। गहे (लॉग (एम))अगर टी 1 संतुलित है, और हे (एम) अन्यथा है। टी 2 के डी के लिए वही बात।

matchTree() के लिए सबसे खराब मामला है, हे (घ) है दूर का यह टी 2 की ऊंचाई होगा recurse कर सकता है।

subTree() के लिए सबसे खराब मामला है हे (ग) अपनी प्रत्यावर्तन के लिए, दूर का है क्योंकि यह, टी 1 की ऊंचाई, प्लस matchTree() बुलाने की लागत होगा recurse सकता हे (ग + कुल डी)।

और containsTree() बस, subTree() बुला की चोटी पर एक निरंतर जोड़ती है, ताकि अंतरिक्ष जटिलता नहीं बदलता है।

तो दोनों टी 1 और टी 2 संतुलित कर रहे हैं, जगह ग और घ से आप देख सकते हैं कि हे (लॉग (एम) + लॉग (एन)) उचित लगता है। "सही जवाब"

साथ

समस्याएं जैसे कि मैंने पहले कहा, यह मान लेना द्विआधारी पेड़ संतुलित हैं जब तक आप एक तथ्य यह है कि वे के लिए पता सही नहीं है। तो एक बेहतर जवाब ओ (एम + एन) हो सकता है।

लेकिन प्रतीक्षा करें! सवाल बताता है कि का आकार टी 2टी 1 के आकार से कम है। इसका मतलब है कि nहे (एम) है, और लॉग (एन)हे (लॉग (एम)) है। तो हम एन के बारे में चिंता करने में समय बर्बाद क्यों कर रहे हैं?

यदि पेड़ संतुलित हैं, तो अंतरिक्ष जटिलता केवल ओ (लॉग (एम)) है। सामान्य मामले में जहां आप नहीं जानते कि संतुलित क्या है या नहीं, वास्तविक उत्तर ओ (एम), बड़े पेड़ का आकार होना चाहिए।