Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> प्रोग्रामिंग

मेल्ड ऑपरेशन की एमोर्टाइज़्ड लागत


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

मान लीजिए B एक एब्सट्रैक्ट डेटा टाइप (ADT) है जिसके बेसिक ऑपरेशन्स P = {P₁, P₂, ..., Pₖ} हैं और DS, B को लागू करने वाला एक डेटा स्ट्रक्चर है। मान लीजिए F, डेटा स्ट्रक्चर के कॉन्फिगरेशन्स पर निर्दिष्ट एक पोटेंशियल फ़ंक्शन है जो नॉन-नेगेटिव रियल नंबर देता है। मान लीजिए आगे कि F(Φ) = 0। मान लीजिए DSʲ एक कॉन्फिगरेशन को निर्दिष्ट करता है जो हम कॉन्फिगरेशन DS पर एक ऑपरेशन Pₖ करके प्राप्त करते हैं और C, DS पर Pₖ को करने की वास्तविक लागत को दर्शाता है।

तब, DS पर ऑपरेट करने वाले Pₖ की एमोर्टाइज़्ड लागत, जिसे a(Pₖ, DS) से दर्शाया जाता है, निम्न द्वारा दी जाती है:

a(Pₖ, DS) = C + F(DSʲ) – F(DS)

यदि सभी आकार m के कॉन्फिगरेशन DS के लिए a(Pₖ, DS) ≤ cⱼg(m) है, तो हम निष्कर्ष निकालते हैं कि Pₖ की एमोर्टाइज़्ड लागत O(g(m)) है।

  1. एमोर्टाइज़्ड कॉम्प्लेक्सिटी (परिशोधित जटिलता) एमोर्टाइज़्ड कॉम्प्लेक्सिटी (परिशोधित जटिलता)

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

  1. कर्स्कल का (मिनिमम स्पैनिंग ट्री) MST एल्गोरिदम कर्स्कल का (मिनिमम स्पैनिंग ट्री) MST एल्गोरिदम

    एक कनेक्टेड ग्राफ G(V,E) है और हर एज के लिए वजन या लागत दी गई है। कर्स्कल का एल्गोरिदम ग्राफ और लागत का उपयोग करके मिनिमम स्पैनिंग ट्री ढूंढेगा।यह मर्ज ट्री दृष्टिकोण है। प्रारंभ में अलग-अलग ट्री हैं, यह एल्गोरिदम उन्हें उन एज को लेकर मर्ज करेगा जिनकी लागत न्यूनतम है, और एक सिंगल ट्री बनाएगा।इस समस्

  1. डेटा स्ट्रक्चर में एमोर्टाइज़्ड समय जटिलता डेटा स्ट्रक्चर में एमोर्टाइज़्ड समय जटिलता

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