मूल्यह्रास विश्लेषण

हेलो, हेब्र!

आज हम मूल्यह्रास विश्लेषण के बारे में बात करेंगे। पहले मैं आपको बताऊंगा कि यह क्या है और एक खिलौना उदाहरण देता है। और फिर मैं आपको बताऊंगा कि इसका उपयोग कैसे करें कि आप असंतुष्ट सेट की प्रणाली का विश्लेषण कर सकें।

मूल्यह्रास विश्लेषण

मूल्यह्रास विश्लेषण का उपयोग कई बार चलने वाले एल्गोरिदम के लिए किया जाता है। एल्गोरिथ्म का समय बहुत उतार-चढ़ाव कर सकता है, लेकिन हम सभी शुरुआत के लिए औसत या कुल समय का अनुमान लगाते हैं। ज्यादातर, एक एल्गोरिथ्म डेटा संरचना पर किसी प्रकार के ऑपरेशन को लागू करता है।

शब्द "मूल्यह्रास" खुद वित्त से आया है। यह ऋण चुकाने के लिए छोटे आवधिक भुगतान का मतलब है। सामान्य मामले में, इसका मतलब है कि तेज संचालन अपने समय के साथ धीमे लोगों की लागत की भरपाई करता है।

संचालन के अनुक्रम पर विचार करें । हर ऑपरेशन वास्तव में समय में निष्पादित किया जाता है । इस समय को वास्तविक कहा जाएगा। प्रत्येक ऑपरेशन के लिए हम मूल्यह्रास समय की गणना करेंगे । हम इस समय का मूल्यांकन करना आसान बनाते हैं । दो प्रतिबंध इस से अनुसरण करते हैं: ए) औपचारिक - किसी भी क्षण के लिए असमानता रखती है , और बी) अनौपचारिक - मूल्यह्रास लागत की राशि पर आसानी से विचार किया जाना चाहिए।

हमारी आंखों के सामने एक ठोस उदाहरण रखने के लिए, उस डेटा संरचना पर विचार करें जिसके भीतर स्टैक निहित है। डेटा संरचना op(m, x) ऑपरेशन का समर्थन करती है, जो अंतिम को पॉप करता है तत्वों और फिर तत्व सम्मिलित करता है ।

 def op(stack, m, x): for i in range(m): stack.pop() stack.push(x) 

हम मान लेंगे कि तर्क हमेशा सही होते हैं, और हमें स्टैक पर अधिक से अधिक फेंकने की आवश्यकता नहीं होगी। इसके अलावा, हम मानते हैं कि op(m, x) में संतुष्ट है बिना कदम -notatsii। हमारे सभी अनुमानों को हमेशा सही होने के लिए एक निरंतरता से गुणा किया जा सकता है।

ध्यान दें कि टाइम ऑपरेशन op(m, x) एक से दूसरे तक चल सकता है कदम। एक मोटा अनुमान समय देगा सभी को पूरा करने के लिए संचालन।

मूल्यह्रास विश्लेषण तीन मूल्यांकन विधियाँ प्रदान करता है।

बैंकर की विधि। समय पैसा है

समय की हर इकाई को एक सिक्का होने दें। हम प्रत्येक ऑपरेशन देते हैं सिक्के और खर्च करने की अनुमति । उनके सभी ऑपरेशन के सिक्के डेटा संरचना के अनुसार रखे जा सकते हैं। एक ऑपरेशन की मूल्यह्रास लागत होगी ।

सहायक का समर्थन करने के लिए , हम एक प्रतिबंध सेट करेंगे: आप इस समय अधिक सिक्के खर्च नहीं कर सकते हैं: । जैसे तो ।

हमारे उदाहरण के लिए, हम प्रत्येक ऑपरेशन को एक सिक्का देंगे ( )। इसे उस आइटम पर रखें जो केवल स्टैक में जोड़ा गया था। इस प्रकार, हमने इस आइटम के भविष्य के पीओपी के लिए भुगतान किया।

ध्यान दें कि स्टैक के प्रत्येक तत्व पर किसी भी समय एक सिक्का निहित है, अर्थात। सभी POP प्रीपेड हैं।

बाहर फेंकने के लिए तत्व हम उन सभी सिक्कों को खर्च करेंगे जो उन पर झूठ बोलते हैं ( )। फिर प्रत्येक लेनदेन की मूल्यह्रास लागत । यह ध्यान देना बाकी है । हमें शीर्ष रैखिक प्रदर्शन अनुमान मिला संचालन।

