परिशोधित विश्लेषण: Difference between revisions

Revision as of 22:12, 2 March 2023

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

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

इतिहास

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

विधि

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

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

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

उदाहरण

गतिशील सरणी

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

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

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

श्रेणी

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

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)$ है .^[4]

वैकल्पिक रूप से, हम किसी भी सामग्री को इनपुट सरणी से आउटपुट सरणी में उस सामग्री के लिए पहले के एनक्यू ऑपरेशन में प्रतिलिपि करने की निवेश/व्यय चार्ज कर सकते हैं। यह चार्जिंग योजना एन्क्यू के लिए परिशोधित समय को दोगुना कर देती है किन्तु डीक्यू के लिए परिशोधित समय $O(1)$ को कम कर देती है.

किन्तु डीक्यू के लिए परिशोधित समय $O(1)$ को कम कर देती है.

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

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

संदर्भ

↑ ^1.0 ^1.1 Tarjan, Robert Endre (April 1985). "परिशोधित कम्प्यूटेशनल जटिलता" (PDF). SIAM Journal on Algebraic and Discrete Methods. 6 (2): 306–318. doi:10.1137/0606031.
↑ ^2.0 ^2.1 ^2.2 Rebecca Fiebrink (2007), Amortized Analysis Explained (PDF), archived from the original (PDF) on 20 October 2013, retrieved 3 May 2011
↑ ^3.0 ^3.1 ^3.2 ^3.3 ^3.4 Kozen, Dexter (Spring 2011). "CS 3110 Lecture 20: Amortized Analysis". Cornell University. Retrieved 14 March 2015.
↑ Grossman, Dan. "CSE332: Data Abstractions" (PDF). cs.washington.edu. Retrieved 14 March 2015.

साहित्य

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

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

[tarjan-1] 1.0 ^1.1 Tarjan, Robert Endre (April 1985). "परिशोधित कम्प्यूटेशनल जटिलता" (PDF). SIAM Journal on Algebraic and Discrete Methods. 6 (2): 306–318. doi:10.1137/0606031.

[fiebrink-2] 2.0 ^2.1 ^2.2 Rebecca Fiebrink (2007), Amortized Analysis Explained (PDF), archived from the original (PDF) on 20 October 2013, retrieved 3 May 2011

[Lecture_20-3] 3.0 ^3.1 ^3.2 ^3.3 ^3.4 Kozen, Dexter (Spring 2011). "CS 3110 Lecture 20: Amortized Analysis". Cornell University. Retrieved 14 March 2015.

[Grossman-4] Grossman, Dan. "CSE332: Data Abstractions" (PDF). cs.washington.edu. Retrieved 14 March 2015.

[1]

[2]

[3]

[4]

@@ Line 1: / Line 1: @@
 {{Short description|Method for algorithm analysis in computer science}}
