मिनट-हीप पर डालने / हटाने की बढ़ी हुई लागत
मैं हाल ही में एक साक्षात्कार प्रश्न में भाग गया। कोई अतिरिक्त जानकारी प्रश्न में नहीं दी गई है (शायद डिफ़ॉल्ट कार्यान्वयन का उपयोग किया जाना चाहिए ...)
n शून्य मिनट ढेर पर डालने और हटाने के कार्यों का मनमाना क्रम ( डिलीट एलिमेंट के लिए स्थान ज्ञात है ) की लागत में वृद्धि हुई है:
ए) ओ डालें (1), ओ हटाएं (लॉग एन)
बी) ओ डालें (एन लॉग करें), ओ निकालें (1)
विकल्प ( B ) सही है।
उत्तर पुस्तिका देखने पर मुझे आश्चर्य हुआ। मुझे पता है कि यह मुश्किल है, शायद खाली ढेर है, शायद हटाने के लिए तत्वों का स्थान जानना ... मुझे पता नहीं क्यों (ए) गलत है? क्यों (बी) सच है?
जवाब
किसी डेटा संरचना पर परिचालनों में परिशोधित लागतों को निर्दिष्ट करते समय, आपको यह सुनिश्चित करने की आवश्यकता होती है कि किए गए किसी भी क्रम के लिए, यह सुनिश्चित करने के लिए कि उन परिचालनों की वास्तविक लागतों के योग में परिमित लागतों का योग हमेशा कम से कम उतना बड़ा हो।
तो चलिए विकल्प 1 लेते हैं, जो सम्मिलन के लिए O (1) की परिमित लागत और विलोपन के लिए O (लॉग एन) की परिशोधन लागत प्रदान करता है। हमें जो प्रश्न पूछना है, वह निम्नलिखित है: क्या यह सच है कि किसी खाली बाइनरी हीप पर परिचालन के किसी भी क्रम के लिए , उन परिचालनों की वास्तविक लागत उन परिचालनों की परिमित लागत से ऊपरी-सीमाबद्ध होती है? और इस मामले में, जवाब नहीं है। कल्पना कीजिए कि आप शुद्ध रूप से n सम्मिलन का एक क्रम ढेर में करते हैं। इन ऑपरेशनों को करने की वास्तविक लागत Θ (n log n) हो सकती है यदि प्रत्येक तत्व को ढेर के शीर्ष तक सभी तरह से बुलबुला बनाना है। हालाँकि, इस संचालन योजना के साथ उन परिचालनों की परिशोधित लागत O (n) होगी, क्योंकि हमने n संचालन किया था और प्रत्येक एक O (1) समय का नाटक किया था। इसलिए, यह परिशोधित लेखा योजना काम नहीं करती है, क्योंकि यह हमें उस काम को कम आंकने देगी जो हम कर रहे हैं।
दूसरी तरफ, विकल्प 2 को देखें, जहां हम अपनी परिशोधित लागत के रूप में O (लॉग एन) असाइन करते हैं और ओ (1) को हमारी amortized remove cost के रूप में। अब, क्या हम n संचालन का एक क्रम पा सकते हैं, जहां उन परिचालनों की वास्तविक लागत परिशोधित लागतों से अधिक हो? इस मामले में, जवाब नहीं है। यहाँ यह देखने का एक तरीका है। हमने ओ (लॉग एन) होने के लिए एक सम्मिलन की परिमाणित लागत निर्धारित की है, जो इसकी वास्तविक लागत से मेल खाती है, और इसलिए एकमात्र तरीका है कि हम कुल को कम करके आंका जा सकता है एक विलोपन की हमारी परिमित लागत (O) के साथ ), जो एक विलोपन की सही लागत से कम है। हालाँकि, यह यहाँ एक समस्या नहीं है। हमें हटाए गए ऑपरेशन करने में सक्षम होने के लिए, हमें पहले उस तत्व को सम्मिलित करना होगा जिसे हम हटा रहे हैं। सम्मिलन और विलोपन की संयुक्त वास्तविक लागत हे (लॉग एन) + ओ (लॉग एन) = ओ (लॉग एन), और सम्मिलन और हटाने का संयुक्त परिशोधन लागत हे (लॉग एन) + ओ (१) ) = ओ (लॉग एन)। इस लिहाज से, यह दिखावा कि विलोपन तेज हैं, हमारी कुल लागत में बदलाव नहीं होता है।
यह देखने के लिए एक अच्छा सहज तरीका है कि दूसरा दृष्टिकोण क्यों काम करता है, लेकिन पहला यह सोचने के लिए नहीं है कि परिशोधन विश्लेषण क्या है। परिशोधन के पीछे अंतर्ज्ञान पहले के संचालन को थोड़ा अधिक चार्ज करना है ताकि भविष्य के संचालन में कम समय लगे। दूसरी लेखांकन योजना के मामले में, ठीक यही हम कर रहे हैं: हम उस तत्व को पहली जगह में ढेर में डालने की लागत पर बाइनरी हीप से एक तत्व के विलोपन की लागत को स्थानांतरित कर रहे हैं। इस तरह, चूंकि हम केवल काम को पीछे की ओर स्थानांतरित कर रहे हैं, इसलिए परिशोधन लागतों का योग वास्तविक लागतों के योग से कम नहीं हो सकता है। दूसरी ओर, पहले मामले में, हम विलोपन के लिए भुगतानों को हटाकर समय पर काम को आगे बढ़ा रहे हैं। लेकिन यह एक समस्या है, क्योंकि अगर हम सम्मिलन का एक गुच्छा करते हैं और फिर उसी विलोपन को कभी नहीं करते हैं तो हमने काम को उन कार्यों के लिए स्थानांतरित कर दिया है जो मौजूद नहीं हैं।
क्योंकि ढेर शुरू में खाली है, आप आवेषण की तुलना में अधिक हटा नहीं सकते हैं।
विलोपन के लिए O (1) और प्रति सम्मिलन O (लॉग एन) की एक परिचालित लागत बिलकुल समान है, आवेषण और डिलीट दोनों के लिए O (लॉग एन) की परिशोधन लागत, क्योंकि आप केवल विलोपन लागत की गणना तब कर सकते हैं जब आप ऐसा नहीं करते हैं संगत डालें।
यह दूसरे तरीके से काम नहीं करता है। चूँकि आप हटाए जाने की तुलना में अधिक आवेषण कर सकते हैं, इसलिए प्रत्येक प्रविष्टि की लागत का भुगतान करने के लिए पर्याप्त हटाए नहीं जा सकते हैं।