अमूर्त विश्लेषण
अमूर्त विश्लेषण संचालन के सबसे खराब स्थिति वाले अनुक्रम पर प्रति संचालन औसत लागत को सीमित करता है, यह दर्शाता है कि कभी-कभी महंगे संचालन सस्ते हो सकते हैं जब उनकी लागत कई सस्ते संचालनों में फैली होती है।
Definition
अमूर्त विश्लेषण एक डेटा संरचना पर संचालन के अनुक्रम की कुल लागत को सीमित करने और संचालन की संख्या से विभाजित करने की एक विधि है, जिससे प्रति संचालन एक अमूर्त लागत प्राप्त होती है जो पूरे अनुक्रम पर सबसे खराब स्थिति में भी मान्य होती है, भले ही व्यक्तिगत संचालन की लागत में व्यापक भिन्नता हो।
Scope
यह विषय अमूर्त विश्लेषण की तीन मानक तकनीकों — एग्रीगेट विधि, अकाउंटिंग (बैंकर की) विधि, और पोटेंशियल विधि — और गतिशील सरणियों, बाइनरी काउंटरों, स्प्ले ट्री, और डिसजॉइंट-सेट (यूनियन-फाइंड) संरचना जैसे डेटा संरचनाओं पर उनके अनुप्रयोग को शामिल करता है, जिनके व्यक्तिगत संचालन की लागत भिन्न होती है। यह अमूर्त लागत को औसत-मामले की लागत और प्रति-संचालन सबसे खराब स्थिति की लागत से अलग करता है।
Core questions
- अमूर्त लागत प्रति-संचालन सबसे खराब स्थिति और औसत-मामले की लागत से कैसे भिन्न होती है?
- एग्रीगेट विधि संचालन अनुक्रम की कुल लागत को कैसे सीमित करती है?
- अकाउंटिंग विधि बाद के महंगे संचालन के लिए भुगतान करने के लिए क्रेडिट कैसे आवंटित करती है?
- पोटेंशियल विधि लागतों को सुचारू करने के लिए पोटेंशियल फ़ंक्शन का उपयोग कैसे करती है?
- कौन सी डेटा संरचनाएं प्रति-संचालन सीमाओं के बजाय अमूर्त गारंटी पर निर्भर करती हैं?
Key concepts
- अमूर्त लागत
- एग्रीगेट विधि
- अकाउंटिंग (बैंकर की) विधि
- पोटेंशियल विधि
- पोटेंशियल फ़ंक्शन
- गतिशील सरणी का दोगुना होना
- बाइनरी काउंटर वृद्धि
- पाथ कम्प्रेशन के साथ यूनियन-फाइंड
Key theories
- पोटेंशियल विधि
- पोटेंशियल विधि डेटा संरचना की स्थिति को एक गैर-ऋणात्मक पोटेंशियल प्रदान करती है; एक संचालन की अमूर्त लागत उसकी वास्तविक लागत और पोटेंशियल में परिवर्तन का योग होती है, इसलिए सस्ते संचालन पोटेंशियल का निर्माण करते हैं जो बाद के महंगे संचालनों के लिए भुगतान करता है।
- अकाउंटिंग (बैंकर की) विधि
- अकाउंटिंग विधि कुछ संचालनों पर उनकी वास्तविक लागत से अधिक शुल्क लेती है, अधिशेष को डेटा-संरचना तत्वों पर क्रेडिट के रूप में संग्रहीत करती है ताकि भविष्य के महंगे संचालनों के लिए भुगतान किया जा सके, यह सुनिश्चित करते हुए कि क्रेडिट कभी नकारात्मक न हो।
Clinical relevance
अमूर्त विश्लेषण बताता है कि कई व्यापक रूप से उपयोग की जाने वाली संरचनाएं कभी-कभी महंगे संचालन के बावजूद व्यवहार में कुशल क्यों होती हैं: गतिशील सरणियाँ (पुनः आकार देने योग्य सूचियाँ), हैश टेबल जो रीहैश करते हैं, कनेक्टिविटी और न्यूनतम-स्पैनिंग-ट्री एल्गोरिदम में उपयोग किए जाने वाले यूनियन-फाइंड, और स्प्ले ट्री जैसी स्व-समायोजित संरचनाएं सभी प्रति-संचालन गारंटी के बजाय अमूर्त पर निर्भर करती हैं।
History
अमूर्त विश्लेषण के लिए शब्द और व्यवस्थित ढांचा रॉबर्ट टार्जन द्वारा 1985 में पेश किया गया था, जो पहले के तदर्थ तर्कों पर आधारित था। यह तकनीक 1980 के दशक में टार्जन और स्लेटर द्वारा विकसित स्व-समायोजित डेटा संरचनाओं (स्प्ले ट्री, फिबोनाची हीप्स) का विश्लेषण करने के लिए केंद्रीय थी।
Key figures
- Robert Tarjan
- Daniel Sleator
Related topics
Seminal works
- tarjan1985amortized
- cormen2009
Frequently asked questions
- क्या अमूर्त लागत औसत-मामले की लागत के समान है?
- नहीं। औसत-मामले की लागत इनपुट के संभाव्यता वितरण पर एक अपेक्षा है और एक दुर्भाग्यपूर्ण इनपुट द्वारा इसका उल्लंघन किया जा सकता है। अमूर्त लागत संचालन के अनुक्रम पर सबसे खराब स्थिति की गारंटी है जिसमें कोई यादृच्छिकता नहीं मानी जाती है: ऐसे किसी भी अनुक्रम की कुल लागत सीमित होती है, इसलिए प्रति संचालन औसत हमेशा मान्य होता है।
- जब आकार बदलना O(n) होता है तो गतिशील सरणी में जोड़ना O(1) अमूर्त क्यों होता है?
- क्योंकि सरणी आमतौर पर अपनी क्षमता को दोगुना करती है, आकार बदलना जोड़ने की तुलना में दुर्लभ होता है, और n जोड़ने के अनुक्रम पर कुल कॉपी करने का काम n के आनुपातिक होता है। सभी जोड़ने पर फैला हुआ, यह एक स्थिर अमूर्त लागत देता है, भले ही एक एकल आकार बदलना रैखिक हो।