डेटा संरचनाओं में परिशोधित समय जटिलता

परिशोधन विश्लेषण

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

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

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

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

n संचालन के अनुक्रम के लिए, लागत है -

$\frac{लागत ( n\:ऑपरेशंस)}{n}=\frac{लागत (सामान्य\:ऑपरेशंस)+लागत (महंगा\:ऑपरेशंस)}{n}$

परिशोधन विश्लेषण पर उदाहरण

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

गतिशील सरणी के लिए, ci =ith प्रविष्टि की लागत दें।

$So\:ci=1+\ start{cases}i\:-\:1,if\:i-1\:is\:power\:of\:2 \\0, \:\:\:\ :\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:अन्यथा \end{मामलों}$

$$\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}$$