डेटा संरचनाएँ और एल्गोरिदम
मुख्य तथ्य
- बिग-ओ संकेत बताता है कि इनपुट बढ़ने पर समय या अतिरिक्त मेमोरी की ज़रूरत किस दर से बढ़ती है;
- ऐरे में इंडेक्स से पहुँच O(1) होती है, जबकि लिंक्ड लिस्ट सीधी पहुँच छोड़कर कड़ियों की मदद से प्रविष्टि और विलोपन को लचीला बनाती है।
- बाइनरी सर्च के लिए डेटा क्रमबद्ध होना चाहिए; मर्ज सॉर्ट स्थिर है और O(n log n) समय लेता है, जबकि गलत पिवट मिलने पर क्विकसॉर्ट O(n^2) तक गिर सकता है।
- हैश टेबल में प्रविष्टि, खोज और विलोपन औसतन O(1) हो सकते हैं, लेकिन टकराव को चेनिंग या ओपन ऐड्रेसिंग से संभालना पड़ता है।
मुख्य बिंदु
- 1
बिग-ओ संकेत बताता है कि इनपुट बढ़ने पर समय या अतिरिक्त मेमोरी की ज़रूरत किस दर से बढ़ती है; वस्तुनिष्ठ परीक्षा में `O(1)`, `O(n)`, `O(n log n)` और `O(n^2)` प्रमुख हैं।
- 2
ऐरे में इंडेक्स से पहुँच `O(1)` होती है, जबकि लिंक्ड लिस्ट सीधी पहुँच छोड़कर कड़ियों की मदद से प्रविष्टि और विलोपन को लचीला बनाती है।
- 3
स्टैक में सबसे बाद आया तत्व पहले निकलता है, यानी LIFO क्रम; क्यू में सबसे पहले आया तत्व पहले निकलता है, यानी FIFO क्रम। सही रिकर्शन में बेस केस होना अनिवार्य है।
- 4
बाइनरी सर्च ट्री यानी BST का इनऑर्डर ट्रैवर्सल कुंजियों को क्रमबद्ध रूप में देता है; एडेल्सन-वेल्स्की और लैंडिस का AVL ट्री बदलाव के बाद संतुलन सुधारकर खोज को तेज रखता है।
- 5
चौड़ाई-प्रथम खोज क्यू का उपयोग करती है और अभारित ग्राफ में एज की संख्या के आधार पर सबसे छोटा पथ देती है, जबकि गहराई-प्रथम खोज स्टैक या रिकर्शन से चलती है।
- 6
बाइनरी सर्च के लिए डेटा क्रमबद्ध होना चाहिए; मर्ज सॉर्ट स्थिर है और `O(n log n)` समय लेता है, जबकि गलत पिवट मिलने पर क्विकसॉर्ट `O(n^2)` तक गिर सकता है।
- 7
हैश टेबल में प्रविष्टि, खोज और विलोपन औसतन `O(1)` हो सकते हैं, लेकिन टकराव को चेनिंग या ओपन ऐड्रेसिंग से संभालना पड़ता है।
आगे पढ़ें
एल्गोरिदम की बुनियाद और जटिलता
डेटा संरचना डेटा को इस तरह व्यवस्थित करती है कि पहुँच, खोज, प्रविष्टि, विलोपन और ट्रैवर्सल जैसे काम आसानी से किए जा सकें। एल्गोरिदम किसी समस्या को हल करने वाले सीमित और क्रमबद्ध चरणों का समूह है। वस्तुनिष्ठ सवालों में प्रोग्राम का कोड याद करने से अधिक ज़रूरी यह पहचानना है कि किस काम में कितना समय या मेमोरी लगेगी।
समय-जटिलता बताती है कि इनपुट बढ़ने पर मुख्य ऑपरेशनों की संख्या किस दर से बढ़ती है। स्थान-जटिलता अतिरिक्त मेमोरी की ज़रूरत बताती है। बिग-ओ संकेत ऊपरी वृद्धि-दर दिखाता है। कम से अधिक वृद्धि का सामान्य क्रम `O(1)`, `O(log n)`, `O(n)`, `O(n log n)` और `O(n^2)` है। स्थिर गुणक और छोटे पद छोड़ दिए जाते हैं, इसलिए `5n + 20` को `O(n)` तथा `n^2 + n` को `O(n^2)` माना जाता है। श्रेष्ठ, औसत और सबसे खराब स्थिति की लागत अलग हो सकती है। तुलना करते समय पहले इनपुट का आकार, फिर बार-बार होने वाला ऑपरेशन और अंत में समय या अतिरिक्त मेमोरी की माँग पहचाननी चाहिए।
पूरा नोट खोलें
यह सार्वजनिक पृष्ठ पहला उपलब्ध खंड दिखाता है। स्टडी पैक पूरा विषय और सभी पुनरावलोकन सामग्री खोलता है।
6 और खंड पूरे नोट में हैं
स्टडी पैक खोलें