दस बुनियादी व्यावहारिक एल्गोरिदम जिन्हें प्रोग्रामर को अवश्य जानना चाहिए और उनकी व्याख्या

• एल्गोरिथ्म 1: त्वरित क्रमबद्ध एल्गोरिथ्म

  फास्ट सॉर्टिंग एक सॉर्टिंग एल्गोरिथ्म है जो टोनी हॉल द्वारा विकसित किया गया है। औसत स्थिति में, n प्रोजेक्ट को क्रमबद्ध करने के लिए O ((nlogn) बार की आवश्यकता होती है। सबसे खराब स्थिति में, यह O ((n2) बार की आवश्यकता होती है, लेकिन यह स्थिति आम नहीं है। वास्तव में, फास्ट सॉर्टिंग आमतौर पर अन्य O ((nlogn) एल्गोरिदम की तुलना में काफी तेज होती है, क्योंकि इसका आंतरिक चक्र (innerloop) अधिकांश संरचनाओं पर बहुत कुशलता से लागू किया जा सकता है।

  फास्ट सॉर्ट एक सूची को दो उप-सूचियों में विभाजित करने के लिए एक विभाजन और विजय रणनीति का उपयोग करता है।

  एल्गोरिथ्म चरणः

  • 1। एक तत्व चुनें, जिसे pivot () कहा जाता है, और उस तत्व को चुनें जिसे pivot () कहा जाता है।

  • 2। सरणी को फिर से व्यवस्थित करें, सभी तत्व जो कि बेंचमार्क से छोटे हैं, उन्हें बेंचमार्क के सामने रखा गया है, और सभी तत्व जो बेंचमार्क से बड़े हैं, उन्हें बेंचमार्क के पीछे रखा गया है। (समान संख्या दोनों तरफ हो सकती है) । इस विभाजन के बाहर निकलने के बाद, यह आधार सरणी के मध्य में है। यह विभाजन ऑपरेशन कहा जाता है।

  • 3। पुनरावर्ती रूप से ((recursive) एक आधार तत्व से कम और एक आधार तत्व से अधिक की एक श्रृंखला को क्रमबद्ध करता है।

    पुनरावृत्ति की सबसे निचली स्थिति यह है कि संख्याओं का आकार शून्य या एक है, यानी हमेशा के लिए अच्छी तरह से क्रमबद्ध किया गया है। हालांकि यह लगातार पुनरावर्ती है, लेकिन यह एल्गोरिथ्म हमेशा बाहर निकलता है, क्योंकि प्रत्येक पुनरावृत्ति में यह कम से कम एक तत्व को अपने अंतिम स्थान पर रखता है।

• एल्गोरिथ्म 2: ढेर क्रमबद्ध एल्गोरिथ्म

  ढेर सॉर्ट () एक सॉर्टिंग एल्गोरिथ्म है जो ढेर की इस प्रकार की डेटा संरचना का उपयोग करके डिज़ाइन किया गया है। ढेर एक पूर्ण द्विआधारी पेड़ की संरचना है, और साथ ही ढेर की प्रकृति को पूरा करता हैः अर्थात्, एक उप-नोड का कुंजी मान या सूचकांक हमेशा इसके मूल नोड से छोटा (या बड़ा) होता है।

  स्टैक सॉर्टिंग की औसत समय जटिलता O ((nlogn) 。 है।

  एल्गोरिथ्म चरणः

  • 1। एक H ढेर बनाएँ[0..n-1]

  • 2, स्टैकहेड (माहतम मान) और स्टैकएंड का आदान-प्रदान

  • 3, ढेर को 1 से छोटा करें और shift_down () को कॉल करें, जिसका उद्देश्य नए सरणी के शीर्ष पर डेटा को उचित स्थान पर समायोजित करना है

  • 4, चरण 2 को दोहराएं जब तक कि ढेर का आकार 1 न हो

• एल्गोरिथ्म III: समावेशन क्रमबद्ध करना

  विलय क्रमबद्ध (Mergesort, ताइवान अनुवादः मर्ज सॉर्ट) एक प्रभावी क्रमबद्ध एल्गोरिथ्म है जो विलय ऑपरेशन पर आधारित है। यह एल्गोरिथ्म विभाजन और विजय (DivideandConquer) का एक बहुत ही विशिष्ट अनुप्रयोग है।

  एल्गोरिथ्म चरणः

  • 1. रिक्वेस्ट स्पेस को दो पहले से सॉर्ट किए गए अनुक्रमों के योग के रूप में आकार दें, जो विलय के बाद के अनुक्रमों को संग्रहीत करने के लिए उपयोग किया जाता है

  • 2। दो पॉइंटर सेट करें, प्रारंभिक स्थान दो पहले से क्रमबद्ध अनुक्रमों की प्रारंभिक स्थिति है

  • 3. दो सूचक द्वारा निर्देशित तत्वों की तुलना करें, एक छोटा सा तत्व चुनें जो एकीकरण स्थान में रखा गया है, और सूचक को अगले स्थान पर ले जाएं
  • 4. चरण 3 को तब तक दोहराएं जब तक कि एक सूचक अनुक्रम के अंत तक नहीं पहुंच जाता
  • 5. अन्य अनुक्रम के शेष सभी तत्वों को सीधे संयोजन अनुक्रम के अंत में कॉपी करें

• एल्गोरिथ्म चार: द्विधातु खोज एल्गोरिथ्म

  द्विआधारी खोज एक खोज एल्गोरिथ्म है जो क्रमबद्ध सरणी में किसी विशेष तत्व की खोज करता है। खोज प्रक्रिया सरणी के मध्य तत्व से शुरू होती है, यदि मध्य तत्व ठीक है तो खोज प्रक्रिया समाप्त हो जाती है; यदि कोई विशेष तत्व मध्य तत्व से बड़ा या छोटा है, तो खोज सरणी के मध्य तत्व से शुरू होती है और तुलना शुरू होती है। यदि किसी चरण में चरण संख्या शून्य है, तो प्रतिनिधि नहीं मिल सकता है। इस खोज एल्गोरिथ्म ने प्रत्येक तुलना में खोज सीमा को आधा छोटा कर दिया है। आधा खोज हर बार खोज क्षेत्र को आधा कम कर देता है, और जटिलता समय ((Οlogn) है।

• एल्गोरिथ्म पांच: BFPRT (रेखीय खोज एल्गोरिथ्म)

  बीएफपीआरटी एल्गोरिथ्म के समाधान की समस्या बहुत क्लासिक है, जो कि किसी तत्व के अनुक्रम से k सबसे बड़ा (और k सबसे छोटा) तत्व का चयन करता है, चतुर विश्लेषण के माध्यम से, बीएफपीआरटी सबसे खराब स्थिति में भी रैखिक समय जटिलता की गारंटी दे सकता है। इस एल्गोरिथ्म के विचार तेजी से क्रमबद्ध करने के विचार के समान हैं, और निश्चित रूप से, एल्गोरिथ्म के लिए सबसे खराब स्थिति में, यह अभी भी o (n) की समय जटिलता तक पहुंच सकता है, पांच एल्गोरिथ्म लेखकों ने एक उत्कृष्ट प्रसंस्करण किया है।

  एल्गोरिथ्म चरणः

  • 1। n तत्वों को 5 में से एक समूह में, n/5 (ऊपरी सीमा) समूहों में विभाजित करें।

  • 2. प्रत्येक समूह के मध्यस्थों को निकालें, किसी भी क्रमबद्ध विधि का उपयोग करें, जैसे कि सम्मिलित करना।
  • 3. चयन एल्गोरिथ्म को पिछले चरण में सभी मध्यस्थों के मध्यस्थों को खोजने के लिए आवर्ती कॉल करें, इसे x पर सेट करें, और यदि कोई मध्यस्थ संख्या है, तो इसे मध्य में से एक को चुनने के लिए सेट करें।

  • 4। सरणी को विभाजित करने के लिए x का उपयोग करें, जो कि k से कम है जो x के बराबर है और n-k से अधिक है जो कि x से अधिक है।

  • 5। यदि i==k, तो x लौटाएं; यदि i<k, तो x से छोटे तत्वों में से i-k तत्वों को खोजने के लिए पुनरावर्ती; यदि i>k, तो x से बड़े तत्वों में से i-k तत्वों को खोजने के लिए पुनरावर्ती।

    समाप्ति शर्त: जब n = 1 है, तो लौटाया गया तत्व i है।

• एल्गोरिथ्म 6: डीएफएस ((गहरी प्राथमिकता खोज)

  गहराई-प्रथम-खोज (Deepth-First-Search) एक प्रकार का खोज एल्गोरिथ्म है। यह पेड़ की गहराई के साथ पेड़ के सभी नोड्स को पार करता है और पेड़ की शाखाओं को यथासंभव गहराई से खोजता है। जब नोड v के सभी किनारों की खोज की जाती है, तो खोज उस नोड के शुरुआती बिंदु पर वापस आ जाती है जो नोड v को ढूंढता है। यह प्रक्रिया तब तक जारी रहती है जब तक कि सभी नोड्स जो स्रोत नोड से पाए गए हैं, उन तक नहीं पहुंच जाते। यदि अभी भी कोई अनदेखा नोड है, तो स्रोत नोड के रूप में एक को चुनें और ऊपर की प्रक्रिया को दोहराएं, पूरी प्रक्रिया बार-बार की जाती है जब तक कि सभी नोड्स का दौरा नहीं किया जाता है। डीएफएस अंधा खोज के अंतर्गत आता है।

  गहराई-प्राथमिकता खोज (Deep Priority Search) ग्राफिक्स में एक क्लासिक एल्गोरिथ्म है, जो एक गहरी-प्राथमिकता खोज एल्गोरिथ्म का उपयोग करके एक लक्ष्य ग्राफ के लिए एक टोपोलॉजिकल सॉर्टिंग टेबल उत्पन्न कर सकता है। टोपोलॉजिकल सॉर्टिंग टेबल का उपयोग करके कई संबंधित ग्राफिकल समस्याओं को आसानी से हल किया जा सकता है, जैसे कि अधिकतम पथ समस्या आदि। डीएफएस एल्गोरिथ्म को लागू करने के लिए स्टैक डेटा संरचना का उपयोग करना आम है।

  एल्गोरिथ्म के चरणों को गहराई से प्राथमिकता देंः

  • 1। शिखर तक पहुँचें v;

  • 2. ग्राफ को गहराई से प्राथमिकता के साथ यात्रा करें, जो कि v के अनियंत्रित आसन्न बिंदुओं से शुरू होता है; जब तक कि ग्राफ में और v के साथ एक ही पथ के शिखर तक पहुंच नहीं जाता है;
  • 3. यदि इस समय मानचित्र में कोई शिखर अभी तक नहीं पहुंचा है, तो एक अनियंत्रित शिखर से शुरू करें और फिर से गहराई प्राथमिकता यात्रा करें, जब तक कि मानचित्र के सभी शिखरों पर नहीं जाया जाता।

    यह वर्णन अमूर्त हो सकता है, उदाहरण के लिएः

    डीएफएस एक्सेस मानचित्र में किसी एक टॉप v को शुरू करने के बाद, v से शुरू होता है, जो इसके किसी भी पड़ोसी टॉप w1 पर जाता है; फिर w1 से शुरू होता है, जो w1 के साथ पड़ोसी टॉप w2 पर जाता है, लेकिन अभी तक नहीं गया है; और फिर w2 से शुरू होता है, एक समान यात्रा के लिए, ... ऐसा तब तक किया जाता है जब तक कि सभी पड़ोसी टॉप u तक नहीं पहुंच जाते हैं।

    इसके बाद, एक कदम पीछे हटें और उस शीर्ष पर वापस जाएं जिसे आपने पिछली बार देखा था, यह देखने के लिए कि क्या कोई अन्य आसन्न शीर्ष नहीं है जिसे देखा गया है। यदि कोई है, तो उस शिखर पर जाएं, और फिर उस शिखर से आगे बढ़ें, जैसा कि ऊपर उल्लेख किया गया है; यदि नहीं, तो एक कदम पीछे हटें और खोज करें। ऊपर बताई गई प्रक्रिया को तब तक दोहराएं जब तक कि कनेक्टिविटी मानचित्र में सभी शीर्षों पर नहीं जाया जाता।

• एल्गोरिथ्म सात: बीएफएस (BFS)

  Breadth-First-Search, एक ग्राफिक खोज एल्गोरिथ्म है। सरल शब्दों में, BFS रूट नोड से शुरू होता है और पेड़ के साथ पेड़ की चौड़ाई के साथ घूमता है। यदि सभी नोड्स का दौरा किया जाता है, तो एल्गोरिथ्म बंद हो जाता है। BFS भी अंधा खोज है। आम तौर पर BFS एल्गोरिथ्म को लागू करने के लिए पदानुक्रमित डेटा संरचनाओं का उपयोग किया जाता है।

  एल्गोरिथ्म चरणः

  • 1. सबसे पहले, रूट नोड्स को कतार में डालें।
  • 2. कतार से पहला नोड निकालें और जांचें कि क्या यह लक्ष्य है।

    यदि लक्ष्य पाया जाता है, तो खोज को समाप्त करें और परिणाम वापस भेजें।
    यदि नहीं, तो अपने सभी प्रत्यक्ष उप-नोड्स को कतार में जोड़ें जिन्हें अभी तक जांच नहीं किया गया है।

  • 3। यदि कतार खाली है, तो यह दर्शाता है कि पूरे नक्शे की जांच की गई है, अर्थात नक्शे में कोई लक्ष्य नहीं है जिसे आप खोजना चाहते हैं।

  • 4. चरण 2 को दोहराएं।

• एल्गोरिथ्म आठ: डिजकस्ट्रा एल्गोरिथ्म

  डाइकस्ट्रा एल्गोरिथ्म (अंग्रेज़ीः Dijkstra-salgorithm) एक डच कंप्यूटर वैज्ञानिक, एज़्ज़ेल डाइकस्ट्रा द्वारा प्रस्तावित किया गया है। डाइकोसचर एल्गोरिथ्म एक गैर-ऋणात्मक आरेख के एकल-स्रोत लघुतम पथ की समस्या को हल करने के लिए चौड़ाई-प्राथमिकता खोज का उपयोग करता है, एल्गोरिथ्म अंततः एक लघुतम पथ का पेड़ प्राप्त करता है। एल्गोरिथ्म को अक्सर रूटिंग एल्गोरिथ्म में या अन्य आरेख एल्गोरिदम के एक उप-मॉड्यूल के रूप में उपयोग किया जाता है।

  इस एल्गोरिथ्म के इनपुट में एक भारित दिशात्मक आरेख G, और G में एक स्रोत शीर्ष S <unk> होता है। हम V को G में सभी शीर्षों का संग्रह कहते हैं। प्रत्येक आरेख में किनारे, दो शीर्षों द्वारा बनाए गए क्रमबद्ध तत्व जोड़े होते हैं। u, v को u से v तक एक मार्ग से जोड़ा जाता है। हम E को G में सभी किनारों का संग्रह कहते हैं, और किनारों का भार भार भारित फ़ंक्शन w: E→ द्वारा दिया जाता है[0,∞] परिभाषा <unk>

  इस प्रकार, w (u, v) एक गैर-ऋण भार है जो एक शिखर u से शिखर v तक है. पक्षों का भार दो शिखरों के बीच की दूरी के रूप में कल्पना किया जा सकता है. किसी भी दो बिंदुओं के बीच के मार्ग का भार, उस पथ पर सभी पक्षों का भार है. ज्ञात है कि V में शिखर s और t हैं, और Dijkstra एल्गोरिथ्म s से t का न्यूनतम भार पथ पा सकता है। (उदाहरण के लिए, सबसे छोटा पथ) । यह एल्गोरिथ्म एक चार्ट में एक शिखर s से किसी अन्य शिखर तक का सबसे छोटा पथ पा सकता है।

  एल्गोरिथ्म चरणः

  • 1। आरंभिक समय क्रम S = {V0}, T = {अन्य शिखर}, T में शिखर के अनुरूप दूरी मान
    यदि <V0,Vi>,d (V0,Vi) <V0,Vi> पर स्थित है
    यदि <V0,Vi> मौजूद नहीं है, तो d{\displaystyle V0,Vi}

  • 2. T में से एक शिखर W चुनें जिसका न्यूनतम दूरी मान है और S में नहीं है, और S में शामिल करें

  • 3। शेष T में शीर्ष के लिए दूरी मान को संशोधित करेंः यदि आप W को मध्यवर्ती शीर्ष के रूप में जोड़ते हैं, तो V0 से Vi तक की दूरी को छोटा करते हैं, तो इस दूरी को संशोधित करें

    चरण 2 और 3 को तब तक दोहराएं जब तक कि S में सभी शीर्ष शामिल न हों, अर्थात जब तक कि W = Vi न हो

• एल्गोरिथ्म 9: गतिशील योजना एल्गोरिथ्म

  गतिशील प्रोग्रामिंग (Dynamicprogramming) गणित, कंप्यूटर विज्ञान और अर्थशास्त्र में एक विधि है जो जटिल समस्याओं को हल करने के लिए मूल समस्या को अपेक्षाकृत सरल उप-प्रश्नों में तोड़ने के लिए उपयोग की जाती है। गतिशील प्रोग्रामिंग अक्सर उन समस्याओं के लिए लागू होती है जिनमें ओवरलैप उप-प्रश्न और इष्टतम संरचनात्मक विशेषताएं होती हैं, गतिशील प्रोग्रामिंग विधियों में अक्सर सरल समाधानों की तुलना में बहुत कम समय लगता है।

  गतिशील नियोजन के पीछे मूल विचार बहुत सरल है। आम तौर पर, यदि हम किसी दिए गए समस्या को हल करने के लिए इसके विभिन्न भागों को हल करने की आवश्यकता है (जैसे कि एक बच्चे की समस्या) और फिर बच्चे की समस्याओं के समाधान को मूल समस्या का समाधान प्राप्त करने के लिए संयोजित करें। आमतौर पर कई बच्चे की समस्याएं बहुत समान होती हैं, जिसके लिए गतिशील नियोजन विधि केवल प्रत्येक बच्चे की समस्या को एक बार हल करने की कोशिश करती है, जिससे गणना की मात्रा कम हो जाती हैः एक बार जब किसी दिए गए बच्चे की समस्या का समाधान हल हो जाता है, तो इसे स्मृति में संग्रहीत किया जाता है, ताकि अगली बार जब उसी बच्चे की समस्या को हल करने की आवश्यकता हो, तो इसे सीधे सूचीबद्ध किया जा सके। यह विशेष रूप से उपयोगी है जब दोहराने वाले बच्चों की संख्या के बारे में इनपुट के आकार का सूचकांक बढ़ता है।

  गतिशील योजना के बारे में सबसे क्लासिक सवाल बैग के बारे में हैं।

  एल्गोरिथ्म चरणः

  1. इष्टतम संरचनात्मक गुण. यदि समस्या के इष्टतम समाधान में शामिल उप-प्रश्न का समाधान भी इष्टतम है, तो हम कहते हैं कि समस्या में इष्टतम संरचनात्मक गुण है (यानी इष्टतम सिद्धांत को पूरा करता है) । इष्टतम संरचनात्मक गुण गतिशील योजना एल्गोरिदम समस्या को हल करने के लिए महत्वपूर्ण सुराग प्रदान करता है ।

  2। सबप्रश्न ओवरलैप की विशेषता <unk> सबप्रश्न ओवरलैप की विशेषता का अर्थ है कि जब एक समस्या को ऊपर से नीचे की ओर एक पुनरावर्ती एल्गोरिथ्म के साथ हल किया जाता है, तो हर बार उत्पन्न होने वाली सबप्रश्न हमेशा एक नई समस्या नहीं होती है, कुछ सबप्रश्न को कई बार दोहराया जाता है <unk> गतिशील योजना एल्गोरिथ्म इस सबप्रश्न की ओवरलैप की विशेषता का उपयोग करता है, प्रत्येक सबप्रश्न के लिए केवल एक बार गणना करता है, फिर इसकी गणना के परिणामों को एक तालिका में संग्रहीत करता है, और जब पहले से गणना की गई सबप्रश्न को फिर से गणना करने की आवश्यकता होती है, तो केवल तालिका में परिणामों की जांच करें, जिससे उच्च दक्षता प्राप्त हो <unk>

• एल्गोरिथ्म 10: सरल बेयस वर्गीकरण एल्गोरिथ्म

  सरल बेयज़ वर्गीकरण एल्गोरिदम बेयज़ सिद्धांतों पर आधारित एक सरल संभाव्यता वर्गीकरण एल्गोरिदम है। बेयज़ वर्गीकरण की नींव संभाव्यता परिकल्पना पर है, जो कि विभिन्न स्थितियों के अस्तित्व में अनिश्चितता है, केवल इसकी संभावनाओं को जानने के मामले में, कैसे तर्क और निर्णय लेने के कार्य को पूरा किया जाए। संभाव्यता परिकल्पना निश्चितता परिकल्पना के अनुरूप है। जबकि सरल बेयज़ वर्गीकरणकर्ता एक स्वतंत्र परिकल्पना पर आधारित है, अर्थात यह कि प्रत्येक नमूना विशेषता अन्य विशेषताओं से संबंधित नहीं है।

  सरल बेयज़ वर्गीकरण सटीक प्राकृतिक संभाव्यता मॉडल पर निर्भर करता है और पर्यवेक्षित सीखने वाले नमूनों के केंद्र में बहुत अच्छा वर्गीकरण प्रभाव प्राप्त करता है। कई व्यावहारिक अनुप्रयोगों में, सरल बेयज़ मॉडल पैरामीटर का अनुमान अधिकतम निकटता अनुमान विधि का उपयोग करके किया जाता है, दूसरे शब्दों में, सरल बेयज़ मॉडल बेयज़ संभाव्यता या किसी भी बेयज़ मॉडल का उपयोग किए बिना काम करता है।

  इन सरल विचारों और अति-सरलीकृत धारणाओं के बावजूद, सरल बेयज़ वर्गीकरण कई जटिल वास्तविकताओं में काफी अच्छा काम कर सकता है।