किसी एल्गोरिदम की समय जटिलता और स्थान जटिलता की व्याख्या
दो ऐसे प्रोग्रामों की कल्पना कीजिए जो बिल्कुल एक ही काम करते हैं। दोनों को एक-एक हजार रिकॉर्ड दीजिए, आप उनमें फर्क नहीं कर पाएंगे। लेकिन अगर उन्हें एक अरब रिकॉर्ड दे दीजिए, तो एक प्रोग्राम एंटर बटन दबाने से पहले ही अपना काम खत्म कर देगा, जबकि दूसरा अगले मंगलवार तक चलता रहेगा।
एक ही लैपटॉप। एक ही डेटा। उनमें अंतर समय जटिलता का है, जो कि किसी एल्गोरिदम के कार्यभार में वृद्धि की गति को दर्शाने वाला एक नाम मात्र है, जैसे-जैसे आप उसे अधिक इनपुट देते हैं।
हम जानेंगे कि इस शब्द का असल मतलब क्या है, बिग ओ नोटेशन इसे कैसे दर्शाता है, इसे कोड के एक वास्तविक हिस्से से कैसे निकाला जा सकता है, और स्पेस कॉम्प्लेक्सिटी इसमें कहाँ काम आती है। और अंत में, एक ऐसी जगह जहाँ यह सब होमवर्क नहीं रहेगा, बल्कि असल में पैसे खर्च करने लायक हो जाएगा: स्मार्ट कॉन्ट्रैक्ट्स।
किसी एल्गोरिदम की समय जटिलता क्या है?
कुछ समय के लिए सेकंड को भूल जाइए। समय जटिलता चरणों की गणना करती है। तुलना, आवंटन, थोड़ी-बहुत अंकगणितीय गणनाएँ, और आप कुल योग को n के फलन के रूप में लिखते हैं, जहाँ n इनपुट का आकार है।
यह कल्पना से परे सबसे उबाऊ कार्य है:
पायथन def print_all(items): for item in items: print(item)
दस वस्तुएँ? लूप के दस चक्कर। दस हज़ार? दस हज़ार चक्कर।
कार्य इनपुट के ठीक बगल में एक सीधी रेखा में बढ़ता है, इसलिए हम इसे O(n) कहते हैं।
अब, हो सकता है कि हर यात्रा में एक के बजाय तीन छोटे ऑपरेशन लगें। ठीक है, तो यह 3n हो गया। सच कहूँ तो, किसी को परवाह नहीं है, क्योंकि सूची को दोगुना करने से काम भी दोगुना हो जाता है, और यही वृद्धि वक्र हमें चाहिए। सटीक संख्या जानबूझकर छोड़ दी गई है।
यही कारण है कि हर DSA कोर्स और आधे से ज़्यादा कोडिंग इंटरव्यू में टाइम कॉम्प्लेक्सिटी पर ज़ोर दिया जाता है। अगर आप किसी एल्गोरिदम को देखकर उसकी कॉम्प्लेक्सिटी का अंदाज़ा लगा सकते हैं, तो आप यह भी अनुमान लगा सकते हैं कि वह उस इनपुट डेटा पर कैसा व्यवहार करेगा जिसे आपने कभी टेस्ट नहीं किया। और प्रोडक्शन में, ज़्यादातर डेटा यही होता है।
किसी एल्गोरिदम के निष्पादन समय का मापन उसके प्रदर्शन का एक खराब पैमाना क्यों है?
तो टाइमर के साथ ही इसे क्यों न चलाया जाए? बहुत से लोग ऐसा करते हैं, और मैं इसे समझता हूँ। दिक्कत यह है कि निष्पादन समय में ऐसी बहुत सी चीजें शामिल हो जाती हैं जिनका आपके एल्गोरिदम से कोई लेना-देना नहीं है:
- हार्डवेयर। मेरा पांच साल पुराना लैपटॉप और एक बिल्कुल नया क्लाउड बॉक्स एक ही स्क्रिप्ट के लिए आपको बिलकुल अलग-अलग परिणाम देंगे।
- प्रोग्रामिंग भाषा। उसी लूप को C और Python में लिखें और आपको 10 गुना या उससे भी अधिक का अंतर दिखाई दे सकता है।
- सिस्टम पर भार बढ़ जाता है। कोई बैकग्राउंड अपडेटर सक्रिय हो जाता है, गार्बेज कलेक्टर जाग उठता है, कैश खाली हो जाता है। आपका परिणाम बदल जाता है।
- आपको जो भी इनपुट मिला हो। जो सॉर्टिंग विधि लगभग सॉर्ट किए गए डेटा पर तेज़ी से काम करती है, वह शफल्ड डेटा पर धीमी गति से काम कर सकती है।
एक स्टॉपवॉच आपको एक इनपुट के साथ एक बॉक्स पर एक बार चलने की जानकारी देती है। अगर आप उससे 100 गुना अधिक डेटा के बारे में पूछें, तो वह कुछ भी नहीं बता पाएगी।
स्टेप काउंट में कोई बदलाव नहीं होता। एल्गोरिदम और इनपुट एक ही हों, तो चाहे रैक सर्वर पर रस्ट हो या किसी के फोन पर जावास्क्रिप्ट, आपको स्टेप्स की संख्या समान ही मिलेगी। इसीलिए बेंचमार्किंग से पहले टाइम कॉम्प्लेक्सिटी दो समाधानों के बीच एक निष्पक्ष तुलना होती है। हालांकि, बेंचमार्किंग के बाद भी मैं बेंचमार्किंग करने की सलाह दूंगा। बस सवाल अलग होगा।
बिग ओ और अन्य एसिम्प्टोटिक नोटेशन की व्याख्या
पाठ्यपुस्तकों में इसे एसिम्प्टोटिक नोटेशन कहा जाता है, जो सुनने में जितना बुरा लगता है, उतना होता नहीं। इसमें n को बहुत बड़ा मान लिया जाता है और छोटी-छोटी बातों पर ध्यान देना बंद कर दिया जाता है, जिससे स्थिर गुणक और छोटे इनपुट गायब हो जाते हैं और केवल वृद्धि वक्र ही शेष रह जाता है। इनमें से तीन को जानना ज़रूरी है:
| नोटेशन | यह क्या वर्णन करता है | सीधा अर्थ | उदाहरण |
|---|---|---|---|
| बिग ओ, ओ(एफ(एन)) | ऊपरी सीमा | यह एल्गोरिदम f(n) से अधिक तेजी से नहीं बढ़ता है। | लीनियर सर्च O(n) है। |
| बिग-ओमेगा, Ω(f(n)) | निचली सीमा | इस एल्गोरिदम को कम से कम f(n) कार्य की आवश्यकता है। | किसी भी तुलना क्रम का मान Ω(n log n) होता है। |
| बिग-थीटा, Θ(f(n)) | कसकर बंधा हुआ | ऊपरी और निचली सीमाएँ मेल खाती हैं | मर्ज सॉर्ट Θ(n log n) है |
व्यवहार में आपको लगभग 95% बार बिग ओ नोटेशन सुनने को मिलेगा। यह एक ऊपरी सीमा निर्धारित करता है, जिसका अर्थ है कि रनिंग टाइम कोष्ठक के अंदर की दर से अधिक तेज़ी से नहीं बढ़ेगा। मेरी पहली नौकरी में कोड रिव्यू के दौरान एक वरिष्ठ डेवलपर ने नेस्टेड लूप के आगे "O(n²), कृपया ठीक करें" लिखा था, और उनका मतलब था कि सबसे खराब स्थिति में टाइम कॉम्प्लेक्सिटी वर्ग के अनुपात में थी और लिस्ट बहुत लंबी होने वाली थी।
ओमेगा और थीटा ज्यादातर एल्गोरिदम के विश्लेषण पर आधारित विश्वविद्यालय पाठ्यक्रमों में ही इस्तेमाल होते हैं, और मुझे नहीं लगता कि मैंने काम पर सालों से इनमें से किसी को भी टाइप किया है। बिग ओ इसलिए बेहतर है क्योंकि यह उस सवाल का जवाब देता है जो लोग मीटिंग में असल में पूछते हैं, जैसे कि "अगर ट्रैफिक तीन गुना हो जाए तो स्थिति कितनी खराब हो जाएगी?"
एक तकनीकी बात ने मुझे कुछ समय के लिए उलझन में डाल दिया। चूंकि बिग O केवल एक सीमा है, इसलिए O(n) फ़ंक्शन भी सख्ती से O(n²) होता है, ठीक उसी तरह जैसे 5 फुट का व्यक्ति "7 फुट से कम" होता है। सच है, लेकिन बेमानी। हर कोई अपनी क्षमता के अनुसार सबसे सटीक सीमा बताता है और मैं भी वही करूंगा।
उदाहरणों सहित सामान्य समय जटिलता वर्ग
वास्तविक कोड में आपको इतनी सारी क्लासें देखने को नहीं मिलेंगी, शायद सात ही, अगर आप कुछ मुश्किल क्लासों को भी गिनें तो। n = 1,000 पर प्रत्येक की अनुमानित लागत इस प्रकार है:
| कक्षा | नाम | विशिष्ट उदाहरण | n = 1,000 पर संक्रियाएँ |
|---|---|---|---|
| ओ(1) | स्थिर | ऐरे इंडेक्स, हैश टेबल लुकअप | 1 |
| O(लॉग n) | लघुगणकीय | द्विआधारी खोज | ~10 |
| पर) | रेखीय | सूची को स्कैन करना | 1,000 |
| O(n log n) | रेखीय | मर्ज सॉर्ट, क्विकसॉर्ट (औसत) | ~10,000 |
| O(n²) | द्विघात | नेस्टेड लूप, बबल सॉर्ट | 1,000,000 |
| O(2ⁿ) | घातीय | सरल पुनरावर्ती फिबोनाची | ब्रह्मांड में परमाणुओं से भी अधिक |
| पर!) | कारख़ाने का | ज़बरदस्ती यात्रा करने वाला विक्रेता | और भी बड़ा |
O(1): स्थिर समय
चाहे आपके पायथन डिक्शनरी में दस कुंजियाँ हों या दस मिलियन, एक कुंजी द्वारा एक कुंजी निकालने में लगभग समान समय लगता है, और सूची से आइटम[5] पढ़ने में भी यही होता है। यही समतलता निरंतर समय का मूल सिद्धांत है।
O(log n): लघुगणकीय समय
मैं इन्हें "1 से 100 के बीच की संख्या का अनुमान लगाने" वाले एल्गोरिदम के रूप में देखता हूँ, जहाँ हर अनुमान शेष संख्याओं में से आधी को खारिज कर देता है। बाइनरी सर्च सॉर्ट की गई सूची पर ठीक यही करता है:
पायथन def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid if arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
एक अरब क्रमबद्ध वस्तुओं के साथ, इसे लगभग 30 तुलनाओं की आवश्यकता होती है, जबकि एक-एक करके उनकी जांच करने में पूरे एक अरब आइटम लग सकते हैं, और मुझे यह बात आज तक हास्यास्पद लगती है।
O(n) और O(n log n)
एक लीनियर एल्गोरिदम प्रत्येक एलिमेंट को एक निश्चित संख्या में बार-बार देखता है, ठीक वैसे ही जैसे आप किसी स्प्रेडशीट कॉलम में सबसे बड़ी संख्या को देखकर खोजते हैं। O(n log n) एक अच्छा सॉर्टिंग परिणाम देता है। मर्ज सॉर्ट सूची को अलग-अलग आइटमों में विभाजित करता है (विभाजन के log n स्तर) और फिर मर्ज करते समय प्रत्येक स्तर पर एक लीनियर पास करता है, इसलिए इसका रनिंग टाइम स्थिर रहता है चाहे डेटा सॉर्ट किया हुआ हो या अव्यवस्थित।
O(n²) और इससे भी बदतर
क्वाड्रेटिक कोड में लगभग हमेशा एक लूप के अंदर दूसरा लूप होता है, जैसे कि यह डुप्लिकेट चेक जो प्रत्येक जोड़ी की तुलना करता है:
पायथन def has_duplicate(items): for i in range(len(items)): for j in range(i + 1, len(items)): if items[i] == items[j]: return True return False
घातीय और फैक्टोरियल वृद्धि तो इससे भी कहीं ज़्यादा जटिल होती है। पाठ्यपुस्तक में वर्णित पुनरावर्ती फिबोनाची विधि एक ही उपसमस्या को बार-बार हल करती रहती है, इसलिए n में प्रत्येक +1 के साथ काम लगभग दोगुना हो जाता है। n = 20 पर आपको इसका पता भी नहीं चलेगा; लेकिन n = 60 पर आप खाना बना सकते हैं, खा सकते हैं, बर्तन धो सकते हैं, फिर भी काम पूरा नहीं होगा।
समय जटिलता की गणना चरण दर चरण कैसे करें
समय जटिलता की गणना करने के लिए आपको शायद ही कभी औपचारिक प्रमाण की आवश्यकता होती है। मैं इस सूची को अपने दिमाग में दोहराता हूँ और यह मेरे द्वारा देखे गए अधिकांश कोड को कवर करती है:
- n को परिभाषित करें। इनपुट आकार क्या है, यह तय करें: सूची की लंबाई, ग्राफ में नोड्स की संख्या, या किसी संख्या में अंकों की संख्या।
- प्रत्येक पंक्ति में किए गए कार्य की गणना करें। सरल कथनों (असाइनमेंट, तुलना, अंकगणित) की लागत O(1) है।
- क्रमिक ब्लॉक जोड़ें। n पर एक के बाद एक दो लूप चलाने से n + n = 2n प्राप्त होता है।
- नेस्टेड ब्लॉकों को गुणा करें। n पर चलने वाले एक लूप के अंदर n पर चलने वाला दूसरा लूप n × n = n² देता है।
- स्थिरांकों को हटा दें। 2n, n बन जाता है, और 500, 1 बन जाता है।
- केवल प्रमुख पद को ही रखें। n² + n में, n के बढ़ने के साथ-साथ n² भाग शेष भाग से बड़ा हो जाता है।
एक त्वरित हल। आपकी गणना T(n) = 3n² + 5n + 2 आती है। एक मिलियन जोड़ें: 3n² तीन ट्रिलियन है, 5n पाँच मिलियन है। राउंडिंग त्रुटि। इसे O(n²) मान लें, हो गया।
ऐसे लूप जो एक-एक कदम आगे बढ़ने के बजाय बीच-बीच में रुक जाते हैं, वे अधिक चालाक होते हैं:
python def count_halvings(n): steps = 0 while n > 1: n //= 2 steps += 1 return steps
प्रत्येक चरण में n आधा हो जाता है, इसलिए यह while लूप लगभग log₂(n) राउंड के बाद रुक जाता है। यही मूल रूप से इस प्रश्न का उत्तर है कि "समय जटिलता O(log n) कब होती है?" यदि शेष भाग प्रत्येक चरण में एक स्थिरांक से कम होता जाता है, तो आप उस बिंदु पर पहुँच जाते हैं।
रिकर्सन को एक और टूल, यानी रिकरेंस की आवश्यकता होती है। मर्ज सॉर्ट दो आधे आकार के कार्य करता है और फिर उन्हें मर्ज करता है, इसलिए T(n) = 2T(n/2) + n। मास्टर थ्योरम इस प्रकार के रिकरेंस के लिए एक चीट शीट है, और इसके लिए यह O(n log n) मान देता है।
और कॉम्पिटिटिव प्रोग्रामिंग का एक जाना-माना नियम जिस पर मैं अक्सर भरोसा करता हूँ: एक सामान्य मशीन एक सेकंड में लगभग 10⁸ सरल ऑपरेशन कर लेती है। यह एक मोटा-मोटा अनुमान है, लेकिन सबमिट करने से पहले सॉल्यूशन की टाइम कॉम्प्लेक्सिटी की जाँच करने के लिए काफी है। n का मान 10⁵ होने पर, O(n²) लगभग 10¹⁰ ऑपरेशन होते हैं, इसलिए आपका कोड टाइम आउट हो जाएगा। O(n log n) 20 लाख से कम ऑपरेशन होते हैं। यह आसानी से हो जाता है।
सबसे खराब स्थिति, सबसे अच्छी स्थिति और औसत स्थिति का विश्लेषण
एक ही एल्गोरिदम को अलग-अलग इनपुट देने पर काम की मात्रा में बहुत बड़ा बदलाव आ सकता है। लीनियर सर्च इसे बखूबी दर्शाता है:
- सबसे अच्छी स्थिति: जो आप चाहते हैं वह बिल्कुल सामने ही रखा है। एक बार तुलना करने पर आप बाहर हो जाएंगे।
- सबसे खराब स्थिति: यह बिल्कुल अंत में हो, या बिल्कुल भी मौजूद न हो। यह n तुलनाएँ हैं।
- औसत स्थिति: यदि समान संभावनाओं के साथ यह कहीं भी हो सकता है, तो आप औसतन n/2 के आसपास जाँच करेंगे। फिर भी, ध्यान रहे, यह O(n) ही रहेगा।
किसी डेवलपर से किसी चीज़ की "जटिलता" के बारे में पूछें और वे लगभग हमेशा आपको सबसे खराब स्थिति में समय जटिलता बताएंगे, क्योंकि वह संख्या एक वादा है जिसके आधार पर आप योजना बना सकते हैं।
मान लीजिए कि आपका API किसी अनुरोध को सबसे खराब स्थिति में भी O(n) समय में संभाल लेता है। बहुत बढ़िया, अब आपको पता है कि सबसे धीमे अनुरोध का व्यवहार कैसा होता है, और अगर कोई जानबूझकर गलत डेटा भेजता है तो भी आप सुरक्षित हैं। लोग ऐसा ज़रूर करते हैं: अगर कोई हमलावर यह पता लगा लेता है कि किन कुंजियों के कारण आपकी हैश टेबल में गड़बड़ी होती है, तो कुछ समय के लिए आपको केवल वही कुंजियाँ दिखाई देंगी।
औसत स्थिति पर विचार करना तब उपयोगी होता है जब प्रतिकूल परिस्थितियाँ शायद ही कभी उत्पन्न होती हैं। क्विकसॉर्ट इसका सबसे अच्छा उदाहरण है, जिसका औसत समय O(n log n) होता है, लेकिन यदि आप पहले से सॉर्ट किए गए डेटा पर पिवट का चयन सरलता से करते हैं तो यह O(n²) तक गिर जाता है। मानक लाइब्रेरी यादृच्छिक पिवट का उपयोग करके या पुनरावृति के अत्यधिक जटिल हो जाने पर किसी अन्य सॉर्टिंग एल्गोरिदम पर स्विच करके इस समस्या का समाधान करती हैं।
स्थानिक जटिलता और सहायक स्थान क्या हैं?
किसी एल्गोरिदम के लिए आवश्यक दूसरा खर्च मेमोरी होता है। स्पेस कॉम्प्लेक्सिटी यह दर्शाती है कि इनपुट का आकार बढ़ने पर आपको कितनी स्पेस की आवश्यकता होती है, और इसे समय की तरह ही बिग ओ नोटेशन में लिखा जाता है।
उस मेमोरी का एक हिस्सा इनपुट ही होता है, जिसके लिए आपको भुगतान करना ही पड़ता है, चाहे आप उसका उपयोग किसी भी तरह से करें। जिस हिस्से पर आपका वास्तविक नियंत्रण होता है, उसे सहायक स्थान कहा जाता है, जिसका अर्थ है वह अतिरिक्त चीज़ें जो आपका कोड काम करते समय आवंटित करता है, जैसे कि अस्थायी चर और नए एरे, साथ ही कॉल स्टैक जिसे कोई तब तक याद नहीं रखता जब तक कि वह समस्या न खड़ी कर दे।
कुछ त्वरित उदाहरण:
- दो चरों को स्वैप करने के लिए कुछ स्लॉट की आवश्यकता होती है, चाहे कुछ भी हो, इसलिए यह O(1) सहायक स्थान है।
- n आइटम वाली सूची को एक नई सूची में कॉपी करने में आपको O(n) अतिरिक्त मेमोरी खर्च करनी पड़ती है।
- n स्तरों तक रिकर्सन करने से स्टैक पर n फ्रेम रह जाते हैं, जो कि O(n) स्पेस है, भले ही आपने कभी कोई ऐरे नहीं बनाया हो।
मैंने एक जूनियर डेवलपर को उस आखिरी समस्या में पूरी दोपहर बर्बाद करते देखा। उनका रिकर्सिव फ़ंक्शन देखने में तो बिल्कुल भी मेमोरी का इस्तेमाल नहीं करता था, लेकिन हर अधूरा कॉल स्टैक पर अटका रहता था और नीचे वाले कॉल्स के रिटर्न का इंतज़ार करता था, और ज़्यादा इनपुट आने पर पूरा सिस्टम स्टैक ओवरफ़्लो के कारण क्रैश हो गया।
कई ऑप्टिमाइज़ेशन में मेमोरी को समय से बदला जाता है या इसका उल्टा किया जाता है। मेमोइज़ेशन पहले से गणना किए गए परिणामों को कैश करता है, जिससे सामान्य फिबोनाची का समय O(2ⁿ) से घटकर O(n) हो जाता है, लेकिन इसके बदले में O(n) मेमोरी खर्च होती है। हैश टेबल बकेट पर जगह खर्च करके O(1) औसत लुकअप प्रदान करते हैं। 64 जीबी रैम वाले सर्वर पर यह बदलाव आमतौर पर बहुत आसान होता है, लेकिन माइक्रोकंट्रोलर या स्मार्ट कॉन्ट्रैक्ट के अंदर आपको इस पर दो बार सोचना पड़ेगा।
सामान्य डेटा संरचनाओं की समय और स्थान जटिलता
सही डेटा संरचना का चयन करना आमतौर पर आपके लूप के अंदर की हर छोटी-मोटी चीज़ को समायोजित करने से बेहतर होता है। सबसे अधिक उपयोग की जाने वाली संरचनाओं के लिए औसत लागत इस प्रकार है:
| डेटा संरचना | पहुँच | खोज | डालना | मिटाना | अंतरिक्ष |
|---|---|---|---|---|---|
| सरणी | ओ(1) | पर) | पर) | पर) | पर) |
| लिंक्ड लिस्ट | पर) | पर) | ओ(1) | ओ(1) | पर) |
| हैश तालिका | लागू नहीं | ओ(1) | ओ(1) | ओ(1) | पर) |
| संतुलित बाइनरी सर्च ट्री | O(लॉग n) | O(लॉग n) | O(लॉग n) | O(लॉग n) | पर) |
| बाइनरी हीप | O(1) न्यूनतम/अधिकतम के लिए | पर) | O(लॉग n) | O(लॉग n) | पर) |
दो अतिरिक्त टिप्पणियाँ। लिंक्ड लिस्ट में इंसर्ट और डिलीट केवल O(1) होते हैं यदि नोड पहले से मौजूद हो। और हैश टेबल में कई कुंजियों के टकराने पर यह O(n) तक गिर सकता है।
सॉर्टिंग एल्गोरिदम में भी उतनी ही विविधता पाई जाती है:
| सॉर्टिंग एल्गोरिदम | श्रेष्ठ | औसत | बहुत बुरा | सहायक स्थान |
|---|---|---|---|---|
| बुलबुले की तरह | पर) | O(n²) | O(n²) | ओ(1) |
| मर्ज सॉर्ट | O(n log n) | O(n log n) | O(n log n) | पर) |
| क्विकसॉर्ट | O(n log n) | O(n log n) | O(n²) | O(लॉग n) |
| ढेर बनाएं और छांटें | O(n log n) | O(n log n) | O(n log n) | ओ(1) |
मर्ज सॉर्ट पूर्वानुमान योग्य है लेकिन अतिरिक्त मेमोरी की आवश्यकता होती है। हीप सॉर्ट उसी स्थान पर सॉर्ट करता है और सबसे खराब स्थिति को बरकरार रखता है। क्विकसॉर्ट, अपनी कमज़ोर सीमा के बावजूद, व्यवहार में बेहतर साबित होता है।
ब्लॉकचेन और स्मार्ट कॉन्ट्रैक्ट्स में समय जटिलता
अब असली मज़ा शुरू होता है। आपके अपने सर्वर पर, एक कमज़ोर एल्गोरिदम CPU को बर्बाद करता है और शायद किसी उपयोगकर्ता को परेशान भी करता है। एथेरियम या किसी भी EVM चेन पर, यह पैसे की बर्बादी है। स्मार्ट कॉन्ट्रैक्ट द्वारा निष्पादित प्रत्येक ऑपकोड के लिए गैस की आवश्यकता होती है, जिसका भुगतान चेन की मूल मुद्रा में किया जाता है, इसलिए आपके ऑपरेशन की संख्या किसी के बिल में जुड़ जाती है। दूसरे शब्दों में, खराब टाइम कॉम्प्लेक्सिटी की कीमत चुकानी पड़ती है।
मान लीजिए आपके पास एक ऐसा अनुबंध है जो प्रत्येक टोकन धारक को पुरस्कार देने के लिए बार-बार चलता है। समय अवधि O(n) है, और प्रत्येक नए धारक के साथ गैस लागत बढ़ती जाती है। लॉन्च के दिन किसी को इसका पता नहीं चलता।
फिर धारकों की सूची बढ़ती रहती है। एक दिन भुगतान के लिए ब्लॉक गैस सीमा से अधिक गैस की आवश्यकता होती है, जो एक ब्लॉक में समा सकने वाली गैस की अधिकतम सीमा है। इसके बाद लेन-देन पूरा नहीं हो पाता। यह "धीमा" नहीं है। यह बस कभी सफल नहीं होता, और उस प्रक्रिया के पीछे जो भी धनराशि जमा होती है, वह अटक जाती है। लेखा परीक्षक इस तरह के असीमित लूप को सेवा से इनकार (डेनायल-ऑफ-सर्विस) के तहत दर्ज करते हैं, और यह उचित भी है।
इसका समाधान केवल जटिलता के बारे में सोचने का सरल तरीका है:
- काम को कई लेन-देनों में निश्चित आकार के बैचों में विभाजित करें।
- इसे इस तरह पलट दें कि प्रत्येक उपयोगकर्ता अपना स्वयं का इनाम प्राप्त कर सके। प्रत्येक कॉल O(1) है।
- लूप को मर्कल प्रूफ से बदलें।
मुझे मर्कल प्रूफ बहुत पसंद हैं, क्योंकि ये इस बात का बेहतरीन उदाहरण हैं कि ऑन-चेन में log n इतना महत्वपूर्ण क्यों है। मर्कल ट्री डेटा के एक बड़े ढेर को एक रूट हैश में बदल देता है।
किसी सेट में एक एंट्री के शामिल होने को साबित करने के लिए, आपको लगभग log₂(n) हैश की आवश्यकता होती है। दस लाख एंट्री के लिए यह संख्या लगभग 20 होती है, दस लाख नहीं। एयरड्रॉप इसी तकनीक पर आधारित होते हैं, और लाइट बिटकॉइन वॉलेट पूरे ब्लॉक को डाउनलोड किए बिना लेनदेन की पुष्टि करने के लिए इसी तरकीब का उपयोग करते हैं।
ऑफ-चेन में भी यही बात लागू होती है। एक ऐसे पेमेंट बैकएंड की कल्पना कीजिए जो हर आने वाले ब्लॉकचेन ट्रांजैक्शन को हर खुले हुए ट्रांजैक्शन को स्कैन करके इनवॉइस से मिलाता है। प्रति पेमेंट O(n) समय लगता है, और दुकान के बढ़ने के साथ यह धीमा होता जाता है। इनवॉइस को एड्रेस या आईडी द्वारा कुंजीबद्ध हैश मैप में रखें और हर मिलान O(1) समय में हो जाएगा। और अगर आप खुद यह सब बनाना और संभालना नहीं चाहते, तो प्लिसियो जैसे क्रिप्टो पेमेंट गेटवे आपके लिए यह काम कर देते हैं।
