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

"Amortized" redirects here. For other uses, see Amortization.

कंप्यूटर विज्ञान में, परिशोधित विश्लेषण किसी दिए गए एल्गोरिदम की कम्प्यूटेशनल जटिलता, या कितना संसाधन, विशेष रूप से समय या स्मृति, निष्पादन (कंप्यूटिंग) में लेता है, एल्गोरिदम के विश्लेषण के लिए एक विधि है। परिशोधित विश्लेषण के लिए प्रेरणा यह है कि सबसे खराब स्थिति वाले रन टाइम को देखना बहुत निराशावादी हो सकता है। इसके बजाय, परिशोधित विश्लेषण उस क्रम में एक क्रम में संचालन के चलने के समय को औसत करता है। एक निष्कर्ष के रूप में: परिशोधित विश्लेषण एक उपयोगी उपकरण है जो अन्य तकनीकों जैसे वर्स्ट-केस निष्पादन समय|वर्स्ट-केस और औसत-केस जटिलता|औसत-केस विश्लेषण का पूरक है।

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

इतिहास

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

विधि

Main articles: Accounting method (computer science) and Potential method

परिशोधित विश्लेषण के लिए ज्ञान की आवश्यकता होती है कि किस श्रृंखला के संचालन संभव हैं। यह आमतौर पर डेटा संरचनाओं के मामले में होता है, जिसमें स्थिति (कंप्यूटर विज्ञान) होती है जो संचालन के बीच बनी रहती है। मूल विचार यह है कि सबसे खराब स्थिति ऑपरेशन राज्य को इस तरह से बदल सकता है कि सबसे खराब स्थिति फिर से लंबे समय तक नहीं हो सकती है, इस प्रकार इसकी लागत को परिशोधित किया जा सकता है।

परिशोधित विश्लेषण करने के लिए आम तौर पर तीन विधियाँ हैं: कुल विधि, लेखा पद्धति और संभावित विधि। ये सभी सही उत्तर देते हैं; किसका उपयोग करना है यह इस बात पर निर्भर करता है कि किसी विशेष स्थिति के लिए कौन सा सबसे सुविधाजनक है।

• कुल विश्लेषण एन संचालन के अनुक्रम की कुल लागत पर ऊपरी सीमा टी (एन) निर्धारित करता है, फिर टी (एन) / एन होने के लिए परिशोधित लागत की गणना करता है।*लेखांकन पद्धति (कंप्यूटर विज्ञान) समग्र विश्लेषण का एक रूप है जो प्रत्येक ऑपरेशन को एक परिशोधित लागत प्रदान करता है जो इसकी वास्तविक लागत से भिन्न हो सकती है। शुरुआती परिचालनों में उनकी वास्तविक लागत से अधिक परिशोधित लागत होती है, जो एक सहेजे गए क्रेडिट को जमा करता है जो बाद के संचालन के लिए भुगतान करता है, जिनकी परिशोधन लागत उनकी वास्तविक लागत से कम होती है। क्योंकि क्रेडिट शून्य से शुरू होता है, संचालन के अनुक्रम की वास्तविक लागत परिशोधित लागत घटा संचित क्रेडिट के बराबर होती है। क्योंकि क्रेडिट गैर-नकारात्मक होना आवश्यक है, परिशोधित लागत वास्तविक लागत पर ऊपरी सीमा होती है। आम तौर पर, कई शॉर्ट-रनिंग ऑपरेशंस इस तरह के क्रेडिट को छोटे वेतन वृद्धि में जमा करते हैं, जबकि लंबे समय तक चलने वाले ऑपरेशन इसे काफी कम कर देते हैं।*पोटेंशियल मेथड अकाउंटिंग मेथड का एक रूप है जहां सेव्ड क्रेडिट की गणना डेटा स्ट्रक्चर की स्थिति के एक फंक्शन (संभावित) के रूप में की जाती है। परिशोधित लागत तत्काल लागत और क्षमता में परिवर्तन है।

उदाहरण

गतिशील सरणी

एक गतिशील सरणी के लिए पुश ऑपरेशन का परिशोधित विश्लेषण

