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

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

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

इतिहास

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

विधि

Main articles: लेखा विधि (कंप्यूटर विज्ञान) and संभावित विधि

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

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

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

उदाहरण

गतिशील सरणी

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

एक गतिशील सरणी पर विचार करें जो आकार में बढ़ता है क्योंकि इसमें अधिक तत्व जोड़े जाते हैं, जैसे 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 विपंक्ति संचालन का क्रम कर सकते हैं $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.