एमोर्टाइज़्ड एनालिसिस
यह विश्लेषण तब उपयोग किया जाता है जब कभी-कभार होने वाला ऑपरेशन बहुत धीमा होता है, लेकिन अधिकांश ऑपरेशन जो बहुत बार निष्पादित होते हैं, वे तेज़ होते हैं। डेटा संरचनाओं में हमें हैश टेबल, डिसजॉइंट सेट आदि के लिए एमोर्टाइज़्ड विश्लेषण की आवश्यकता होती है।
हैश टेबल में, अधिकांश समय सर्चिंग टाइम कॉम्प्लेक्सिटी O(1) होती है, लेकिन कभी-कभी यह O(n) ऑपरेशन निष्पादित करता है। जब हम हैश टेबल में किसी तत्व को खोजना या डालना चाहते हैं, तो अधिकांश मामलों में यह कॉन्स्टेंट टाइम लेता है, लेकिन जब कॉलिजन होता है, तो कॉलिजन रिज़ॉल्यूशन के लिए O(n) समय के ऑपरेशन की आवश्यकता होती है।
एग्रीगेट मेथड
एग्रीगेट मेथड का उपयोग कुल लागत खोजने के लिए किया जाता है। यदि हम ढेर सारा डेटा जोड़ना चाहते हैं, तो हमें इस फॉर्मूला द्वारा एमोर्टाइज़्ड लागत खोजने की आवश्यकता होती है।
n ऑपरेशन के अनुक्रम के लिए, लागत है -
एमोर्टाइज़्ड एनालिसिस पर उदाहरण
डायनामिक ऐरे के लिए, आइटम को दिए गए इंडेक्स पर O(1) समय में डाला जा सकता है। लेकिन यदि वह इंडेक्स ऐरे में मौजूद नहीं है, तो यह कॉन्स्टेंट टाइम में कार्य करने में विफल रहता है। उस स्थिति में, यह प्रारंभ में ऐरे का आकार दोगुना करता है फिर तत्व डालता है यदि इंडेक्स मौजूद है।
डायनामिक ऐरे के लिए, मान लें 𝑐𝑖 = 𝑖वें इंसर्शन की लागत।
