सर्वश्रेष्ठ, सर्वाधिक और औसत मामला
तीन तरीके से एक एल्गोरिदम को मापें
हर एल्गोरिदम की लागत इसके इनपुट पर निर्भर करती है। दो इनपुट के समान आकार के होने पर वे विस्तृत रूप से भिन्न रनटाइम पैदा कर सकते हैं। जटिलता विश्लेषण उस भिन्नता के तीन दृष्टिकोणों को संरक्षित करता है।
सर्वश्रेष्ठ मामला - Ω (ओमेगा): एल्गोरिदम को सबसे तेज़ काम करने वाला इनपुट। लाइनर खोज के लिए: Ω(1) - लक्ष्य पहले स्थान पर स्थित होता है। एक परीक्षण, कर दिया।
सर्वाधिक मामला - O (बिग ओ): एल्गोरिदम को सबसे धीरे काम करने वाला इनपुट। लाइनर खोज के लिए: O(N) - लक्ष्य सूची के अंतिम भाग में स्थित होता है, या इसके अभाव में होता है। हर तत्व की जाँच की आवश्यकता होती है।
औसत मामला - Θ (थीटा): सभी संभव इनपुट के लिए अपेक्षित लागत, समान वितरण के साथ। लाइनर खोज के लिए लक्ष्य को किसी भी संभव स्थान पर समान रूप से संभव होता है: Θ(N/2) = Θ(N)। क्रमांक 1/2 गिरता है क्योंकि थीटा निर्देशिका निकट असिम्प्टोटिक वृद्धि, नहीं सही संकेतों को व्यक्त करता है।
यह क्यों सबसे खराब मामला निर्देशिका से प्रभावित होता है।
सिस्टम को सबसे खराब मामले का ध्यान रखना होगा। एक डेटाबेस क्वेरी जो औसतन 10 मिलीसेकंड लेती है, लेकिन कभी-कभी 60 सेकंड लेती है, उपयोगकर्ता दिखने वाली विफलता पैदा करती है। इंजीनियर सबसे खराब मामले के सीमा के लिए डिज़ाइन करते हैं ताकि प्रदर्शन स्थिर रहे चाहे इनपुट क्यों न हो। औसत मामले का विश्लेषण संभावित सेटिंग्स में मूल्य रखता है, लेकिन सबसे खराब मामले का विश्लेषण देता है वादे।
बाइनरी खोज मामला विश्लेषण
बाइनरी खोज केवल सॉर्टेड मैट्रिक्स पर काम करती है। प्रत्येक चरण में: लक्ष्य को मध्य बिंदु के तत्व के साथ तुलना करें। यदि लक्ष्य मध्य बिंदु को बराबर होता है, तो इसे वापस करें। यदि लक्ष्य छोटा है, तो बाएँ आधे पर पुनरावृति करें। यदि बड़ा है, तो दाएँ आधे पर पुनरावृति करें।
प्रत्येक तुलना आधे शेष उम्मीदवारों को निकालती है।
स्मृति वृद्धि और समय-स्थान परिमाण विनिमय
स्मृति की गिनती करें, नहीं काम करें
समय जटिलता एक एल्गोरिदम के कार्य करते हुए किए गए संचालन की संख्या को मापती है। स्थानीयता जटिलता इसके द्वारा आवंटित अतिरिक्त स्मृति को मापती है जो इसके प्रवेश से अधिक है। दोनों निर्माण प्रणालियों में महत्वपूर्ण हैं: एक तेज़ एल्गोरिदम जो ओ (एन ²) स्मृति आवंटित करता है, एक सर्वर को समाप्त कर देगा।
ओ (1) स्थान: एन के बावजूद कॉन्स्टेंट अतिरिक्त स्मृति। एक इन-प्लेस सॉर्ट (जैसे इंसर्शन सॉर्ट) स्वैप करता है कि मूल्य आरे में। यह एक सिरी के लिए ओ (1) मात्रा में अस्थायी चर - चाहे कितनी बड़ी दूरी हो।
ओ (एन) स्थान: स्मृति का प्रवेश आकार के अनुपात। एन- तत्वों वाली एक लिस्ट का एक कॉपी करने के लिए एन स्लॉट की आवश्यकता है। एन स्ट्रिंग्स की एक सूची से एक हैश सेट बनाने के लिए एन प्रवेश को संग्रहीत करता है।
ओ (एन ²) स्थान: एन × एन ग्राफ के लिए एक ग्राफ के लिए एक ग्राफ के लिए एन वर्णों के साथ एक साधारण स्विचिंग ग्रिड के लिए आवश्यक है। एन = 10,000 वर्णों के लिए, यह 10^8 प्रविष्टियाँ हैं - एक सरल बूलियन ग्रिड के लिए सैकड़ों मेगाबाइट।
समय-स्थान परिमाण विनिमय
एल्गोरिदम डिज़ाइन के एक मौलिक कदम: स्थान के लिए समय का विनिमय करें, या समय के लिए स्थान।
हैश टेबल ओ (एन) अतिरिक्त स्थान का उपयोग करके ओ (1) लुकअप प्राप्त करते हैं। हैश टेबल के बिना, एक स्कैन एक सूची में ओ (एन) लुकअप के लिए ओ (1) अतिरिक्त स्थान का उपयोग करता है। हैश टेबल ने तेज़ी से स्पीड का भुगतान किया।
मेमोइज़ेशन पिछले रूपांतरित परिणामों (ओ (एन) या अधिक स्थान) को संग्रहीत करता है ताकि उन्हें पुनर्जनन न करें। गणितीय फिबोनाची के बिना मेमोइज़ेशन ओ (2 ^ एन) समय। मेमोइज़ेशन के साथ: ओ (एन) समय और ओ (एन) स्थान। स्थान का निवेश समय को आठांकीय रूप से कम करता है।
हैश डिक्शनरी vs सॉर्टेड लिस्ट
दो शब्दों की वारसात की गिनती करने के लिए दो रणनीतियों का साथ करें: N शब्दों वाले दस्तावेज़ में:
रणनीति ए: एक शब्दकोश (हैश मैप)। प्रत्येक शब्द को डालें; इसकी गिनती बढ़ाएं।
रणनीति बी: देखे हुए शब्दों की सूची बनाए रखें; दोहरे खोज के लिए बाइनरी सर्च इस्तेमाल करें।
अमोर्टाइज्ड एनालिसिस: लागत का वितरण
जब असामान्य खर्च औसत प्रदर्शन को नुकसान नहीं पहुंचाता है
कुछ संचालन कभी-कभार महंगे होते हैं, लेकिन औसत के साथ सस्ते होते हैं एक क्रम में। अमोर्टाइज्ड एनालिसिस किसी भी एकल संचालन के अधिकतम लागत के बजाय पूरे क्रम के लिए औसत लागत कोण पर संचालन करता है।
डाइनेमिक आरे (पायथन सूची, जावा एलिमेंटलिस्ट): 1 की क्षमता के साथ शुरू होता है। जब पूरा होता है, तब क्षमता डबल होती है। डबलिंग में मौजूदा सभी तत्वों की प्रतिलिपि बनाई जाती है: O(N) काम एक ऐपेंड के लिए। लेकिन डबलिंग्स दुर्लभ हैं। N कुल इंसर्ट्स के बाद, कॉपी संचालन की कुल संख्या क्या होगी?
डबलिंग होती है 1, 2, 4, 8, ..., N/2 की क्षमता पर। कॉपी की संख्या: 1 + 2 + 4 + ... + N/2। यह एक भिन्न श्रृंखला का योग होता है, जो N-1 कुल कॉपी को N इंसर्ट्स पर फैला देता है। औसत कॉपी प्रति ऐपेंड: (N-1) / N < 1, इसलिए O(1) अमोर्टाइज्ड प्रति ऐपेंड हालांकि O(N) वorst-case cost per doubling।
अमोर्टाइज्ड एनालिसिस का महत्व
एक प्रणाली जो कभी-कभी रिज़ाइज़, रीबैलेंस या एक संरचना को संपीड़ित करने के लिए पauses करती है, उसे दिखने वाले O(N) वाले व्यक्तिगत संचालन के लिए चिंता करने की आवश्यकता हो सकती है। अमोर्टाइज्ड एनालिसिस का उपयोग करता है कि चिंता मिथ्या है: दुर्लभ महंगे घटनाक्रमों को सस्ते कई घटनाक्रमों द्वारा भुगतान किया जाता है। अमोर्टाइज्ड लागत के समझने से ओवर-इन्जीनियरिंग की रोकथाम होती है: दुर्लभ O(N) संचालन को बचाने के लिए जो केवल O(1) अमोर्टाइज्ड में योगदान देते हैं, उन्हें जटिलता जोड़ने का काम बर्बाद है।
गहन अध्ययन: अनहैमिंग कोर्स रियल-वर्ल्ड प्रोडक्शन सॉफ्टवेयर में कम्प्लेक्सिटी एनालिसिस लागू करता है। देखें [The Missing Chapter: Algorithmic Complexity](/en/un/unhamming_algorithmic_complexity) & [MOAD-0001: The Sedimentary Defect](/en/un/unhamming_moad_sedimentary).
हैश टेबल में अमोर्टाइज्ड इनसर्ट
एक हैश टेबल शुरू में खाली होता है और जब लोड फैक्टर 0.75 से अधिक होता है, तब इसकी क्षमता डबल की जाती है। 1,000 तत्वों को इनसर्ट करने पर exactly 10 डबलिंग होती हैं क्षमता 1, 2, 4, 8, 16, 32, 64, 128, 256, 512।