Table of Contents
गतिशील सरणी डेटा संरचनाएं हैं जो स्वचालित रूप से जब वे क्षमता तक पहुंचते हैं तो आकार बदलती हैं। उनकी कम लागत को समझना कई कार्यों पर अपनी दक्षता का मूल्यांकन करने में मदद करता है।
Amortized Cost क्या है?
amortized लागत आपरेशन के एक अनुक्रम पर प्रति आपरेशन औसत लागत है। यह कई सस्ती आपरेशनों में उन्हें वितरित करके सामयिक आकार की उच्च लागत को बाहर कर देता है।
गतिशील ऐरे ऑपरेशन
गतिशील सरणी पर सामान्य संचालन में सम्मिलन, हटाने और आकार शामिल हैं। अंत में सम्मिलन आम तौर पर सबसे अधिक बार ऑपरेशन होता है, जो क्षमता से अधिक होने पर आकार देने को ट्रिगर कर सकता है।
Amortized Cost की गणना
जब तत्वों को सम्मिलित किया जाता है, तो सरणी पूर्ण होने पर आकार में दोगुनी हो जाती है। आकार देने की लागत में नए सरणी में सभी मौजूदा तत्वों की प्रतिलिपि शामिल है। हालांकि आकार देने की लागत महंगा है, यह अक्सर होता है।
उदाहरण के लिए, यदि एक सरणी क्षमता 1 के साथ शुरू होती है, तो एकाधिक सम्मिलन पर लागत को आकार देने का अनुक्रम निम्नानुसार संक्षेप में प्रस्तुत किया जा सकता है:
- 1 तत्व डालें: लागत 1
- दूसरा तत्व डालें: आकार बदलें (लागत 1), कुल लागत 2
- 3rd तत्व डालें: आकार बदलें (लागत 2), कुल लागत 3
- 4th तत्व डालें: आकार बदलें (लागत 4), कुल लागत 4
कुल लागत n सम्मिलन पर 2n के बराबर है, जिससे लगभग O (1) प्रति सम्मिलन लागत होती है।