भौतिकविद् विधि। अपनी क्षमता का उपयोग करें

कोई भी डेटा संरचना कई संभावित राज्यों को ले सकती है। चलो सभी कार्यों से पहले इसकी प्रारंभिक स्थिति है, और - हालत के बाद वें ऑपरेशन। हम संभावित फ़ंक्शन का परिचय देते हैं , जो डेटा संरचना की वर्तमान स्थिति को इनपुट के रूप में लेता है और कुछ गैर-नकारात्मक संख्या देता है। संभावित प्रारंभिक अवस्था शून्य होनी चाहिए। सादगी के लिए, हम निरूपित करते हैं के माध्यम से , और के माध्यम से । मूल्यह्रास लागत ।

अचल क्षमता की परिभाषा से। वास्तव में, ; सब पहले और आखिरी को छोड़कर, कम हो गए हैं और । जैसे तो ।

सामान्य विचार यह है कि क्षमता के ऐसे कार्य को खोजा जाए जो महंगे परिचालनों पर नाटकीय रूप से घटे, वास्तविक समय के लिए क्षतिपूर्ति हो, और सस्ते लोगों पर थोड़ा बढ़े। हमारे उदाहरण के लिए, ढेर पर तत्वों की संख्या उपयुक्त है। के बाद POP और एक PUSH । फिर मूल्यह्रास लागत , और फिर से हम एक रैखिक अनुमान प्राप्त करते हैं।

एकत्रीकरण विधि। आपको सब कुछ लेने और साझा करने की आवश्यकता है

यह विधि दो पिछले वाले का एक सामान्यीकरण है, और किसी तरह गणना करना है और प्रश्नों की संख्या से विभाजित करें।

हमारे मामले में, यह तर्क काम करता है। प्रत्येक op(m, x) ऑपरेशन एक PUSH और कई POP करता है। आप स्टैक से अधिक तत्वों को वहां नहीं डाल सकते हैं। ढेर पर रखो तत्वों, कोई और अधिक फेंक । तो कुल समय है । एक ऑपरेशन की मूल्यह्रास लागत ।

सेट प्रणाली को अस्वीकृत करें

उन्होंने हमें दिया तत्वों। तत्वों को सेट में जोड़ा जा सकता है। हम एक डेटा संरचना बनाना चाहते हैं जो तीन ऑपरेशनों का समर्थन करती है

• make_set(key) - एक तत्व का एक सेट बनाता है,
• union(A, B) - सेट A और B को जोड़ती है,
• find(x) - वह सेट लौटाता है जिसमें तत्व निहित है ।

इन परिचालनों का समर्थन करने वाली डेटा संरचना को डिसऑइंट सेट सिस्टम (एसएनएम) (डिसऑइंट-सेट डेटा स्ट्रक्चर, यूनियन-फाइंड डेटा स्ट्रक्चर या मर्ज-फाइ सेट) कहा जाता है।

पहले से ही एसएनएम के बारे में लिखा है। एल्गोरिथ्म और इसके आवेदन का विस्तृत विवरण यहां पाया जा सकता है । इस पोस्ट में, मैं संक्षेप में एल्गोरिथम को याद करता हूं और विश्लेषण पर ध्यान केंद्रित करता हूं।

एल्गोरिथ्म

प्रत्येक सेट हम एक पेड़ के रूप में संग्रहित करेंगे। ट्री नोड अभिभावक के लिए एक संदर्भ संग्रहीत करता है। यदि नोड मूल है, तो लिंक None को इंगित करता है। इसके अलावा, प्रत्येक नोड में एक अतिरिक्त rank फ़ील्ड होगा। हम नीचे इसकी चर्चा करेंगे।

 class Node: def __init__(self, key): self.parent = None self.rank = 0 self.key = key 

सेट को संभालने के लिए, हम प्रत्येक सेट के लिए एक प्रतिनिधि चुनेंगे। हमारे मामले में, यह पेड़ की जड़ होगी। यदि दो तत्वों के लिए प्रतिनिधि समान है, तो वे एक ही सेट में झूठ बोलते हैं। दो सेटों को संयोजित करने के लिए, आपको एक पेड़ को दूसरे की जड़ तक निलंबित करने की आवश्यकता है। हम एक सरल एल्गोरिथ्म प्राप्त करते हैं:

 def find(x): if x.parent == None: return x return find(x.parent) def union(x, y): x = find(x) y = find(y) y.parent = x return x 

