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

एमोर्टाइज़्ड विश्लेषण

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

हैश-टेबल में, अधिकांश समय खोज समय जटिलता O(1) होती है, लेकिन कभी-कभी यह O(n) ऑपरेशन्स निष्पादित करता है। जब हम हैश टेबल में किसी एलिमेंट को खोजना या इन्सर्ट करना चाहते हैं, तो अधिकांश मामलों में यह कॉन्स्टेंट टाइम लेने वाला कार्य है, लेकिन जब कोलिजन होती है, तो कोलिजन रिजॉल्यूशन के लिए O(n) समय के ऑपरेशन्स की आवश्यकता होती है।

एग्रीगेट मेथड

एग्रीगेट मेथड का उपयोग कुल लागत खोजने के लिए किया जाता है। यदि हम डेटा का एक समूह जोड़ना चाहते हैं, तो हमें इस सूत्र द्वारा एमोर्टाइज़्ड लागत ढूंढनी होगी।

n ऑपरेशन्स के सीक्वेंस के लिए, लागत है:

$\frac{Cost (n\:operations)}{n}=\frac{Cost (normal\:operations)+Cost (Expensive\:operations)}{n}$

एमोर्टाइज़्ड विश्लेषण पर उदाहरण

एक डायनामिक सरणी के लिए, आइटम दिए गए इंडेक्स पर O(1) समय में इन्सर्ट किए जा सकते हैं। लेकिन यदि वह इंडेक्स सरणी में मौजूद नहीं है, तो यह कॉन्स्टेंट टाइम में कार्य करने में विफल रहता है। उस मामले में, यह प्रारंभ में सरणी का आकार दोगुना करता है फिर एलिमेंट को इन्सर्ट करता है यदि इंडेक्स मौजूद है।

डायनामिक सरणी के लिए, मान लीजिए ci = ith इन्सर्शन की लागत।

$So\:ci=1+\begin{cases}i\:-\:1,if\:i-1\:is\:power\:of\:2 \\0, \:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:Otherwise\end{cases}$

$$\frac{\displaystyle\sum\limits_{i=1}^n ci}{n}\leq\frac{n+\displaystyle\sum\limits_{j=1}^{\lfloor\log{2}{\lgroup n-1\rgroup}\rfloor} 2j}{n}=\frac{O\lgroup n\rgroup}{n}$$