फिबोनाची ढेर को कैस्केडिंग कटौती की आवश्यकता क्यों है?

Question

मैं 'परिचय से एल्गोरिदम' से एफ-ढेर सीख रहा हूं, और 'कमी-कुंजी' ऑपरेशन वास्तव में मुझे भ्रमित करता है - इसे 'कैस्केडिंग-कट' क्यों चाहिए?

तो आप इस कार्रवाई निकाल दिया जाता है:

1. मेकअप ढेर(), सम्मिलित(), न्यूनतम() और संघ() की लागत स्पष्ट रूप से अपरिवर्तित रहता है
2. निकालने मिनट() अब भी है हे (डी (एन)), क्योंकि ओ (एन (एच)) 'समेकित' ऑपरेशन में, अधिकांश रूट पेड़ों की लागत का भुगतान किया जा सकता है जब उन्हें मूल सूची में जोड़ा गया था, और शेष लागत ओ (डी (एन))
3. कमी-कुंजी(): स्पष्ट रूप से ओ (1)

डी (एन) के लिए, हालांकि मैं इसे ठीक से समझा नहीं सकता, मुझे लगता है कि यह अभी भी ओ (एलएनजी), cuz बिना 'कैस्केडिंग-कट' है, एक नोड को थोड़ी देर बाद रूट सूची में स्थानांतरित किया जा सकता है , और किसी भी नोड अपने पिता के तहत छुपा दक्षता को प्रभावित नहीं करता है। कम से कम, इससे स्थिति खराब नहीं होगी।

मेरी गरीब अंग्रेज़ी :(

किसी को भी मदद कर सकते हैं? धन्यवाद

Answer 1

व्यापक कटौती का कारण डी (एन) को कम रखने के लिए है के लिए हमें खेद है। ऐसा लगता है कि अगर आप के किसी भी संख्या के लिए अनुमति देते नोड्स को एक पेड़ से काटा जा सकता है, फिर डी (एन) रैखिक होने के लिए बढ़ सकता है, जो हटा देता है और हटा देता है-मिनट रैखिक समय लेता है।

सहजता से, आप ऑर्डर के पेड़ में नोड्स की संख्या चाहते हैं के रूप में घातीय। इस तरह, आप एक समेकित ढेर में केवल तर्कसंगत रूप से कई पेड़ प्राप्त कर सकते हैं। यदि आप मनमाने ढंग से नोड्स काट सकते हैं एक पेड़ से, आप यह गारंटी खो देते हैं। विशेष रूप से, आप ऑर्डर के पेड़ ले सकते हैं, फिर अपने सभी पोते को काट सकते हैं। यह के पेड़ों के साथ एक पेड़ छोड़ देता है, जिनमें से प्रत्येक पत्तियां हैं। नतीजतन, आप केवल के + 1 कुल नोड्स के साथ ऑर्डर के पेड़ बना सकते हैं। इसका मतलब है कि सबसे बुरे मामले में आपको सभी नोड्स को पकड़ने के लिए ऑर्डर एन -1 के पेड़ की आवश्यकता होगी, इसलिए डी (एन) ओ (लॉग एन) के बजाय एन -1 हो जाता है।

आशा है कि इससे मदद मिलती है!