DAA - विश्लेषण की पद्धति
एल्गोरिथ्म के संसाधन खपत को मापने के लिए, इस अध्याय में चर्चा की गई विभिन्न रणनीतियों का उपयोग किया जाता है।
असममित विश्लेषण
किसी फ़ंक्शन का स्पर्शोन्मुख व्यवहार f(n) की वृद्धि को दर्शाता है f(n) जैसा n बड़ा हो जाता है।
हम आम तौर पर छोटे मूल्यों की उपेक्षा करते हैं n, क्योंकि हम आम तौर पर यह अनुमान लगाने में रुचि रखते हैं कि बड़े इनपुट पर कार्यक्रम कितना धीमा होगा।
अंगूठे का एक अच्छा नियम यह है कि स्पर्शोन्मुख विकास दर जितनी धीमी होगी, एल्गोरिथम उतना ही बेहतर होगा। हालांकि यह हमेशा सच नहीं होता है।
उदाहरण के लिए, एक रेखीय एल्गोरिदम $ f (n) = d * n + k $ हमेशा एक द्विघात, $ f (n) = cn ^ 2 + q $ से असमान रूप से बेहतर होता है।
पुनरावृत्ति समीकरणों को हल करना
पुनरावृत्ति एक समीकरण या असमानता है जो छोटे आदानों पर इसके मूल्य के संदर्भ में एक फ़ंक्शन का वर्णन करता है। आवर्ती का उपयोग आम तौर पर विभाजन और विजय प्रतिमान में किया जाता है।
हम मानते हैं T(n) आकार की समस्या पर चलने का समय होना n।
यदि समस्या का आकार काफी छोटा है, तो कहें n < c कहाँ पे c एक स्थिर है, सीधा समाधान निरंतर समय लेता है, जिसे लिखा जाता है θ(1)। यदि समस्या का विभाजन आकार $ \ frac {n} {b} $ के साथ कई उप-समस्याओं का उत्पादन करता है।
समस्या को हल करने के लिए, आवश्यक समय है a.T(n/b)। यदि हम विभाजन के लिए आवश्यक समय पर विचार करेंD(n) और उप-समस्याओं के परिणामों के संयोजन के लिए आवश्यक समय है C(n)पुनरावृत्ति संबंध का प्रतिनिधित्व इस प्रकार किया जा सकता है -
$$ टी (एन) = \ begin {मामलों} \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \ _ \: \: \: थीटा (१) और अगर \: n \ leqslant c \\ a T (\ frac {n} {b}) + D (n) + C (n) & अन्यथा \ end { मामलों} $$
निम्नलिखित तरीकों का उपयोग करके एक पुनरावृत्ति संबंध को हल किया जा सकता है -
Substitution Method - इस पद्धति में, हम एक बाध्य अनुमान लगाते हैं और गणितीय प्रेरण का उपयोग करके हम यह साबित करते हैं कि हमारी धारणा सही थी।
Recursion Tree Method - इस विधि में, एक पुनरावृत्ति वृक्ष का निर्माण होता है जहाँ प्रत्येक नोड लागत का प्रतिनिधित्व करता है।
Master’s Theorem - पुनरावृत्ति संबंध की जटिलता को खोजने के लिए यह एक और महत्वपूर्ण तकनीक है।
परिशोधित विश्लेषण
अमूर्त विश्लेषण आमतौर पर कुछ एल्गोरिदम के लिए उपयोग किया जाता है जहां समान संचालन का एक क्रम किया जाता है।
परिशोधित विश्लेषण पूरे अनुक्रम की वास्तविक लागत पर एक सीमा प्रदान करता है, इसके बजाय अलग से संचालन के अनुक्रम की लागत को बाध्य करता है।
परिशोधित विश्लेषण औसत-केस विश्लेषण से भिन्न होता है; संभावना परिशोधन विश्लेषण में शामिल नहीं है। परिशोधित विश्लेषण सबसे खराब स्थिति में प्रत्येक ऑपरेशन के औसत प्रदर्शन की गारंटी देता है।
यह केवल विश्लेषण के लिए एक उपकरण नहीं है, यह डिजाइन के बारे में सोचने का एक तरीका है, क्योंकि डिजाइनिंग और विश्लेषण बारीकी से संबंधित हैं।
एकत्र करने की विधि
कुल विधि एक समस्या के बारे में वैश्विक दृष्टिकोण देती है। इस विधि में, यदिn संचालन में सबसे खराब समय लगता है T(n)कुल मिलाकर। फिर प्रत्येक ऑपरेशन की परिशोधन लागत हैT(n)/n। हालांकि अलग-अलग संचालन में अलग-अलग समय लग सकता है, इस पद्धति में अलग-अलग लागत की उपेक्षा की जाती है।
लेखा विधि
इस पद्धति में, अलग-अलग शुल्क उनकी वास्तविक लागत के अनुसार अलग-अलग परिचालनों को सौंपे जाते हैं। यदि किसी ऑपरेशन की परिशोधित लागत इसकी वास्तविक लागत से अधिक है, तो अंतर को क्रेडिट के रूप में ऑब्जेक्ट को सौंपा गया है। यह क्रेडिट बाद के संचालन के लिए भुगतान करने में मदद करता है जिसके लिए वास्तविक लागत से कम परिशोधन लागत होती है।
यदि वास्तविक लागत और परिशोधित लागत ith ऑपरेशन $ c_ {i} $ और $ \ hat {c_ {l}} $ हैं, फिर
$$ \ displaystyle \ sum \ limit_ {i = 1} ^ n \ hat {c_ {l}} \ geqllant \ displaystyle \ sum \ limit_ {i = 1} ^ n c_ {i} $$
संभावित विधि
यह विधि क्रेडिट के रूप में प्रीपेड काम पर विचार करने के बजाय संभावित ऊर्जा के रूप में प्रीपेड कार्य का प्रतिनिधित्व करती है। यह ऊर्जा भविष्य के संचालन के लिए भुगतान करने के लिए जारी की जा सकती है।
अगर हम प्रदर्शन करते हैं n एक प्रारंभिक डेटा संरचना के साथ संचालन शुरू होता है D0। हम मानते हैं,ci वास्तविक लागत के रूप में और Di के डेटा संरचना के रूप में ithऑपरेशन। एक वास्तविक संख्या के लिए संभावित फ़ंक्शन potential मैप्स Ф (Di), की सम्भावना है Di। अमूर्त लागत $ \ टोपी {c_ {l}} $ द्वारा परिभाषित की जा सकती है
$$ \ hat {c_ {l}} = c_ {i} + \ Phi (D_ {i}) - \ Phi (D_ {i-1}) $$
इसलिए, कुल परिशोधित लागत है
$$ \ displaystyle \ sum \ limit_ {i = 1} ^ n \ hat {c_ {l}} = \ displaystyle \ sum \ limit_ {i = 1} ^ n (c_ {i} + \ Phi (D_ {i) ) - \ Phi (D_ {i-1})) = \ displaystyle \ sum \ limit_ {i = 1} ^ n c_ {i} + \ Phi (D_ {n}) - \ Phi (D_ {0}) $ { $
गतिशील तालिका
यदि तालिका के लिए आवंटित स्थान पर्याप्त नहीं है, तो हमें तालिका को बड़े आकार की तालिका में कॉपी करना होगा। इसी तरह, यदि बड़ी संख्या में सदस्यों को तालिका से मिटा दिया जाता है, तो तालिका को छोटे आकार के साथ फिर से जोड़ना एक अच्छा विचार है।
परिशोधन विश्लेषण का उपयोग करते हुए, हम दिखा सकते हैं कि सम्मिलन और विलोपन की परिशोधित लागत एक गतिशील तालिका में निरंतर और अप्रयुक्त स्थान है जो कुल अंतरिक्ष के निरंतर अंश से अधिक नहीं है।
इस ट्यूटोरियल के अगले अध्याय में, हम संक्षेप में एसिम्प्टोटिक नोटिफिकेशन पर चर्चा करेंगे।