फास्ट सॉर्टिंग टोनी हॉल द्वारा विकसित एक सॉर्टिंग एल्गोरिथ्म है। औसत स्थिति में, सॉर्ट करने के लिए n ऑब्जेक्ट्स को ओ ((nlogn) बार तुलना की आवश्यकता होती है। सबसे खराब स्थिति में, ओ ((n2) बार तुलना की आवश्यकता होती है, लेकिन यह बहुत कम होता है। वास्तव में, फास्ट सॉर्टिंग आमतौर पर अन्य ओ ((nlogn) एल्गोरिथ्म की तुलना में काफी तेज़ होती है, क्योंकि इसके आंतरिक लूप को अधिकांश संरचनाओं पर बहुत कुशलता से लागू किया जा सकता है।
फास्ट सॉर्टिंग एक सूची को दो उप-सूचियों में विभाजित करने के लिए विभाजन और विजय की रणनीति का उपयोग करता है।
एल्गोरिथ्म चरणः
1. संख्याओं की पंक्तियों में से एक तत्व को चुनें, जिसे पिवोट कहा जाता है।
2, पुनः क्रमबद्ध संख्याएँ, सभी तत्वों को संदर्भ के पहले और सभी तत्वों को संदर्भ के बाद रखा जाता है (समान संख्याएं दोनों तरफ जा सकती हैं) । इस विभाजन से बाहर निकलने के बाद, यह आधार संख्याओं के बीच में है। यह विभाजन ऑपरेशन कहा जाता है।
3, पुनरावर्ती (recursive) एक सूक्ष्म सरणी का क्रम देता है जिसमें कम से कम बेन्चमार्क तत्व होते हैं और बड़े से अधिक बेन्चमार्क तत्व होते हैं।
पुनरावर्तन के सबसे निचले मामले में, संख्याओं की पंक्तियों का आकार शून्य या एक होता है, यानी यह हमेशा अच्छी तरह से क्रमबद्ध किया जाता है। हालांकि यह लगातार पुनरावर्तन करता रहता है, लेकिन यह एल्गोरिथ्म हमेशा बाहर निकलता है क्योंकि प्रत्येक पुनरावर्तन में, यह कम से कम एक तत्व को अपनी अंतिम स्थिति में रखता है।
ढेर सॉर्ट एक सॉर्टिंग एल्गोरिथ्म है जो ढेर की तरह डेटा संरचना का उपयोग करके डिज़ाइन किया गया है। ढेर एक लगभग पूर्ण द्विआधारी पेड़ संरचना है और साथ ही साथ ढेर के गुणों को पूरा करता हैः यानी एक उप-नोड का कुंजी मान या सूचकांक हमेशा अपने माता-पिता से छोटा या बड़ा होता है।
ढेर क्रम के लिए औसत समय जटिलता ओ ((nlogn) है।
एल्गोरिथ्म चरणः
1, एक ढेर H [0...n-1] बनाने के लिए
2। ढेर के सिर (max) और ढेर के अंत को प्रतिस्थापित करें
3, स्टैक को 1 से छोटा करें और shift_down ((0) को कॉल करें, ताकि नए सरणी के शीर्ष पर डेटा को उसी स्थान पर समायोजित किया जा सके।
4. चरण 2 को दोहराएं, जब तक कि ढेर का आकार 1 न हो जाए.
विलय क्रम ("Mergesort") एक प्रभावी क्रमबद्ध एल्गोरिथ्म है जो विलय के संचालन पर आधारित है। यह एल्गोरिथ्म विभाजन और विजय के एक बहुत ही विशिष्ट अनुप्रयोग है।
एल्गोरिथ्म चरणः
१, एक आवेदन स्थान, जिसका आकार दो पहले से क्रमबद्ध अनुक्रमों के योग के रूप में होता है, जिसे संयुक्त अनुक्रमों को संग्रहीत करने के लिए उपयोग किया जाता है
2, दो पॉइंटर्स सेट करें, दो क्रमबद्ध अनुक्रमों के शुरुआती स्थानों के लिए प्रारंभिक स्थान।
3। दो पॉइंटर्स के बीच तत्वों की तुलना करें, अपेक्षाकृत छोटे तत्वों का चयन करें, उन्हें संयोजन स्थान में रखें और पॉइंटर्स को अगले स्थान पर ले जाएं
4. चरण 3 को दोहराएं जब तक कि कोई बिंदु अनुक्रम के अंत तक न पहुंचे।
5, दूसरे अनुक्रम के शेष सभी तत्वों को सीधे संयुक्त अनुक्रम के अंत में कॉपी करता है
द्वि-बिंदु खोज एल्गोरिथ्म एक प्रकार का खोज एल्गोरिथ्म है जो क्रमबद्ध सरणी में किसी विशेष तत्व का पता लगाता है। खोज प्रक्रिया सरणी के मध्यवर्ती तत्व से शुरू होती है, यदि मध्यवर्ती तत्व सही है, तो खोज प्रक्रिया समाप्त हो जाती है; यदि कोई विशेष तत्व मध्यवर्ती तत्व से बड़ा या छोटा है, तो खोज उस आधे में की जाती है जो मध्यवर्ती तत्व से बड़ा या छोटा है, और शुरुआत के रूप में मध्यवर्ती तत्व से तुलना की जाती है। यदि किसी चरण में सरणी खाली है, तो प्रतिनिधित्व नहीं किया जा सकता है। यह खोज एल्गोरिथ्म प्रत्येक तुलना में खोज को एक बार छोटा कर देता है। प्रत्येक आधे खोज में खोज क्षेत्र को आधे से कम किया जाता है, समय जटिलता
BFPRT एल्गोरिथ्म के समाधान के लिए एक क्लासिक समस्या है कि n तत्वों के एक अनुक्रम से k सबसे बड़ा (k सबसे छोटा) तत्व चुनें, और कुशल विश्लेषण के माध्यम से, BFPRT सबसे खराब स्थिति में भी रैखिक समय जटिलता के लिए गारंटी देता है। इस एल्गोरिथ्म के विचार तेजी से क्रम के विचार के समान हैं, बेशक, पांच लेखकों के एल्गोरिथ्म ने सबसे खराब स्थिति में भी समय जटिलता तक पहुंचने के लिए एक परिष्कृत प्रसंस्करण किया।
एल्गोरिथ्म चरणः
1, n तत्वों को प्रत्येक 5 में से एक समूह में विभाजित करें, n/5 (ऊपर की सीमा) समूहों में।
2. प्रत्येक समूह के मध्यवर्ती को निकालें, किसी भी क्रमबद्ध विधि का उपयोग करें, जैसे कि क्रमबद्ध डालें.
3. पुनरावर्ती कॉल चयन एल्गोरिथ्म पिछले चरण में सभी मध्यवर्ती संख्याओं के मध्यवर्ती संख्याओं का पता लगाता है, जिसे x के रूप में सेट किया गया है, जो कि मध्यवर्ती संख्याओं के मामले में मध्यवर्ती छोटे को चुनने के लिए सेट किया गया है।
4, x का उपयोग करके एक सरणी को विभाजित करने के लिए, x से कम के लिए k, और x से अधिक के लिए n - k सेट करें।
5. यदि i==k, तो x लौटाता है; यदि i
समाप्ति की शर्तः n = 1 पर, लौटाया गया छोटा तत्व i है।
गहराई-पहला-खोज एल्गोरिथ्म, एक प्रकार का खोज एल्गोरिथ्म है, जो पेड़ के नोड्स के साथ-साथ पेड़ की शाखाओं के साथ-साथ पेड़ की गहराई तक चला जाता है। जब नोड v के सभी किनारों को खोजा जाता है, तो खोज उस बिंदु पर वापस जाती है जहां नोड v पाया गया था। यह प्रक्रिया तब तक जारी रहती है जब तक कि सभी नोड्स जो स्रोत नोड से पहुंच सकते हैं, खोले नहीं जाते हैं। यदि कोई पाया गया नोड नहीं है, तो स्रोत नोड के रूप में एक को चुनें और इस प्रक्रिया को दोहराएं, जब तक कि सभी नोड्स तक नहीं पहुंच जाते। डीएफएस अंधा खोज है।
गहन प्राथमिकता खोज ग्राफ में एक क्लासिक एल्गोरिथ्म है, जिसका उपयोग गहन प्राथमिकता खोज एल्गोरिथ्म का उपयोग करके लक्ष्य ग्राफ के अनुरूप टोपोलॉजिकल क्रमबद्ध तालिका उत्पन्न करने के लिए किया जा सकता है। टोपोलॉजिकल क्रमबद्ध तालिका का उपयोग करके कई संबंधित ग्राफिकल समस्याओं को आसानी से हल किया जा सकता है, जैसे कि अधिकतम पथ समस्या आदि। सामान्य रूप से ढेर डेटा संरचना का उपयोग करके डीएफएस एल्गोरिथ्म को लागू करने में सहायता की जाती है।
गहन प्राथमिकता के साथ एल्गोरिथ्म चरणों के माध्यम सेः
1. शिखर v तक पहुँचें;
2। v के अनपेक्षित समीपवर्ती बिंदुओं से क्रमशः ग्राफ को गहराई से प्राथमिकता के साथ क्रॉस करें; जब तक कि ग्राफ में उन शीर्षों तक नहीं पहुंच जाते, जिनकी यात्रा v के साथ होती है;
3. यदि इस समय चार्ट में कोई भी शीर्ष नहीं है, तो एक अप्रचलित शीर्ष से शुरू करें और फिर से गहराई प्राथमिकता पर जाएं, जब तक कि चार्ट के सभी शीर्षों पर नहीं जाया जाता।
उदाहरण के तौर पर, हम आपको बता रहे हैं कि कैसे एक व्यक्ति को अपने परिवार के सदस्यों के साथ रहने के लिए प्रोत्साहित किया जाता है।
DFS किसी एक्सेस ग्राफ में किसी एक चोटी v से शुरू होने के बाद, v से प्रस्थान करता है, इसके किसी भी आसन्न शिखर w1 तक पहुंचता है; फिर w1 से प्रस्थान करता है, w2 तक पहुंचता है, जो w1 के साथ आसन्न है, लेकिन अभी तक नहीं पहुंचा है; फिर w2 से प्रस्थान करता है, एक समान पहुंच करता है,... और इसी तरह, जब तक कि सभी आसन्न शिखर u तक नहीं पहुंच जाते हैं, जहां सभी आसन्न शिखरों का दौरा किया जाता है।
फिर, पिछले बार देखे गए शिखर पर वापस जाएं और देखें कि क्या कोई अन्य आसन्न शिखर है जो अभी तक नहीं देखा गया है। यदि ऐसा है, तो इस शिखर पर जाएं और फिर इस शिखर से आगे बढ़ें और पहले के समान खोज करें; यदि नहीं, तो एक और कदम वापस जाएं और खोज करें। उपरोक्त प्रक्रिया को दोहराएं, जब तक कि कनेक्टिविटी ग्राफ में सभी शिखरों को नहीं देखा जाता।
चौड़ाई-पहली खोज एल्गोरिथ्म, एक ग्राफिक खोज एल्गोरिथ्म है; सरल शब्दों में, बीएफएस रूट नोड्स से शुरू होता है, जो पेड़ की चौड़ाई के साथ पेड़ के नोड्स को पार करता है। यदि सभी नोड्स पर पहुंच जाती है, तो एल्गोरिथ्म बंद हो जाता है। बीएफएस भी अंधा खोज है। सामान्य रूप से कतार डेटा संरचना का उपयोग करके बीएफएस एल्गोरिथ्म को लागू करने में सहायता करता है।
एल्गोरिथ्म चरणः
1. सबसे पहले, रूट नोड्स को कतार में डालें.
2. कतार में से पहला नोड निकालें और जांचें कि क्या यह लक्ष्य है।
यदि लक्ष्य पाया जाता है, तो खोज को समाप्त करें और परिणाम वापस भेजें। अन्यथा, इसके द्वारा जांच किए गए सभी प्रत्यक्ष उप-नोड्स को कतार में जोड़ा जाता है।
3. यदि कतार खाली है, तो यह दर्शाता है कि पूरे आरेख में कोई भी लक्ष्य नहीं है जिसे आप खोजना चाहते हैं।
4. चरण 2 दोहराएं.
डिक्स्ट्रा एल्गोरिथ्म (अंग्रेज़ीः Dijkstra's Salgorithm) डच कंप्यूटर वैज्ञानिक एज़हर डिक्स्ट्रा द्वारा प्रस्तावित किया गया था। डिक्स्ट्रा एल्गोरिथ्म ने एक गैर-नकारात्मक अधिकार वाले आरेख के एकल स्रोत के सबसे छोटे पथ को हल करने के लिए चौड़ाई प्राथमिकता खोज का उपयोग किया, जो अंततः एक सबसे छोटा पथ पेड़ प्राप्त करता है। यह एल्गोरिथ्म अक्सर रूटिंग एल्गोरिथ्म या अन्य आरेख एल्गोरिथ्म के एक उप-मॉड्यूल के रूप में उपयोग किया जाता है।
इस एल्गोरिथ्म के इनपुट में एक भारित आनुपातिक आरेख G, और एक स्रोत शिखर S शामिल है। हम V को G में सभी शिखरों का सेट कहते हैं। प्रत्येक आरेख में किनारे, दो शिखरों द्वारा बनाए गए क्रमबद्ध तत्वों के जोड़े हैं। u, v का अर्थ है कि शिखर u से v तक एक मार्ग है। हम E को G में सभी किनारों का सेट कहते हैं, जबकि किनारे का भार भारित फ़ंक्शन w: E→[0,∞] द्वारा परिभाषित किया गया है।
इस प्रकार w (u,v) शिखर u से शिखर v तक का गैर-नकारात्मक भार है। किनारे के भार को दो शिखरों के बीच की दूरी के रूप में कल्पना की जा सकती है। किसी भी दो बिंदुओं के बीच के पथ का भार उस पथ पर सभी किनारों के भारों का योग है। ज्ञात बिंदुओं s और t के साथ V में, Dijkstra एल्गोरिथ्म s से t तक का न्यूनतम भारित मार्ग ढूंढता है। यह एल्गोरिथ्म एक ग्राफ में एक शिखर s से किसी अन्य शिखर तक का सबसे छोटा मार्ग भी ढूंढ सकता है। गैर-नकारात्मक अधिकार वाले दिशात्मक ग्राफ के लिए, Dijkstra एल्गोरिथ्म वर्तमान में सबसे तेज़ एकल-स्रोत सबसे छोटा मार्ग है।
एल्गोरिथ्म चरणः
1, प्रारंभिक समय S = {V0}, T = {बाकी चोटी}, T में चोटी के लिए उपयुक्त दूरी का मान
यदि
2, T में से एक चोटी चुनें, जिसका न्यूनतम दूरी का मान W है और S में नहीं है, और S को जोड़ें
3, शेष T में शीर्ष के लिए दूरी मान को संशोधित करेंः यदि मध्य शिखर के रूप में W को जोड़ा जाए, तो V0 से Vi तक दूरी मान को छोटा किया जाता है।
चरण 2 और 3 को दोहराएं, जब तक कि S में सभी अंक न हों, यानी W = Vi
गतिशील प्रोग्रामिंग (अंग्रेज़ीः Dynamic programming) गणित, कंप्यूटर विज्ञान और अर्थशास्त्र में उपयोग की जाने वाली एक पद्धति है जो जटिल समस्याओं को हल करने के लिए उपयोग की जाती है। गतिशील प्रोग्रामिंग अक्सर ओवरलैपिंग सबप्रोब्लम और सबसे अच्छा सबस्ट्रक्चर के गुणों वाले समस्याओं के लिए लागू होती है, और गतिशील प्रोग्रामिंग विधि अक्सर सरल समाधानों की तुलना में बहुत कम समय लेती है।
गतिशील नियोजन के पीछे का मूल विचार बहुत सरल है. आम तौर पर, किसी दिए गए समस्या को हल करने के लिए, हमें इसके विभिन्न भागों (बच्चे की समस्या) को हल करने की आवश्यकता होती है, और मूल समस्या को हल करने के लिए पुनः संयोजन के लिए समस्या का समाधान करना पड़ता है. अक्सर कई बच्चे बहुत समान होते हैं, इसलिए गतिशील नियोजन विधि प्रत्येक बच्चे को केवल एक बार हल करने की कोशिश करती है, जिससे गणना की मात्रा कम हो जाती हैः एक बार किसी दिए गए बच्चे का समाधान हो जाने के बाद, इसे स्मृति में संग्रहीत किया जाता है, ताकि अगली बार जब एक ही बच्चे को हल करने की आवश्यकता होती है तो सीधे जांच की जा सके। यह अभ्यास विशेष रूप से उपयोगी है जब दोहराए गए बच्चे की संख्या में वृद्धि होती है।
गतिशील नियोजन के बारे में सबसे क्लासिक सवाल बैग के बारे में है।
एल्गोरिथ्म चरणः
1. सबसे अच्छा संरचनात्मक गुण। यदि समस्या के सबसे अच्छे समाधान में शामिल एक समस्या का समाधान भी सबसे अच्छा है, तो हम इसे सबसे अच्छा संरचनात्मक गुण कहते हैं (यानी सबसे अच्छा सिद्धांत को पूरा करता है) । सबसे अच्छा संरचनात्मक गुण गतिशील नियोजन एल्गोरिदम के लिए महत्वपूर्ण संकेत प्रदान करता है।
2. सब प्रॉब्लम ओवरलैपिंग प्रॉपर्टी. सब प्रॉब्लम ओवरलैपिंग प्रॉपर्टी का मतलब है कि जब एक रिवर्स एल्गोरिथ्म के साथ एक समस्या को ऊपर से नीचे तक हल किया जाता है, तो हर बार उत्पन्न होने वाली सब प्रॉब्लम हमेशा नई नहीं होती है और कुछ सब प्रॉब्लम को कई बार दोहराया जाता है. डायनेमिक प्लानिंग एल्गोरिथ्म इस तरह की सब प्रॉब्लम के ओवरलैपिंग प्रॉपर्टी का उपयोग करता है, प्रत्येक सब प्रॉब्लम पर केवल एक बार गणना करता है, और फिर इसके परिणामों को एक तालिका में संग्रहीत करता है, और जब फिर से पहले से ही गणना की गई सब प्रॉब्लम की गणना की आवश्यकता होती है, तो परिणामों को तालिका में बस एक नज़र से देखना होता है, जिससे उच्च दक्षता मिलती है।
बेयर्स वर्गीकरण एल्गोरिथ्म बेयर्स प्रमेय पर आधारित एक सरल संभावना वर्गीकरण एल्गोरिथ्म है। बेयर्स वर्गीकरण का आधार संभावना तर्क है, अर्थात् विभिन्न स्थितियों की उपस्थिति अनिश्चितता के साथ, केवल संभावनाओं के अस्तित्व को जानने के साथ, तर्क और निर्णय लेने के कार्यों को पूरा करना। संभावना तर्क निश्चितता तर्क के अनुरूप है। जबकि बेयर्स वर्गीकरण स्वतंत्र धारणा पर आधारित है, यानी यह मानकर कि नमूना में प्रत्येक विशेषता अन्य विशेषताओं से संबंधित नहीं है।
सरल बेयर्स वर्गीकरण सटीक प्राकृतिक संभावना मॉडल पर निर्भर करता है, जो पर्यवेक्षित सीखने वाले नमूना सेटों में बहुत अच्छे वर्गीकरण प्रभाव प्राप्त करता है। कई व्यावहारिक अनुप्रयोगों में, सरल बेयर्स मॉडल पैरामीटर अनुमान अधिकतम सादृश्य अनुमान का उपयोग करते हैं, दूसरे शब्दों में सरल बेयर्स मॉडल बेयर्स संभावना या किसी भी बेयर्स मॉडल के बिना काम करते हैं।
इन सरल विचारों और अति-सरलीकृत धारणाओं के बावजूद, सरल बेयर्स वर्गीकरण कई जटिल वास्तविक परिस्थितियों में काफी अच्छा काम करता है।