लेखांकन पद्धति (कंप्यूटर विज्ञान)

For accounting methods in business and financial reporting, see basis of accounting.

कंप्यूटर विज्ञान में एल्गोरिदम के विश्लेषण के क्षेत्र में, लेखांकन पद्धति लेखांकन पर आधारित परिशोधन विश्लेषण की एक विधि है। लेखांकन विधि अक्सर समग्र विश्लेषण या संभावित विधि की तुलना में किसी ऑपरेशन की परिशोधित लागत का अधिक सहज विवरण देती है। हालाँकि, ध्यान दें कि यह इस बात की गारंटी नहीं देता है कि ऐसा विश्लेषण तुरंत स्पष्ट हो जाएगा; अक्सर, लेखांकन पद्धति के लिए सही मापदंडों को चुनने के लिए समस्या के उतने ही ज्ञान की आवश्यकता होती है और जटिलता की सीमा को अन्य दो तरीकों के रूप में साबित करने का प्रयास किया जाता है।

समय पर बाध्य बिग ओ अंकन (1) को साबित करने के लिए लेखांकन पद्धति सबसे स्वाभाविक रूप से उपयुक्त है। यहां बताई गई विधि ऐसे बंधन को सिद्ध करने के लिए है।

विधि

कलन विधि में उपयोग किए जाने वाले प्राथमिक परिचालनों का एक सेट चुना जाता है और उनकी लागत मनमाने ढंग से 1 पर सेट की जाती है। तथ्य यह है कि इन परिचालनों की लागत वास्तविकता में भिन्न हो सकती है, सिद्धांत रूप में कोई कठिनाई नहीं होती है। महत्वपूर्ण बात यह है कि प्रत्येक प्रारंभिक ऑपरेशन की एक स्थिर लागत होती है।

प्रत्येक समग्र परिचालन को एक भुगतान सौंपा गया है। भुगतान का उद्देश्य इस विशेष ऑपरेशन को पूरा करने के लिए आवश्यक प्रारंभिक संचालन की लागत को कवर करना है, शेष भुगतान में से कुछ को बाद में उपयोग करने के लिए एक पूल में रखा जाएगा।

जिन समस्याओं के लिए परिशोधन विश्लेषण की आवश्यकता होती है, उनमें कठिनाई यह है कि, सामान्य तौर पर, कुछ कार्यों के लिए स्थिर लागत से अधिक की आवश्यकता होगी। इसका मतलब यह है कि कोई भी निरंतर भुगतान किसी ऑपरेशन की सबसे खराब स्थिति की लागत को कवर करने के लिए पर्याप्त नहीं होगा। हालाँकि, भुगतान के उचित चयन के साथ, यह अब कोई कठिनाई नहीं है; महंगे ऑपरेशन तभी होंगे जब पूल में उनकी लागत को कवर करने के लिए पर्याप्त भुगतान होगा।

उदाहरण

कुछ उदाहरण लेखांकन पद्धति के उपयोग को समझाने में मदद करेंगे।

तालिका विस्तार

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

प्रक्रिया को विस्तार से देखने से पहले, हमें कुछ परिभाषाओं की आवश्यकता है। होने देना T एक टेबल बनो, E सम्मिलित करने के लिए एक तत्व, num(T) में तत्वों की संख्या T, और size(T) का आवंटित आकार T. हम ऑपरेशन create_table(n) के अस्तित्व को मानते हैं, जो आकार की एक खाली तालिका बनाता है n, अभी के लिए मुफ़्त माना जाता है, और एलिमेंट्री_इंसर्ट(टी,ई), जो तत्व सम्मिलित करता है E एक तालिका में T जिसके पास पहले से ही जगह आवंटित है, 1 की लागत के साथ।

निम्नलिखित छद्मकोड तालिका प्रविष्टि प्रक्रिया को दर्शाता है:

फ़ंक्शन टेबल_इंसर्ट(टी, ई)
    यदि संख्या(टी) = आकार(टी)
        यू := create_table(2 × आकार(टी))
        टी में प्रत्येक एफ के लिए
            प्राथमिक_सम्मिलित करें (यू, एफ)
        टी := यू
    प्राथमिक_सम्मिलित करें (टी, ई)

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