एल्गोरिथ्म को गति देने के लिए, दो पुनरावृत्तियों का उपयोग किया जाता है।

ग्रेड । प्रत्येक नोड को एक रैंक सौंपा जाएगा जो शुरू में शून्य के बराबर है। वृक्ष की श्रेणी उसकी जड़ की श्रेणी है। सेट्स का संयोजन करते समय, हम निचले रैंक के एक पेड़ को एक बड़े पेड़ के पेड़ पर लटका देंगे। यदि रैंक्स मैच करते हैं, तो पहले पेड़ों की एक-एक करके रैंक बढ़ाएं।

 def union(x, y): x = find(x) y = find(y) if x.rank < y.rank: x, y = y, x if x.rank == y.rank: x.rank += 1 y.parent = x return x 

अकेले एसएनएम के काम को गति देने के लिए रैंक के आंकड़े पर्याप्त होंगे सबसे खराब संचालन के लिए। लेकिन हम और आगे बढ़ेंगे।

पथ संपीड़न आइए हम एक तत्व से find । आप देख सकते हैं कि रास्ते से सभी चोटियों रूट को तुरंत रूट पर निलंबित किया जा सकता है।

 def find(x): if x.parent == None: return x x.parent = find(x.parent) return x.parent 

हैरानी की बात है कि एक साथ इन दो उत्तराधिकारियों ने एक ऑपरेशन के मूल्यह्रास समय को लगभग स्थिर कर दिया है।

के विश्लेषण

1973 में, होपक्रॉफ्ट और उलेमन ने दिखाया कि एक एसएनएम जिसमें दो हेरास्टिक प्रक्रियाएं होती हैं के लिए संचालन जहाँ - पुनरावृति लघुगणक। बाद में, 1975 में, टार्जन ने खुलासा किया कि एसएनएम काम करता है जहाँ एकरमैन का विलोम कार्य है।

मेरी योजना पहले यह पता लगाना है कि ये मुश्किल काम क्या हैं, फिर सबसे खराब स्थिति में एक सरल लघुगणक अनुमान साबित करें, और अंत में हॉपक्रॉफ्ट और उलेमन अनुमान को बाहर करें। टारजन का मूल्यांकन मूल्यह्रास विश्लेषण का व्यापक उपयोग भी करता है, लेकिन इसमें अधिक तकनीकी विवरण शामिल हैं।

ट्रिकी फीचर्स

पुनरावृत्त लघुगणक पावर टॉवर का विलोम है। एक नंबर की कल्पना करते हैं जहां केवल दो होंगे । तो न्यूनतम ऐसा है उस बिजली टॉवर की ऊंचाई और होगा । औपचारिक रूप से

• किसी के लिए ;
• के लिए ।

पाठक को यह दिखाने के लिए अभ्यास करें कि ब्रह्मांड के ज्ञात हिस्से में कणों की संख्या का पुनरावृत्ति लघुगणक पांच से अधिक नहीं है।

आप सोच सकते हैं कि बिजली टॉवर तेजी से बढ़ रहा है, लेकिन बीसवीं शताब्दी की शुरुआत में गणितज्ञों के लिए यह पर्याप्त नहीं था, और वे एकरमैन फ़ंक्शन के साथ आए थे। इसे निम्नानुसार परिभाषित किया गया है:

• के लिए ;
• के लिए ;
• के लिए ।

यह सुविधा बहुत तेजी से बढ़ रही है। पर यह एक पावर टॉवर है। पर यह एक पावर टॉवर भी है, केवल अब टावर की संख्या भी पावर टॉवर है, आदि।

यदि आप दुश्मन से बदला लेना चाहते हैं, तो उसे केवल अंकगणितीय ऑपरेशन, आईएफएस और फॉर-एसएस (जबकि-एस और रिकर्सन की अनुमति नहीं है) का उपयोग करके इस फ़ंक्शन की गणना करने के लिए कहें। एकरमैन ने साबित कर दिया कि वह असफल होंगे।

