सर्वश्रेष्ठ, सबसे खराब और औसत मामला
एक एल्गोरिथ्म को मापने के तीन तरीके
प्रत्येक एल्गोरिथ्म की लागत इसके इनपुट पर निर्भर करती है। एक ही आकार के दो इनपुट बिल्कुल अलग रनटाइम उत्पन्न कर सकते हैं। जटिलता विश्लेषण उस भिन्नता पर तीन दृष्टिकोण को औपचारिक बनाता है।
सर्वश्रेष्ठ मामला — Ω (Omega): वह इनपुट जो एल्गोरिथ्म को सबसे तेजी से समाप्त करता है। N वस्तुओं की सूची पर रैखिक खोज के लिए: Ω(1) — लक्ष्य पहली स्थिति में है। एक तुलना, हो गई।
सबसे खराब मामला — O (Big O): वह इनपुट जो एल्गोरिथ्म को सबसे धीमी गति से समाप्त करता है। रैखिक खोज के लिए: O(N) — लक्ष्य सूची के अंतिम में बैठता है, या बिल्कुल दिखाई नहीं देता है। प्रत्येक तत्व को निरीक्षण की आवश्यकता है।
औसत मामला — Θ (Theta): सभी संभावित इनपुट पर अपेक्षित लागत, समान वितरण मानते हुए। N स्थितियों में से किसी में भी समान रूप से लक्ष्य होने की संभावना वाली रैखिक खोज के लिए: Θ(N/2) = Θ(N)। स्थिरांक 1/2 गायब हो जाता है क्योंकि Theta सटीक अनुकूल वृद्धि व्यक्त करता है, सटीक गुणांक नहीं।
सबसे खराब मामला क्यों प्रभावी है
सिस्टम सबसे खराब मामले को संभालना चाहिए। एक डेटाबेस क्वेरी जो औसतन 10 ms लगती है लेकिन कभी-कभी 60 सेकंड लगती है एक उपयोगकर्ता-दृश्यमान विफलता उत्पन्न करती है। इंजीनियर सबसे खराब-स्थिति सीमाओं के लिए डिज़ाइन करते हैं ताकि प्रदर्शन इनपुट की परवाह किए बिना अनुमानित रहे। औसत-मामला विश्लेषण संभाव्य सेटिंग्स में मूल्य रखता है, लेकिन सबसे खराब-मामला विश्लेषण गारंटी देता है।
बाइनरी सर्च मामला विश्लेषण
बाइनरी सर्च केवल सॉर्ट की गई सरणियों पर काम करता है। प्रत्येक चरण में: लक्ष्य की तुलना मध्यबिंदु पर तत्व से करें। यदि लक्ष्य मध्यबिंदु के बराबर है, तो इसे लौटाएं। यदि लक्ष्य छोटा है, तो बाएं आधे पर पुनरावृत्ति करें। यदि बड़ा है, तो दाएं आधे पर पुनरावृत्ति करें।
प्रत्येक तुलना शेष उम्मीदवारों के आधे को समाप्त करती है।
मेमोरी वृद्धि और समय-स्पेस ट्रेडऑफ
ऑपरेशन नहीं, मेमोरी गिनना
समय जटिलता एक एल्गोरिथ्म को निष्पादित करने वाले ऑपरेशन की संख्या को मापती है। स्पेस जटिलता इसके इनपुट से परे आवंटित अतिरिक्त मेमोरी को मापती है। उत्पादन सिस्टम में दोनों महत्वपूर्ण हैं: एक तेजी से एल्गोरिथ्म जो O(N²) मेमोरी आवंटित करता है एक सर्वर को समाप्त करेगा।
O(1) स्पेस: N की परवाह किए बिना निरंतर अतिरिक्त मेमोरी। एक स्थान-में सॉर्ट (जैसे insertion sort) मूल सरणी के अंदर तत्वों को स्वैप करता है। यह एक मुट्ठी अस्थायी चर का उपयोग करता है — O(1) चाहे सरणी कितनी भी बड़ी हो।
O(N) स्पेस: इनपुट आकार के अनुपातिक मेमोरी। N-तत्व सरणी की एक प्रति बनाने के लिए N स्लॉट की आवश्यकता है। स्ट्रिंग्स की सूची से एक हैश सेट बनाना प्रवेश भंडारण करता है।
O(N²) स्पेस: N के अनुपातिक मेमोरी। N कोने के साथ एक ग्राफ के लिए एक N×N आसन्न मैट्रिक्स बनाने के लिए N² सेल की आवश्यकता है। N = 10,000 कोने पर, वह 10^8 प्रविष्टियां है — एक साधारण बूलियन ग्रिड के लिए सैकड़ों मेगाबाइट।
समय-स्पेस ट्रेडऑफ
एल्गोरिथ्म डिजाइन में मौलिक कदमों में से एक: स्पेस के लिए समय व्यापार, या समय के लिए स्पेस।
हैश तेजी से O(1) लुकअप प्राप्त करने के लिए O(N) अतिरिक्त स्पेस का उपयोग करती है। हैश तेजी के बिना, एक सूची पर स्कैन O(N) लुकअप के साथ O(1) अतिरिक्त स्पेस प्राप्त करता है। हैश तेजी गति खरीदने के लिए मेमोरी का भुगतान करती है।
Memoization पहले से गणना किए गए परिणाम संग्रहीत करता है (O(N) या अधिक स्पेस) उन्हें पुनः गणना करने से बचने के लिए। Memoization के बिना पुनरावर्ती Fibonacci O(2^N) समय में चलता है। Memoization के साथ: O(N) समय और O(N) स्पेस। स्पेस निवेश समय को घातीय रूप से कम करता है।
हैश डिक्शनरी बनाम सॉर्ट की गई सूची
N शब्दों के दस्तावेज़ में शब्द घटनाओं को गिनने के लिए दो रणनीतियों की तुलना करें:
रणनीति A: एक डिक्शनरी (हैश मैप)। प्रत्येक शब्द डालें; इसके गणना को बढ़ाएं।
रणनीति B: देखे गए शब्दों की एक सॉर्ट की गई सूची बनाए रखें; सदस्यता जांचने से पहले बाइनरी सर्च का उपयोग करें।
Amortized विश्लेषण: लागत को फैलाना
जब कभी-कभी व्यय औसत प्रदर्शन को बर्बाद नहीं करता है
कुछ ऑपरेशन कभी-कभी महंगे होते हैं लेकिन एक अनुक्रम में सस्ते होते हैं। Amortized विश्लेषण संपूर्ण अनुक्रम पर प्रति ऑपरेशन औसत लागत की गणना करता है — एकल ऑपरेशन की सबसे खराब-मामला लागत नहीं।
डायनेमिक सरणी (Python list, Java ArrayList): क्षमता 1 से शुरू होता है। जब भरा हो, तो क्षमता दोगुनी करता है। दोगुना सभी मौजूदा तत्वों को कॉपी करता है: एक append के लिए O(N) काम। लेकिन दोगुना दुर्लभ है। N कुल append के बाद, कितने कुल प्रतिलिपि ऑपरेशन हुए?
दोगुना आकार 1, 2, 4, 8, ..., N/2 पर होता है। प्रतिलिपि गणना: 1 + 2 + 4 + ... + N/2। यह एक ज्यामितीय श्रंखला है जो सभी N append में कुल N − 1 प्रतियों में जोड़ती है। प्रति append औसत प्रतिलिपि: (N − 1) / N < 1, तो O(1) amortized प्रति append दोहराव प्रति O(N) सबसे खराब-मामला लागत के बावजूद।
Amortized विश्लेषण क्यों महत्वपूर्ण है
एक सिस्टम जो कभी-कभी resize, rebalance, या compact संरचना करने के लिए रुकता है एक अलार्मिंग सबसे खराब-मामला व्यक्तिगत ऑपरेशन होने लगता है। Amortized विश्लेषण प्रकट करता है कि अलर्ट झूठा है: दुर्लभ महंगी घटनाएं कई सस्ते लोगों द्वारा भुगतान की जाती हैं। Amortized लागत को समझना over-engineering से बचाता है: एक दुर्लभ O(N) ऑपरेशन से बचने के लिए जटिलता जोड़ना जो केवल O(1) amortized में योगदान देता है बर्बादी है।
गहराई में जाना: unhamming पाठ्यक्रम वास्तविक-विश्व उत्पादन सॉफ़्टवेयर में दोषों के लिए जटिलता विश्लेषण लागू करता है। लापता अध्याय देखें: एल्गोरिदमिक जटिलता & MOAD-0001: तलछटी दोष।
हैश तेजी Amortized सम्मिलन
एक हैश तेजी खाली शुरू होती है और जब लोड कारक 0.75 से अधिक हो तो क्षमता दोगुनी करती है। 1,000 तत्वों को सम्मिलित करने से क्षमता 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 पर बिल्कुल 10 दोहराव होता है।