लेखांकन पद्धति का उपयोग करके विश्लेषण के लिए, हम प्रत्येक तालिका प्रविष्टि के लिए 3 का भुगतान निर्धारित करते हैं। हालांकि इसका कारण अभी स्पष्ट नहीं है, लेकिन विश्लेषण के दौरान यह स्पष्ट हो जाएगा।

मान लें कि प्रारंभ में तालिका आकार (T) = m के साथ खाली है। इसलिए पहले एम सम्मिलन के लिए पुनर्आवंटन की आवश्यकता नहीं होती है और इसकी लागत केवल 1 होती है (प्रारंभिक सम्मिलन के लिए)। इसलिए, जब संख्या(T) = m, पूल में (3 - 1)×m = 2m है।

तत्व m + 1 सम्मिलित करने के लिए तालिका के पुनः आवंटन की आवश्यकता होती है। लाइन 3 पर नई तालिका बनाना (अभी के लिए) मुफ़्त है। लाइन 4 पर लूप को एम की लागत के लिए एम प्राथमिक सम्मिलन की आवश्यकता होती है। अंतिम पंक्ति पर सम्मिलन सहित, इस ऑपरेशन की कुल लागत m + 1 है। इस ऑपरेशन के बाद, पूल में 2m + 3 - (m + 1) = m + 2 है।

इसके बाद, हम तालिका में एक और m-1 तत्व जोड़ते हैं। इस बिंदु पर पूल में m + 2 + 2×(m - 1) = 3m है। एक अतिरिक्त तत्व (अर्थात, तत्व 2m + 1) डालने पर लागत 2m + 1 और भुगतान 3 देखा जा सकता है। इस ऑपरेशन के बाद, पूल में 3m + 3 - (2m + 1) = m + 2 है। नोट यह वही राशि है जो तत्व m + 1 डालने के बाद थी। वास्तव में, हम दिखा सकते हैं कि किसी भी संख्या में पुनः आवंटन के लिए यही स्थिति होगी।

अब यह स्पष्ट किया जा सकता है कि प्रविष्टि के लिए भुगतान 3 क्यों है। 1 तत्व की पहली प्रविष्टि के लिए भुगतान करता है, 1 अगली बार तालिका का विस्तार करने पर तत्व को स्थानांतरित करने के लिए भुगतान करता है, और 1 अगली बार पुराने तत्व को स्थानांतरित करने के लिए भुगतान करता है तालिका का विस्तार किया गया है. सहज रूप से, यह बताता है कि किसी तत्व का योगदान कभी भी समाप्त नहीं होता है, भले ही तालिका को कितनी बार विस्तारित किया जाए: चूंकि तालिका हमेशा दोगुनी होती है, नवीनतम आधा हमेशा सबसे पुराने आधे को स्थानांतरित करने की लागत को कवर करता है।

हमने शुरू में यह मान लिया था कि तालिका बनाना निःशुल्क है। वास्तव में, n आकार की तालिका बनाना O(n) जितना महंगा हो सकता है। मान लीजिए कि n आकार की एक तालिका बनाने की लागत n है। क्या यह नई लागत कोई कठिनाई पेश करती है? ज़रूरी नहीं; यह पता चला है कि हम परिशोधित O(1) सीमा को दिखाने के लिए उसी विधि का उपयोग करते हैं। हमें बस भुगतान बदलना है।

जब एक नई तालिका बनाई जाती है, तो एम प्रविष्टियों वाली एक पुरानी तालिका होती है। नई टेबल का आकार 2 मीटर होगा। जब तक तालिका में वर्तमान प्रविष्टियाँ नई तालिका बनाने के लिए भुगतान करने के लिए पूल में पर्याप्त रूप से जुड़ जाती हैं, तब तक हम ठीक रहेंगे।

हम पहले की उम्मीद नहीं कर सकते ${\frac {m}{2}}$ नई तालिका के लिए भुगतान में सहायता के लिए प्रविष्टियाँ। उन प्रविष्टियों का वर्तमान तालिका के लिए पहले ही भुगतान कर दिया गया है। फिर हमें आखिरी पर भरोसा करना चाहिए ${\frac {m}{2}}$ लागत का भुगतान करने के लिए प्रविष्टियाँ $2m$. इसका मतलब है कि हमें जोड़ना होगा ${\frac {2m}{m/2}}=4$ प्रत्येक प्रविष्टि के लिए भुगतान के लिए, 3 + 4 = 7 के कुल भुगतान के लिए।

संदर्भ

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 17.2: The accounting method, pp. 410–412.