एकरमन उलटा फ़ंक्शन न्यूनतम के रूप में परिभाषित किया गया ऐसा है । यह समझना आसान है कि यह बहुत धीरे-धीरे बढ़ता है।

सबसे खराब स्थिति स्कोर

सबसे पहले, ध्यान दें कि प्रत्येक union दो find कार्यों में किया जाता है और कुछ अतिरिक्त समय स्थिर होता है। इसलिए, केवल find लिए मूल्यांकन करना पर्याप्त है। सबसे खराब स्थिति का अनुमान दो सरल टिप्पणियों से है।

अवलोकन १ । रैंक का पेड़ कम से कम शामिल है नोड्स।

यह कथन प्रेरण द्वारा सिद्ध होता है। रैंक 0 के एक पेड़ के लिए, जाहिर है। एक रैंक पेड़ पाने के लिए दो रैंक पेड़ गठबंधन करने की जरूरत है , जिनमें से प्रत्येक में कम से कम नोड्स। तो रैंक ट्री में कम से कम नोड्स।

नतीजतन, किसी भी समय, रैंक के नोड्स अब और नहीं होगा , और अधिकतम नोड रैंक ।

टिप्पणी 2 । माता-पिता की रैंक हमेशा बच्चे की रैंक से अधिक होती है।

यह निर्माण से निम्नानुसार है। चूंकि रैंक हमेशा ऊपर से जड़ तक के रास्ते पर बढ़ती है, इसलिए इसकी लंबाई अधिक नहीं होती है , और किसी भी find काम करता है ।

हॉपक्रॉफ्ट और उलमैन स्कोर

आइए हम यह साबित करते हैं एसएनएम का संचालन तत्वों के लिए आयोजित किया जा सकता है ।

make_set ऑपरेशन make_set किया जाता है । union संचालन - के लिए प्लस दो संचालन का समय। इसलिए, यह दिखाने के लिए पर्याप्त है find संचालन में किया जाएगा ।

find ऑपरेशन का निष्पादन समय उस पथ की लंबाई के लिए आनुपातिक है जो आप दिए गए नोड से रूट पर जाना चाहते हैं। इसलिए, आपको नोड्स द्वारा पास की कुल संख्या का मूल्यांकन करने की आवश्यकता है।

में सभी रैंकों को तोड़ें सेट: । -इस सेट में पावर टावर से सभी रैंक होंगे ऊंचाई to टावर हाइट्स । सेट की संख्या जिसमें नोड झूठ की रैंक को नोड का स्तर कहा जाता है।

हम कहेंगे कि एक नोड अच्छा है यदि यह पेड़ की जड़ है, जड़ का तत्काल बच्चा है, या उसके और उसके माता-पिता के अलग-अलग स्तर हैं। शेष नोड्स को बुरा कहा जाता है।

कुल स्तर नहीं । इसलिए, किसी भी नोड से रूट तक के पथ से अधिक नहीं है अच्छा गाँठ। कुल मिलाकर, कोई और अधिक नहीं होगा अच्छा गाँठ।

खराब नोड्स पर पास की संख्या का अनुमान लगाएं। बुरी गाँठ लगने दो एक रैंक है , और कई के अंतर्गत आता है । ध्यान दें कि एक बुरा नोड मूल नहीं है, और इसलिए इसकी रैंक तय की गई है। अगर find एक नोड के माध्यम से चला जाता है तो एक उच्च पद के साथ एक नए के लिए अपने माता पिता को बदलता है। से अधिक नहीं गुजरता है एक बुरी गाँठ की तरह अच्छा बन जाएगा।

कुल रैंक नोड्स अब और नहीं । तो सेट से रैंक के साथ नोड्स अब और नहीं होगा । प्रत्येक नोड के लिए, अधिक नहीं मार्ग, जैसे कि एक बुरी गाँठ में। तो पास होने के योग में और नहीं होगा । कुल स्तर । तो, खराब नोड्स के माध्यम से अधिक पास नहीं होंगे ।

टोटल को टॉप रेटिंग मिली कुल में सभी कार्यों के लिए।

साहित्य

• कॉर्मेन, लिसेर्सन, रिवेस्ट "एल्गोरिदम: निर्माण और विश्लेषण"
• टारजन "डेटा संरचनाएं और नेटवर्क एल्गोरिदम"
• रेबेका फ़िएब्रिंक "अमूर्त विश्लेषण समझाया"