प्रत्येक जटिलता वर्ग एक वक्र खींचता है
लागत को इनपुट आकार के विरुद्ध प्लॉट करें
x-अक्ष पर इनपुट आकार N रखें। y-अक्ष पर लागत (ऑपरेशन, समय) रखें। प्रत्येक जटिलता वर्ग एक अलग वक्र बनाता है। आप किसी एल्गोरिदम की वृद्धि दर को इसके प्रदर्शन वक्र के आकार से पहचान सकते हैं।
O(1) — सपाट क्षैतिज रेखा। फ़ंक्शन f(N) = 1। कोई ढाल नहीं। लागत N के बावजूद कभी नहीं बदलती। हैश टेबल लुकअप: चाहे टेबल 10 या 10,000,000 तत्वों को रखता है, एक हैश गणना सही बाल्टी में कूदती है।
O(log N) — कोमल ऊपर की ओर वक्र, ढाल घट रही है। N = 1,000,000 पर: लागत ≈ 20 ऑपरेशन। वक्र छोटे N पर तेजी से बढ़ता है, फिर समतल हो जाता है। N की हर दोहरीकरण लागत में ठीक एक इकाई जोड़ता है।
O(N) — विकर्ण सीधी रेखा। ढाल = 1 (स्पर्शोन्मुख अर्थ में)। लागत N के समान दर से बढ़ता है। यदि N तीन गुना हो, तो लागत तीन गुना हो।
O(N log N) — हल्के ऊपर की ओर वक्रता के साथ तेज विकर्ण। O(N) के ऊपर बैठता है लेकिन O(N²) से नीचे। लॉग फ़ैक्टर रैखिक ढाल में धीरे-धीरे बढ़ने वाला गुणक जोड़ता है।
O(N²) — ऊपर की ओर खुलने वाला परवलय। ढाल N बढ़ने के साथ बढ़ता है। N = 10 पर: लागत = 100। N = 100 पर: लागत = 10,000। N = 1,000 पर: लागत = 1,000,000।
बढ़ता अंतर
अनुपात O(N²) / O(N) = N। परवलय और विकर्ण के बीच का अंतर जैसे-जैसे N बढ़ता है वैसे-वैसे बढ़ता है। N = 10 पर: 10× अंतर। N = 100 पर: 100× अंतर। N = 1,000 पर: 1,000× अंतर। N = 50,000 पर: 50,000× अंतर। अंतर हमेशा N के बराबर होता है।
स्केल अंतर की गणना
एक बड़े निर्भरता ग्राफ में 50,000 पैकेज हैं (N = 50,000)। एक एल्गोरिदम O(N) समय में चलता है। एक दूसरा O(N²) में चलता है। इस N पर, अनुपात O(N²)/O(N) = N = 50,000।
एक रेखा खंड को आधा करना
बाइनरी सर्च को दोहराई गई आधा करने के रूप में
N तत्वों की एक क्रमबद्ध सरणी लंबाई N का एक रेखा खंड बनाती है। बाइनरी सर्च इस खंड को बार-बार आधा करता है:
1. शेष खंड के मध्यबिंदु पर इंगित करें।
2. यदि target < midpoint: दाहिना आधा गायब हो जाता है। बाएं आधे पर पुनरावृत्ति करें।
3. यदि target > midpoint: बाया आधा गायब हो जाता है। दाएं आधे पर पुनरावृत्ति करें।
4. यदि target = midpoint: किया।
k आधा करने के बाद, शेष खंड की लंबाई N / 2^k है। सर्च तब समाप्त होता है जब वह लंबाई 1 के बराबर हो:
N / 2^k = 1 → 2^k = N → k = log₂N
तो N तत्वों पर बाइनरी सर्च को अधिकतम log₂N तुलना की आवश्यकता है।
आधा करना & दोहरीकरण: एक ही वक्र की दो भुजाएं
आधा करना और दोहरीकरण ज्यामितीय व्युत्क्रम हैं। घातांकीय वक्र 2^k और लॉगरिदमिक वक्र log₂N रेखा y = x के पार एक दूसरे के प्रतिबिंब हैं।
कागज की परतों पर विचार करें: एक शीट 0.1 मिमी मोटी शुरू होती है। प्रत्येक परत मोटाई को दोगुना करती है। 42 परतों के बाद: 0.1 मिमी × 2^42 ≈ 439,804 किमी — चंद्रमा के पार (384,400 किमी)। बाइनरी सर्च व्युत्क्रम चलाता है: N तत्वों से शुरू करें, प्रत्येक चरण गणना को आधा करता है, log₂N चरणों में 1 तत्व तक पहुंचते हैं।
ज्यामिति: आधा करना एक स्व-समान ऑपरेशन है। प्रत्येक आधा करना दो आधे बनाता है जो पूरे के समान संरचना में दिखते हैं। पुनरावृत्ति और लॉगरिदम इस आत्म-समानता को साझा करते हैं।
तुलना & दोहरीकरण
एक क्रमबद्ध सरणी में 1,048,576 तत्व हैं। नोट: 1,048,576 = 2^20।
एक ज्यामितीय मानचित्र के रूप में एक हैश फ़ंक्शन
फ़ंक्शन के रूप में हैश फ़ंक्शन
एक हैश टेबल एक हैश फ़ंक्शन का उपयोग करके एक कुंजी को एक बाल्टी में मैप करता है:
bucket = hash(key) mod table_size
यह कड़े गणितीय अर्थ में एक फ़ंक्शन है: यह एक डोमेन (सभी संभावित कुंजियां) को एक रेंज (बाल्टी सूचकांक 0 से table_size − 1) में मैप करता है। ज्यामितीय चित्र: कुंजियां एक स्थान घेरती हैं; बाल्टियां दूसरी घेरती हैं। हैश फ़ंक्शन कुंजियों को बाल्टी सूचकांकों पर प्रक्षेपित करता है।
O(1) लुकअप — प्रत्यक्ष कूद, कोई खोज नहीं। हैश फ़ंक्शन स्थिर समय में बाल्टी सूचकांक की गणना करता है। सीधे उस बाल्टी में कूदें। कोई ट्रैवर्सल नहीं, कोई तुलना लूप नहीं।
लोड फ़ैक्टर। 0.75 के लोड फ़ैक्टर पर, 75% बाल्टियों में कम से कम एक तत्व होता है। ~0.9 से ऊपर, टकराव बढ़ते हैं: दो कुंजियां एक ही बाल्टी में हैश करती हैं, उस बाल्टी के अंदर तत्वों की एक श्रृंखला बनाती हैं। एक लंबी श्रृंखला में लुकअप बदतर मामले में O(N) तक गिर जाता है।
वितरण गुणवत्ता को ज्यामिति के रूप में
एक अच्छी तरह से वितरित हैश फ़ंक्शन कुंजियों को सभी बाल्टियों में समान रूप से फैलाता है। ज्यामितीय रूप से: फ़ंक्शन की रेंज इसके कोडोमेन को समान रूप से कवर करती है। प्रत्येक बाल्टी लगभग N / table_size कुंजियां प्राप्त करता है।
एक खराब हैश फ़ंक्शन कुंजियों को कुछ बाल्टियों में समूहित करता है। ज्यामितीय रूप से: फ़ंक्शन की रेंज कोडोमेन के एक सबसेट में संकुचित हो जाती है — अधिकांश कुंजियां एक ही कुछ बिंदुओं में मैप करती हैं। शेष बाल्टियां खाली बैठती हैं।
MOAD-0001 से कनेक्शन
एक सूची को एक सेट से प्रतिस्थापित करना MOAD-0001 को ठीक करता है क्योंकि एक सेट आंतरिक रूप से एक हैश टेबल का उपयोग करता है। O(N) सूची स्कैन → O(1) हैश टेबल लुकअप। ज्यामितीय रूप से: एक अनुक्रम के साथ रैखिक ट्रैवर्सल एक फ़ंक्शन के माध्यम से एक प्रत्यक्ष प्रक्षेपण में परिवर्तित हो जाता है। अनुक्रम गायब हो जाता है; फ़ंक्शन इसे प्रतिस्थापित करता है।
एक खराब वितरित हैश का विश्लेषण
एक हैश टेबल में 1,000 बाल्टियां और 900 तत्व हैं (लोड फ़ैक्टर 0.9)। एक खराब हैश फ़ंक्शन उन 900 तत्वों में से 500 को एक ही बाल्टी में भेजता है।