algorithm - एल्गोरिदम के अमूर्त विश्लेषण क्या है?




analysis amortized-analysis (5)

यह एसिम्प्टोटिक विश्लेषण से अलग कैसे है? आप इसका इस्तेमाल कब करते हैं, और क्यों?

मैंने कुछ लेख पढ़े हैं जो अच्छी तरह से लिखे गए हैं, जैसे:

लेकिन मैं अभी भी इन अवधारणाओं को पूरी तरह समझ नहीं पाया है।

तो, क्या कोई इसे मेरे लिए सरल बना सकता है?


Asymptotic विश्लेषण

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

ध्यान दें कि अब तक हमने केवल विश्लेषण की विधि के बारे में बात की है; हमने यह निर्दिष्ट नहीं किया है कि हम किस मात्रा का विश्लेषण कर रहे हैं (समय जटिलता? अंतरिक्ष जटिलता?), और न ही हमने निर्दिष्ट किया है कि हम किस मीट्रिक में रूचि रखते हैं (सबसे खराब मामला? सबसे अच्छा मामला? औसत?)।

अभ्यास में एसिम्प्टोटिक विश्लेषण शब्द आमतौर पर एल्गोरिदम की ऊपरी बाध्य समय जटिलता को संदर्भित करता है, यानी कुल चलने वाले समय द्वारा मापा जाने वाला सबसे खराब केस प्रदर्शन, जिसे बड़े-ओह नोटेशन द्वारा दर्शाया जाता है (उदाहरण के लिए एक सॉर्टिंग एल्गोरिदम O(nlogn) हो सकता है)।

अमूर्त विश्लेषण

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

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

नोट: सटीक होने के लिए, सबसे खराब पथ सैद्धांतिक रूप से संभव है । यदि आपके पास एक वेक्टर है जो हर बार आकार में गतिशील रूप से दोगुना हो जाता है, तो इसकी क्षमता समाप्त हो जाती है, "सबसे खराब मामला" यह मानने का मतलब नहीं है कि इसे प्रत्येक प्रविष्टि पर दोगुना करने की आवश्यकता होगी क्योंकि सम्मिलन को अनुक्रम के रूप में संसाधित किया जाता है। हमें ज्ञात स्थिति का उपयोग करने की अनुमति है (और वास्तव में) गणितीय रूप से गणित के रूप में कई "यहां तक ​​कि बदतर" मामलों को खत्म करने की अनुमति है, भले ही इनपुट अज्ञात रहता है।

सबसे महत्वपूर्ण अंतर

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

इसलिए:

  • एसिम्प्टोटिक विश्लेषण हमें यह कहने की इजाजत देता है कि एल्गोरिदम की जटिलता जब इसे आकार के सबसे अच्छे / सबसे खराब / औसत मामले इनपुट को दिया जाता है तो कुछ फ़ंक्शन F (N) से घिरा होता है - जहां एन एक चर है
  • अमूर्त विश्लेषण हमें यह कहने की अनुमति देता है कि एल्गोरिदम की जटिलता जब इसे अज्ञात विशेषताओं का इनपुट दिया जाता है लेकिन ज्ञात आकार एन फ़ंक्शन F (N) के मान से भी बुरा नहीं है - जहां एन ज्ञात मान है

"क्या" के बहुत सारे जवाब हैं, लेकिन "क्यों" के लिए कोई भी नहीं।

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

यदि आप लंबे समय तक नौकरी के कुल चलने वाले समय से चिंतित हैं, तो अमूर्त विश्लेषण की बेहतर सीमाएं शायद आप की परवाह करते हैं। यही कारण है कि स्क्रिप्टिंग भाषाओं (उदाहरण के लिए) कुछ कारकों द्वारा सरणी और हैश टेबल विकसित करने के लिए अक्सर खुश होते हैं, भले ही यह एक महंगा ऑपरेशन है। (बढ़ रहा O(n) ऑपरेशन हो सकता है, लेकिन अमूर्त O(1) क्योंकि आप इसे शायद ही कभी करते हैं।)

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

आपके मामले में कौन सा मायने रखता है इस पर निर्भर करता है कि आपकी प्रोग्रामिंग समस्या क्या है।


अमूर्त विश्लेषण दिनचर्या के कई रनों पर कुल लागत के साथ संबंधित है, और लाभ जो उसमें प्राप्त किए जा सकते हैं। उदाहरण के लिए एक एकल मैच के लिए एन आइटमों की एक अनारक्षित सरणी खोजना एन तुलना में हो सकता है और इसलिए ओ (एन) जटिलता है। हालांकि, अगर हम जानते हैं कि एम वस्तुओं के लिए एक ही सरणी की खोज की जा रही है, तो कुल कार्य को दोहराने के बाद जटिलता ओ (एम * एन) होगी। हालांकि, अगर हम पहले से सरणी को सॉर्ट करते हैं, तो लागत ओ (एन लॉग (एन)) है, और लगातार खोज केवल क्रमबद्ध सरणी के लिए ओ (लॉग (एन)) लेती है। इस प्रकार एम दृष्टिकोण के लिए एम एम तत्वों के लिए कुल अमूर्त लागत ओ (एन * लॉग (एन) + एम * लॉग (एन) है। यदि m> = n, यह सॉर्टिंग के लिए ओ (एन ^ 2) की तुलना में प्री-सॉर्टिंग द्वारा ओ (एन लॉग (एन)) के बराबर है। इस प्रकार अमूर्त लागत सस्ता है।

थोड़ी देर पहले थोड़ा खर्च करके, हम बहुत बाद में बचा सकते हैं।


इसका उत्तर संक्षेप में पुस्तक में अमूर्त विश्लेषण अध्याय के पहले वाक्य द्वारा परिभाषित किया गया है - एल्गोरिदम का परिचय:

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

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

लेकिन यह उन मामलों में भ्रामक हो सकता है जहां केवल एक मामला है जहां कार्यक्रम की जटिलता एक चोटी तक पहुंच जाती है, लेकिन आम तौर पर, कार्यक्रम अधिक गणना नहीं करता है।

इसलिए, यह संचालन के अनुक्रम पर लागत को औसत करने के लिए और अधिक समझ में आता है, भले ही एक ही ऑपरेशन महंगा हो। यह अमूर्त विश्लेषण है!

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


नियमित एसिम्प्टोटिक विश्लेषण समस्या के आकार के एक समारोह के रूप में, एक व्यक्तिगत ऑपरेशन के प्रदर्शन को असम्बद्ध रूप से प्रदर्शित करता है। ओ () नोटेशन एक एसिम्प्टोटिक विश्लेषण इंगित करता है।

अमूर्त विश्लेषण (जो एक एसिम्प्टोटिक विश्लेषण भी है) एक साझा डेटास्ट्रक्चर पर कई संचालन के कुल प्रदर्शन को देखता है

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

उदाहरण के लिए, आकार एन के एक स्प्ले पेड़ पर एक व्यक्तिगत ऑपरेशन ओ (एन) समय तक ले सकता है। हालांकि, आकार एन के पेड़ पर एम ऑपरेशंस का एक अनुक्रम ओ (एम (1 + लॉग एन) + एन लॉग एन) समय से घिरा हुआ है, जो लगभग प्रति ऑपरेशन ओ (लॉग एन) है। हालांकि, ध्यान दें कि एक अमूर्त विश्लेषण "औसत-मामला" विश्लेषण से काफी कठोर है: यह साबित करता है कि संचालन के किसी भी संभावित अनुक्रम से इसके असीमित मामले को पूरा किया जाएगा।







amortized-analysis