-{{Redirect|Amortized|other uses|Amortization (disambiguation){{!}}Amortization}}
+{{Redirect|परिशोधित|अन्य उपयोग|ऋणपरिशोध(बहुविकल्पी){{!}}ऋणपरिशोध}}
-[[कंप्यूटर विज्ञान]] में, परिशोधित विश्लेषण किसी दिए गए एल्गोरिदम की कम्प्यूटेशनल जटिलता, या कितना संसाधन, विशेष रूप से समय या स्मृति, [[निष्पादन (कंप्यूटिंग)]] में लेता है, एल्गोरिदम के विश्लेषण के लिए एक विधि है। परिशोधित विश्लेषण के लिए प्रेरणा यह है कि सबसे खराब स्थिति वाले रन टाइम को देखना बहुत निराशावादी हो सकता है। इसके अतिरिक्त, परिशोधित विश्लेषण उस क्रम में एक क्रम में संचालन के चलने के समय को औसत करता है।<ref name="tarjan"/>{{rp|306}}
+[[कंप्यूटर विज्ञान]] में, परिशोधित विश्लेषण किसी दिए गए एल्गोरिदम की कम्प्यूटेशनल जटिलता, या कितना संसाधन, विशेष रूप से समय या स्मृति, [[निष्पादन (कंप्यूटिंग)]] में लेता है, एल्गोरिदम के विश्लेषण के लिए एक विधि है। परिशोधित विश्लेषण के लिए प्रेरणा यह है कि सबसे खराब स्थिति वाले रन टाइम को देखना बहुत निराशावादी हो सकता है। इसके अतिरिक्त, परिशोधित विश्लेषण उस क्रम में एक क्रम में संचालन के चलने के समय को औसत करता है।<ref name="tarjan"/>{{rp|306}} एक निष्कर्ष के रूप में: परिशोधित विश्लेषण उपयोगी उपकरण है जो अन्य विधि जैसे वर्स्ट-केस निष्पादन समय|वर्स्ट-केस और औसत-केस जटिलता|औसत-केस विश्लेषण का पूरक है।<ref name="fiebrink"/>{{rp|14}}
-एक निष्कर्ष के रूप में: परिशोधित विश्लेषण उपयोगी उपकरण है जो अन्य विधि ों जैसे वर्स्ट-केस निष्पादन समय|वर्स्ट-केस और औसत-केस जटिलता|औसत-केस विश्लेषण का पूरक है।<ref name="fiebrink"/>{{rp|14}}
-एक एल्गोरिथम के दिए गए संचालन के लिए, कुछ स्थितियों (जैसे, इनपुट पैरामीट्रिजेशन या डेटा संरचना सामग्री) संसाधनों में महत्वपूर्ण निवेश/व्यय का संकेत दे सकती हैं, जबकि अन्य स्थितियां उतनी महंगी नहीं हो सकती हैं। परिशोधित विश्लेषण संचालन के पूरे अनुक्रम पर साथ महंगा और कम खर्चीला संचालन दोनों पर विचार करता है। इसमें विभिन्न प्रकार के इनपुट, इनपुट की लंबाई और इसके प्रदर्शन को प्रभावित करने वाले अन्य कारकों के लिए लेखांकन सम्मिलित  हो सकता है।<ref name="fiebrink">{{Citation |url=http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf |title=Amortized Analysis Explained |author=Rebecca Fiebrink |year=2007 |access-date=2011-05-03 |archive-url=https://web.archive.org/web/20131020020356/http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf |archive-date=20 October 2013 |url-status=dead }}</ref>
+एक एल्गोरिथम के दिए गए संचालन के लिए, कुछ स्थितियों (जैसे, इनपुट पैरामीट्रिजेशन या डेटा संरचना सामग्री) संसाधनों में महत्वपूर्ण निवेश/व्यय का संकेत दे सकती हैं, जबकि अन्य स्थितियां उतनी बहुमूल्य नहीं हो सकती हैं। परिशोधित विश्लेषण संचालन के पूरे अनुक्रम पर साथ महंगा और कम खर्चीला संचालन दोनों पर विचार करता है। इसमें विभिन्न प्रकार के इनपुट, इनपुट की लंबाई और इसके प्रदर्शन को प्रभावित करने वाले अन्य कारकों के लिए लेखांकन सम्मिलित  हो सकता है।<ref name="fiebrink">{{Citation |url=http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf |title=Amortized Analysis Explained |author=Rebecca Fiebrink |year=2007 |access-date=2011-05-03 |archive-url=https://web.archive.org/web/20131020020356/http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf |archive-date=20 October 2013 |url-status=dead }}</ref>
 == इतिहास ==
-परिशोधित विश्लेषण शुरू में समग्र विश्लेषण नामक विधि से उभरा, जिसे अब परिशोधित विश्लेषण द्वारा सम्मिलित किया गया है। इस विधि  को पहली बार औपचारिक रूप से [[रॉबर्ट टार्जन]] ने अपने 1985 के पेपर अमोर्टाइज्ड कम्प्यूटेशनल कॉम्प्लेक्सिटी में किया था।<ref name="tarjan">{{cite journal|last=Tarjan|first=Robert Endre|author-link=Robert Tarjan|title=परिशोधित कम्प्यूटेशनल जटिलता|journal=SIAM Journal on Algebraic and Discrete Methods|date=April 1985|volume=6|issue=2|pages=306–318|doi=10.1137/0606031|url=http://www.cs.duke.edu/courses/fall11/cps234/reading/Tarjan85_AmortizedComplexity.pdf}}<!--was:http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/Amortized.pdf--></ref> जिसने उपयोग की जाने वाली सामान्य संभाव्य विधियों की तुलना में विश्लेषण के अधिक उपयोगी रूप की आवश्यकता को संबोधित किया। परिशोधन का उपयोग शुरू में बहुत विशिष्ट प्रकार के एल्गोरिदम के लिए किया गया था, विशेष रूप से [[बाइनरी ट्री]] और यूनियन (कंप्यूटर साइंस) संचालन से जुड़े। यद्यपि, यह अब सर्वव्यापी है और कई अन्य एल्गोरिदम का विश्लेषण करते समय भी काम आता है।<ref name="fiebrink"/>
+परिशोधित विश्लेषण प्रारंभ में समग्र विश्लेषण नामक विधि से उभरा, जिसे अब परिशोधित विश्लेषण द्वारा सम्मिलित किया गया है। इस विधि  को पहली बार औपचारिक रूप से [[रॉबर्ट टार्जन]] ने अपने 1985 के पेपर अमोर्टाइज्ड कम्प्यूटेशनल कॉम्प्लेक्सिटी में किया था।<ref name="tarjan">{{cite journal|last=Tarjan|first=Robert Endre|author-link=Robert Tarjan|title=परिशोधित कम्प्यूटेशनल जटिलता|journal=SIAM Journal on Algebraic and Discrete Methods|date=April 1985|volume=6|issue=2|pages=306–318|doi=10.1137/0606031|url=http://www.cs.duke.edu/courses/fall11/cps234/reading/Tarjan85_AmortizedComplexity.pdf}}<!--was:http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/Amortized.pdf--></ref> जिसने उपयोग की जाने वाली सामान्य संभाव्य विधियों की तुलना में विश्लेषण के अधिक उपयोगी रूप की आवश्यकता को संबोधित किया। परिशोधन का उपयोग प्रारंभ में बहुत विशिष्ट प्रकार के एल्गोरिदम के लिए किया गया था, विशेष रूप से [[बाइनरी ट्री]] और यूनियन (कंप्यूटर साइंस) संचालन से जुड़े। यद्यपि, यह अब सर्वव्यापी है और कई अन्य एल्गोरिदम का विश्लेषण करते समय भी काम आता है।<ref name="fiebrink"/>
 == विधि ==
-{{main|Accounting method (computer science)|Potential method}}
+{{main|लेखा विधि (कंप्यूटर विज्ञान)|संभावित विधि}}
-परिशोधित विश्लेषण के लिए ज्ञान की आवश्यकता होती है कि किस श्रृंखला के संचालन संभव हैं। यह सामान्यतः पर [[डेटा संरचना]]ओं के मामले में होता है, जिसमें स्थिति (कंप्यूटर विज्ञान) होती है जो संचालन के बीच बनी रहती है। मूल विचार यह है कि सबसे खराब स्थिति ऑपरेशन राज्य को इस तरह से बदल सकता है कि सबसे खराब स्थिति फिर से लंबे समय तक नहीं हो सकती है, इस प्रकार इसकी निवेश/व्यय को परिशोधित किया जा सकता है।
+परिशोधित विश्लेषण के लिए ज्ञान की आवश्यकता होती है कि किस श्रृंखला के संचालन संभव हैं। यह सामान्यतः पर [[डेटा संरचना]]ओं के स्थति में होता है, जिसमें स्थिति (कंप्यूटर विज्ञान) होती है जो संचालन के बीच बनी रहती है। मूल विचार यह है कि सबसे खराब स्थिति ऑपरेशन राज्य को इस तरह से बदल सकता है कि सबसे खराब स्थिति फिर से लंबे समय तक नहीं हो सकती है, इस प्रकार इसकी निवेश/व्यय को परिशोधित किया जा सकता है।
 परिशोधित विश्लेषण करने के लिए सामान्यतः तीन विधियाँ हैं: कुल विधि, [[लेखा पद्धति]] और संभावित विधि। ये सभी सही उत्तर देते हैं; किसका उपयोग करना है यह इस बात पर निर्भर करता है कि किसी विशेष स्थिति के लिए कौन सा सबसे सुविधाजनक है।<ref name="Lecture 20">{{cite web|url=http://www.cs.cornell.edu/courses/cs3110/2011sp/lectures/lec20-amortized/amortized.htm|title=CS 3110 Lecture 20: Amortized Analysis|last=Kozen|first=Dexter|date=Spring 2011|publisher=[[Cornell University]]|access-date=14 March 2015}}</ref>
-*कुल विश्लेषण एन संचालन के अनुक्रम की कुल निवेश/व्यय पर ऊपरी सीमा टी (एन) निर्धारित करता है, फिर टी (एन) / एन होने के लिए परिशोधित निवेश/व्यय की गणना करता है।<ref name="Lecture 20"/>*लेखांकन पद्धति (कंप्यूटर विज्ञान) समग्र विश्लेषण का रूप है जो प्रत्येक ऑपरेशन को परिशोधित निवेश/व्यय प्रदान करता है जो इसकी वास्तविक निवेश/व्यय से भिन्न हो सकती है। प्रारंभिकुआती परिचालनों में उनकी वास्तविक निवेश/व्यय से अधिक परिशोधित निवेश/व्यय होती है, जो सहेजे गए क्रेडिट को जमा करता है जो बाद के संचालन के लिए भुगतान करता है, जिनकी परिशोधन निवेश/व्यय उनकी वास्तविक निवेश/व्यय से कम होती है। क्योंकि क्रेडिट शून्य से शुरू होता है, संचालन के अनुक्रम की वास्तविक निवेश/व्यय परिशोधित निवेश/व्यय घटा संचित क्रेडिट के बराबर होती है। क्योंकि क्रेडिट गैर-नकारात्मक होना आवश्यक है, परिशोधित निवेश/व्यय वास्तविक निवेश/व्यय पर ऊपरी सीमा होती है। सामान्यतः, कई शॉर्ट-रनिंग ऑपरेशंस इस तरह के क्रेडिट को छोटे वेतन वृद्धि में जमा करते हैं, जबकि लंबे समय तक चलने वाले ऑपरेशन इसे अधिक  कम कर देते हैं।<ref name="Lecture 20"/>*पोटेंशियल मेथड अकाउंटिंग मेथड का रूप है जहां सेव्ड क्रेडिट की गणना डेटा स्ट्रक्चर की स्थिति के फंक्शन (संभावित) के रूप में की जाती है। परिशोधित निवेश/व्यय तत्काल निवेश/व्यय और क्षमता में परिवर्तन है।<ref name="Lecture 20"/>
+*कुल विश्लेषण एन संचालन के अनुक्रम की कुल निवेश/व्यय पर ऊपरी सीमा टी (एन) निर्धारित करता है, फिर टी (एन) / एन होने के लिए परिशोधित निवेश/व्यय की गणना करता है।<ref name="Lecture 20"/>
+*लेखांकन पद्धति (कंप्यूटर विज्ञान) समग्र विश्लेषण का रूप है जो प्रत्येक ऑपरेशन को परिशोधित निवेश/व्यय प्रदान करता है जो इसकी वास्तविक निवेश/व्यय से भिन्न हो सकती है। प्रारंभिक  परिचालनों में उनकी वास्तविक निवेश/व्यय से अधिक परिशोधित निवेश/व्यय होती है, जो सहेजे गए क्रेडिट को जमा करता है जो बाद के संचालन के लिए भुगतान करता है, जिनकी परिशोधन निवेश/व्यय उनकी वास्तविक निवेश/व्यय से कम होती है। क्योंकि क्रेडिट शून्य से प्रारंभ होता है, संचालन के अनुक्रम की वास्तविक निवेश/व्यय परिशोधित निवेश/व्यय घटा संचित क्रेडिट के सामान्य होती है। क्योंकि क्रेडिट गैर-नकारात्मक होना आवश्यक है, परिशोधित निवेश/व्यय वास्तविक निवेश/व्यय पर ऊपरी सीमा होती है। सामान्यतः, कई शॉर्ट-रनिंग ऑपरेशंस इस तरह के क्रेडिट को छोटे वेतन वृद्धि में जमा करते हैं, जबकि लंबे समय तक चलने वाले ऑपरेशन इसे अधिक  कम कर देते हैं।<ref name="Lecture 20" />
+*पोटेंशियल मेथड अकाउंटिंग मेथड का रूप है जहां सेव्ड क्रेडिट की गणना डेटा स्ट्रक्चर की स्थिति के फंक्शन (संभावित) के रूप में की जाती है। परिशोधित निवेश/व्यय तत्काल निवेश/व्यय और क्षमता में परिवर्तन है।<ref name="Lecture 20" />
@@ Line 22: / Line 23: @@
 === गतिशील सरणी ===
-[[File:AmortizedPush.png|thumb|right|270px|एक गतिशील सरणी के लिए पुश ऑपरेशन का परिशोधित विश्लेषण]]एक [[गतिशील सरणी]] पर विचार करें जो आकार में बढ़ता है क्योंकि इसमें अधिक तत्व जोड़े जाते हैं, जैसे {{code|ArrayList}} जावा में या {{code|std::vector}} सी ++ में। यदि हम आकार 4 के गतिशील सरणी के साथ शुरू करते हैं, तो हम इसमें 4 तत्वों को धकेल सकते हैं, और प्रत्येक ऑपरेशन में [[निरंतर समय]] लगेगा। फिर भी उस सरणी पर पाँचवें तत्व को धकेलने में अधिक समय लगेगा क्योंकि सरणी को वर्तमान आकार (8) के दोगुने का नया सरणी बनाना होगा, पुराने तत्वों को नए सरणी पर कॉपी करना होगा, और फिर नया तत्व जोड़ना होगा। अगले तीन पुश ऑपरेशंस में इसी तरह निरंतर समय लगेगा, और फिर बाद के जोड़ के लिए सरणी आकार के और धीमे दोहरीकरण की आवश्यकता होगी।
+[[File:AmortizedPush.png|thumb|right|270px|एक गतिशील सरणी के लिए पुश ऑपरेशन का परिशोधित विश्लेषण]]एक [[गतिशील सरणी]] पर विचार करें जो आकार में बढ़ता है क्योंकि इसमें अधिक तत्व जोड़े जाते हैं, जैसे {{code|ArrayList}} जावा में या {{code|std::vector}} सी ++ में। यदि हम आकार 4 के गतिशील सरणी के साथ प्रारंभ करते हैं, तो हम इसमें 4 तत्वों को धकेल सकते हैं, और प्रत्येक ऑपरेशन में [[निरंतर समय]] लगेगा। फिर भी उस सरणी पर पाँचवें तत्व को धकेलने में अधिक समय लगेगा क्योंकि सरणी को वर्तमान आकार (8) के दोगुने का नया सरणी बनाना होगा, पुराने तत्वों को नए सरणी पर प्रतिलिपि करना होगा, और फिर नया तत्व जोड़ना होगा। अगले तीन पुश ऑपरेशंस में इसी तरह निरंतर समय लगेगा, और फिर बाद के जोड़ के लिए सरणी आकार के और धीमे दोहरीकरण की आवश्यकता होगी।
-सामान्यतः यदि हम n + 1 को आकार n की सरणी में पुश की मनमानी संख्या पर विचार करते हैं, तो हम देखते हैं कि पुश ऑपरेशंस में अंतिम समय को छोड़कर निरंतर समय लगता है जो बिग ओ नोटेशन लेता है।{{tmath|\Theta(n)}} आकार दोहरीकरण ऑपरेशन करने का समय। चूँकि कुल n + 1 ऑपरेशन थे, इसलिए हम इसका औसत ले सकते हैं और पा सकते हैं कि डायनेमिक एरे पर पुशिंग एलिमेंट्स लगते हैं: <math>\tfrac{n\Theta(1)+\Theta(n)}{n+1} = \Theta(1)</math>, निरंतर समय।<ref name="Lecture 20" />
+सामान्यतः यदि हम n + 1 को आकार n की सरणी में पुश की इच्छानुसार संख्या पर विचार करते हैं, तो हम देखते हैं कि पुश ऑपरेशंस में अंतिम समय को छोड़कर निरंतर समय लगता है जो बिग ओ नोटेशन लेता है।{{tmath|\Theta(n)}} आकार दोहरीकरण ऑपरेशन करने का समय। चूँकि कुल n + 1 ऑपरेशन थे, इसलिए हम इसका औसत ले सकते हैं और पा सकते हैं कि गतिशील सरणी पर पुशिंग एलिमेंट्स लगते हैं: <math>\tfrac{n\Theta(1)+\Theta(n)}{n+1} = \Theta(1)</math>, निरंतर समय।<ref name="Lecture 20" />
-=== कतार ===
+=== श्रेणी ===
-दिखाया गया [[कतार (सार डेटा प्रकार)]], एक [[फीफो (कंप्यूटिंग और इलेक्ट्रॉनिक्स)]] का रूबी कार्यान्वयन है:
+दिखाया गया [[कतार (सार डेटा प्रकार)|श्रेणी (सार डेटा प्रकार)]], एक [[फीफो (कंप्यूटिंग और इलेक्ट्रॉनिक्स)]] का रूबी कार्यान्वयन है:
 <syntaxhighlight lang="ruby">
 class Queue
@@ Line 53: / Line 54: @@
 एन्क्यू ऑपरेशन सिर्फ तत्व को इनपुट ऐरे पर धकेलता है; यह ऑपरेशन इनपुट या आउटपुट की लंबाई पर निर्भर नहीं करता है और इसलिए निरंतर समय में चलता है।
-चूंकि डेक्यू ऑपरेशन अधिक जटिल है। यदि आउटपुट ऐरे में पहले से ही कुछ तत्व हैं, तो डेक्यू निरंतर समय में चलता है; अन्यथा, डेक्यू लेता है {{tmath|O(n)}} इनपुट सरणी से आउटपुट सरणी पर सभी तत्वों को जोड़ने का समय, जहां n इनपुट सरणी की वर्तमान लंबाई है। इनपुट से एन तत्वों की प्रतिलिपि बनाने के बाद, हम एन डेक्यू ऑपरेशन कर सकते हैं, प्रत्येक आउटपुट सरणी फिर से खाली होने से पहले निरंतर समय लेता है। इस प्रकार, हम केवल n dequeue संचालन का क्रम कर सकते हैं {{tmath|O(n)}} समय, जिसका तात्पर्य है कि प्रत्येक डेक्यू ऑपरेशन का परिशोधित समय है {{tmath|O(1)}}.<ref name=Grossman>{{cite web|last1=Grossman|first1=Dan|title=CSE332: Data Abstractions|url=http://courses.cs.washington.edu/courses/cse332/10sp/lectures/lecture21.pdf|website=cs.washington.edu|access-date=14 March 2015}}</ref>
+चूंकि डेक्यू ऑपरेशन अधिक जटिल है। यदि आउटपुट ऐरे में पहले से ही कुछ तत्व हैं, तो डेक्यू निरंतर समय में चलता है; अन्यथा, डेक्यू लेता है {{tmath|O(n)}} इनपुट सरणी से आउटपुट सरणी पर सभी तत्वों को जोड़ने का समय, जहां n इनपुट सरणी की वर्तमान लंबाई है। इनपुट से एन तत्वों की प्रतिलिपि बनाने के बाद, हम एन डेक्यू ऑपरेशन कर सकते हैं, प्रत्येक आउटपुट सरणी फिर से खाली होने से पहले निरंतर समय लेता है। इस प्रकार, हम केवल n विपंक्ति संचालन का क्रम कर सकते हैं {{tmath|O(n)}} समय, जिसका तात्पर्य है कि प्रत्येक डेक्यू ऑपरेशन का परिशोधित समय {{tmath|O(1)}} है .<ref name=Grossman>{{cite web|last1=Grossman|first1=Dan|title=CSE332: Data Abstractions|url=http://courses.cs.washington.edu/courses/cse332/10sp/lectures/lecture21.pdf|website=cs.washington.edu|access-date=14 March 2015}}</ref>
-वैकल्पिक रूप से, हम किसी भी आइटम को इनपुट एरे से आउटपुट एरे में उस आइटम के लिए पहले के एनक्यू ऑपरेशन में कॉपी करने की निवेश/व्यय चार्ज कर सकते हैं। यह चार्जिंग योजना एन्क्यू के लिए परिशोधित समय को दोगुना कर देती है किन्तुडीक्यू के लिए परिशोधित समय को कम कर देती है {{tmath|O(1)}}.
+वैकल्पिक रूप से, हम किसी भी सामग्री को इनपुट सरणी से आउटपुट सरणी में उस सामग्री के लिए पहले के एनक्यू ऑपरेशन में प्रतिलिपि करने की निवेश/व्यय चार्ज कर सकते हैं। यह चार्जिंग योजना एन्क्यू के लिए परिशोधित समय को दोगुना कर देती है किन्तु डीक्यू के लिए परिशोधित समय {{tmath|O(1)}} को कम कर देती है.
+'''किन्तु डीक्यू के लिए परिशोधित समय {{tmath|O(1)}} को कम कर देती है.'''
 == सामान्य उपयोग ==

Anonymous

Search

परिशोधित विश्लेषण: Difference between revisions

Namespaces

More

Page actions

Revision as of 22:12, 2 March 2023

Contents

इतिहास

विधि

उदाहरण

गतिशील सरणी

श्रेणी

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

संदर्भ

साहित्य

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

परिशोधित विश्लेषण: Difference between revisions

Revision as of 22:12, 2 March 2023

इतिहास

विधि

उदाहरण

गतिशील सरणी

श्रेणी

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

संदर्भ

साहित्य

Navigation

Wiki tools

Page tools

Other projects

Hidden categories