एक गतिशील सरणी पर विचार करें जो आकार में बढ़ता है क्योंकि इसमें अधिक तत्व जोड़े जाते हैं, जैसे ArrayList जावा में या std::vector सी ++ में। यदि हम आकार 4 के एक गतिशील सरणी के साथ शुरू करते हैं, तो हम इसमें 4 तत्वों को धकेल सकते हैं, और प्रत्येक ऑपरेशन में निरंतर समय लगेगा। फिर भी उस सरणी पर पाँचवें तत्व को धकेलने में अधिक समय लगेगा क्योंकि सरणी को वर्तमान आकार (8) के दोगुने का एक नया सरणी बनाना होगा, पुराने तत्वों को नए सरणी पर कॉपी करना होगा, और फिर नया तत्व जोड़ना होगा। अगले तीन पुश ऑपरेशंस में इसी तरह निरंतर समय लगेगा, और फिर बाद के जोड़ के लिए सरणी आकार के एक और धीमे दोहरीकरण की आवश्यकता होगी।

सामान्य तौर पर यदि हम n + 1 को आकार n की एक सरणी में पुश की मनमानी संख्या पर विचार करते हैं, तो हम देखते हैं कि पुश ऑपरेशंस में अंतिम समय को छोड़कर निरंतर समय लगता है जो बिग ओ नोटेशन लेता है।$\Theta (n)$ आकार दोहरीकरण ऑपरेशन करने का समय। चूँकि कुल n + 1 ऑपरेशन थे, इसलिए हम इसका औसत ले सकते हैं और पा सकते हैं कि डायनेमिक एरे पर पुशिंग एलिमेंट्स लगते हैं: ${\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)$, निरंतर समय।

कतार

दिखाया गया एक कतार (सार डेटा प्रकार), एक फीफो (कंप्यूटिंग और इलेक्ट्रॉनिक्स) का रूबी कार्यान्वयन है:

class Queue
  def initialize
    @input = []
    @output = []
  end

  def enqueue(element)
    @input << element
  end

  def dequeue
    if @output.empty?
      while @input.any?
        @output << @input.pop
      end
    end

    @output.pop
  end
end

एन्क्यू ऑपरेशन सिर्फ एक तत्व को इनपुट ऐरे पर धकेलता है; यह ऑपरेशन इनपुट या आउटपुट की लंबाई पर निर्भर नहीं करता है और इसलिए निरंतर समय में चलता है।

हालांकि डेक्यू ऑपरेशन अधिक जटिल है। यदि आउटपुट ऐरे में पहले से ही कुछ तत्व हैं, तो डेक्यू निरंतर समय में चलता है; अन्यथा, डेक्यू लेता है $O(n)$ इनपुट सरणी से आउटपुट सरणी पर सभी तत्वों को जोड़ने का समय, जहां n इनपुट सरणी की वर्तमान लंबाई है। इनपुट से एन तत्वों की प्रतिलिपि बनाने के बाद, हम एन डेक्यू ऑपरेशन कर सकते हैं, प्रत्येक आउटपुट सरणी फिर से खाली होने से पहले निरंतर समय लेता है। इस प्रकार, हम केवल n dequeue संचालन का क्रम कर सकते हैं $O(n)$ समय, जिसका तात्पर्य है कि प्रत्येक डेक्यू ऑपरेशन का परिशोधित समय है $O(1)$. वैकल्पिक रूप से, हम किसी भी आइटम को इनपुट एरे से आउटपुट एरे में उस आइटम के लिए पहले के एनक्यू ऑपरेशन में कॉपी करने की लागत चार्ज कर सकते हैं। यह चार्जिंग योजना एन्क्यू के लिए परिशोधित समय को दोगुना कर देती है लेकिन डीक्यू के लिए परिशोधित समय को कम कर देती है $O(1)$.

सामान्य उपयोग

• सामान्य उपयोग में, एक परिशोधित एल्गोरिथ्म वह है जिसे एक परिशोधित विश्लेषण ने अच्छा प्रदर्शन करने के लिए दिखाया है।
• ऑनलाइन एल्गोरिदम आमतौर पर परिशोधित विश्लेषण का उपयोग करते हैं।

साहित्य

• "व्याख्यान 7: परिशोधित विश्लेषण" (PDF). Carnegie Mellon University. Retrieved 14 March 2015.
• Allan Borodin and Ran El-Yaniv (1998). ऑनलाइन संगणना और प्रतिस्पर्धी विश्लेषण. pp. 20, 141.

श्रेणी:एल्गोरिदम का विश्लेषण श्रेणी:रूबी कोड उदाहरण के साथ लेख श्रेणी:परिशोधित डेटा संरचनाएं