विभाजन और जीत कलनविधि (डिवाइड एंड कॉन्कर): Difference between revisions

Latest revision as of 10:33, 24 February 2023

कंप्यूटर विज्ञान में, विभाजन और जीत एक कलन विधि डिजाइन प्रतिमान है। विभाजन और जीत कलनविधि एक समस्या को पुनरावर्ततः समान या संबंधित प्रकार की दो या दो से अधिक उप-समस्याओं में तब तक खंडित करता है, जब तक कि ये सीधे हल करने के लिए पर्याप्त सरल न हो जाएं। उप-समस्याओं के समाधान को तब मूल समस्या का समाधान करने के लिए संयोजित किया जाता है।

विभाजन और जीत तकनीक कई समस्याओं के लिए कुशल कलनविधि का आधार है, जैसे पृथक्करण कलन विधि (उदाहरण के लिए, त्वरित सॉर्ट, मर्ज़ सॉर्ट), बृहत्संख्या को गुणा करना (जैसे, करात्सुबा कलनविधि ), बिंदुओं की निकटतम जोड़ी खोजना, वाक्यात्मक विश्लेषण (उदाहरण के लिए, टॉप-डाउन पार्सर्स अर्थात शीर्ष पाद पद विन्यासक) और असतत फूरियर रूपांतरण (एफ एफ टी) की गणना करना।^[1]

कुशल विभाजन और जीत कलनविधि अभिकल्पना करना कठिन हो सकता है। जैसा कि गणितीय आगमन में होता है, प्रायः समस्या को पुनरावर्ती समाधान करके उत्तरदायी बनाने के लिए सामान्यीकरण करना आवश्यक होता है। विभाजन और जीत कलनविधि की शुद्धता सामान्यतः गणितीय प्रेरण द्वारा सिद्ध होती है, और इसकी अभिकलनात्मक लागत प्रायः पुनरावृत्ति संबंधों को हल करके निर्धारित की जाती है।

फूट डालो और राज करो

बढ़ते क्रम में सूची (38, 27, 43, 3, 9, 82, 10) को क्रमबद्ध करने के लिए विभाजन और जीत दृष्टिकोण। ऊपरी आधा: सब्लिस्ट्स में विभाजन; मध्य: एक-तत्व सूची तुच्छ रूप से क्रमबद्ध है; निचला आधा: सॉर्ट किए गए सबलिस्ट्स की रचना।

विभाजन और जीत प्रतिमान का उपयोग प्रायः किसी समस्या का इष्टतम समाधान खोजने के लिए किया जाता था। इसका मूल विचार दी गई समस्या को दो या अधिक समान, लेकिन सरल, उप-समस्याओं में वियोजित करना है, उन्हें बारी-बारी से समाधान करना और दी गई समस्या को समाधान करने के लिए उनके समाधानों की रचना करना है। पर्याप्त सरलता की समस्याएं सीधे हो जाती हैं।

उदाहरण के लिए, n प्राकृतिक संख्याओं की दी गई सूची को क्रमबद्ध करने के लिए, इसे लगभग n /2 संख्याओं मे प्रत्येक की दो सूचियों में विभाजित करें, उनमें से प्रत्येक को बारी-बारी से क्रमबद्ध करें, और दी गई सूची के क्रमबद्ध संस्करण को प्राप्त करने के लिए दोनों परिणामों को उचित रूप से अंतरापत्र करें ( चित्र देखें)। इस दृष्टिकोण को मर्ज सॉर्ट कलनविधि के रूप में जाना जाता है।

"विभाजन और जीत" नाम कभी-कभी कलनविधि पर लागू होता है जो प्रत्येक समस्या को केवल एक उप-समस्या तक घटाता है, जैसे कि बाइनरी सर्च कलनविधि जो एक क्रमबद्ध सूची में रिकॉर्ड खोजने के लिए (या संख्यात्मक अभिकलन में इसका अनुरूप , मूलनिर्धारण के लिए द्विभाजन कलनविधि ) किया जाता है।^[2] सामान्य विभाजन और जीत कलनविधि की तुलना में इन कलनविधि को अधिक कुशलता से लागू किया जा सकता है; विशेष रूप से, यदि वे टेल रिकर्सन का उपयोग करते हैं, तो उन्हें साधारण सरल लूप (कंप्यूटिंग) में परिवर्तित किया जा सकता है। यद्यपि, इस व्यापक परिभाषा के अंतर्गत, प्रत्येक कलनविधि जो रिकर्सन या लूप का उपयोग करता है, उसे "विभाजन और जीत कलनविधि" के रूप में माना जा सकता है। इसलिए, कुछ लेखकों का मानना है कि "विभाजन और जीत" नाम का उपयोग केवल तभी किया जाना चाहिए जब प्रत्येक समस्या दो या दो से अधिक उप-समस्याएं उत्पन्न कर सकती है।^[3] एकल-उप-समस्या वर्ग के स्थान पर ह्रास और जीत नाम प्रस्तावित किया गया है।^[4]

विभाजन और जीत का एक महत्वपूर्ण अनुप्रयोग अनुकूलीकरण में है,^{[example needed]} जहां यदि प्रत्येक चरण पर एक स्थिर कारक द्वारा खोज स्थान को कम ("छंटनी") किया जाता है, तो समग्र कलनविधि में प्रूनिंग चरण के समान विषम जटिलता होती है, साथ में प्रूनिंग कारक स्थिरांक पर निर्भर करता है (ज्यामितीय श्रृंखला को जोड़कर); इसे प्रून एंड सर्च के रूप में जाना जाता है।

प्रारंभिक ऐतिहासिक उदाहरण

इन कलनविधि के प्रारंभिक उदाहरण प्राथमिक रूप से ह्रास और जीत हैं - मूल समस्या क्रमिक रूप से एकल उप-समस्याओं में खंडित किया जाता है, और वास्तव में इसे पुनरावृत्त रूप से समाधान किया जा सकता है।

बाइनरी खोज, एक कमी-और-जीत कलन विधि जहां उप-समस्याएं लगभग आधे मूल आकार की होती हैं, का एक लंबा इतिहास रहा है। जबकि कंप्यूटर पर एल्गोरिथम का एक स्पष्ट विवरण 1946 में जॉन मौचली के एक लेख में दिखाई दिया, खोज की सुविधा के लिए वस्तुओं की एक क्रमबद्ध सूची का उपयोग करने का विचार कम से कम 200 ईसा पूर्व बेबिलोनिया तक था।^[5]एक अन्य प्राचीन कमी-और-जीत कलन विधि यूक्लिडियन कलन विधि है जो संख्याओं को छोटे और छोटे समतुल्य उपसमस्याओं में घटाकर दो संख्याओं के सबसे बड़े सामान्य विभाजक की गणना करता है, जो कई शताब्दियों ईसा पूर्व की है।

कई उप-समस्याओं के साथ विभाजित और जीत कलन विधि का एक प्रारंभिक उदाहरण कार्ल फ्रेडरिक गॉस का 1805 का विवरण है जिसे अब कूली-तुकी एफएफटी एल्गोरिदम कहा जाता है। कूली-तुकी फास्ट फूरियर ट्रांसफॉर्म (एफएफटी) एल्गोरिदम।^[6] हालांकि उन्होंने मात्रात्मक रूप से एल्गोरिदम का विश्लेषण नहीं किया, और एफएफटी तब तक व्यापक नहीं हुए जब तक कि उन्हें एक सदी बाद फिर से खोजा नहीं गया।

एक प्रारंभिक दो-उप-समस्या डी एंड सी कलन विधि जो विशेष रूप से कंप्यूटरों के लिए विकसित किया गया था और ठीक से विश्लेषण किया गया था, मर्ज सॉर्ट कलन विधि है, जिसका आविष्कार जॉन वॉन न्यूमैन ने 1945 में किया था।^[7] एक अन्य उल्लेखनीय उदाहरण 1960 में अनातोली अलेक्सीविच करात्सुबा द्वारा आविष्कृत करात्सुबा एल्गोरिद्म है। अनातोली ए. करात्सुबा^[8] जो दो n-अंकीय संख्याओं का गुणा कर सकता है $O(n^{\log _{2}3})$ संचालन (बिग ओ नोटेशन में)। इस कलन विधि ने एंड्री कोलमोगोरोव के 1956 के अनुमान को खारिज कर दिया $\Omega (n^{2})$ उस कार्य के लिए संचालन की आवश्यकता होगी।

फूट डालो और जीतो एल्गोरिद्म के एक अन्य उदाहरण के रूप में, जिसमें मूल रूप से कंप्यूटर शामिल नहीं थे, डोनाल्ड नुथ उस विधि को देते हैं जो एक डाकघर आमतौर पर मेल को रूट करने के लिए उपयोग करता है: पत्रों को अलग-अलग भौगोलिक क्षेत्रों के लिए अलग-अलग बैग में सॉर्ट किया जाता है, इनमें से प्रत्येक बैग को स्वयं सॉर्ट किया जाता है। छोटे उप-क्षेत्रों के लिए बैचों में, और इसी तरह जब तक वे वितरित नहीं हो जाते।^[5] यह एक आपको कामयाबी मिले से संबंधित है, जिसका वर्णन IBM आईबीएम 80 सीरीज कार्ड सॉर्टर्स| पंच-कार्ड सॉर्टिंग मशीनों के लिए 1929 की शुरुआत में किया गया था।^[5]

लाभ

कठिन समस्याओं का समाधान

विभाजन-और-जीत अवधारणात्मक रूप से कठिन समस्याओं को हल करने के लिए एक शक्तिशाली उपकरण है: इसके लिए केवल समस्या को उप-समस्याओं में खंडित करने, तुच्छ समस्याओं को हल करने और उप-समस्याओं को मूल समस्या से जोड़ने का एक तरीका है। इसी तरह, ह्रास-और-जीत केवल समस्या को एक छोटी समस्या में कम करने की आवश्यकता है, जैसे हनोई पहेली का क्लासिक टॉवर, जो $n$ ऊंचाई के टॉवर को स्थानांतरित कर $n-1$ ऊंचाई के टावर तक कम कर देता हैं।

एल्गोरिथम दक्षता

विभाजन-और-जीत प्रतिमान प्रायः कुशल कलनविधि की खोज में सहायता करता है। उदाहरण के लिए, यह, करात्सुबा की तीव्र गुणन विधि, क्विकसॉर्ट और मर्जसॉर्ट कलनविधि, मैट्रिक्स गुणन के लिए स्ट्रैसन कलनविधि और फास्ट फूरियर ट्रांसफॉर्म्स (एफ एफ टी) की कुंजी थी।

इन सभी उदाहरणों में, डी एंड सी दृष्टिकोण ने समाधान की उपगामी लागत में सुधार किया। उदाहरण के लिए, यदि (ए) आधार समस्याओं का आकार स्थिर-परिबद्ध है, तो समस्या को विभाजित करने और आंशिक समाधानों के संयोजन का कार्य समस्या के आकार $n$ के समानुपाती होता है और प्रत्येक (बी) चरण में,~ $n/p$ आकार की एक $p$ परिबद्ध संख्या संख्या की उप- समस्याएं हैं, तब विभाजन-और-जीत कलनविधि की लागत $O(n\log _{p}n)$ होगी।

समांतरवाद

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

मेमोरी एक्सेस

विभाजन और जीत एल्गोरिदम स्वाभाविक रूप से मेमोरी कैश का कुशल उपयोग करते हैं। इसका कारण यह है कि एक बार एक उप-समस्या अधिक छोटी हो जाती है, तो इसे और इसकी सभी उप-समस्याओं को, सिद्धांत रूप में, धीमी मुख्य मेमोरी तक पहुंचे बिना कैश के भीतर हल किया जा सकता है। इस तरह से कैश का समुपयोजन करने के लिए परिकलन किया गया कलनविधि कैश-अब्लिवीअस कहा जाता है, क्योंकि इसमें कैश आकार को एक स्पष्ट मापदण्ड के रूप में सम्मिलित नहीं किया जाता है।^[9] इसके अतिरिक्त, डी एंड सी कलनविधि को महत्वपूर्ण कलनविधि के लिए परिकलन किया जा सकता है (उदाहरण के लिए, सॉर्टिंग, एफएफटी, और मैट्रिक्स गुणन) इष्टतम कैश-अब्लिवीअस कलनविधि होने के लिए - वे कैश का उपयोग संभवत: इष्टतम तरीके से करते हैं, एक स्पर्शोन्मुख अर्थ में, चाहे कैचे का आकार कुछ भी हो। इसके विपरीत, कैश का समुपयोजन करने का पारंपरिक तरीका है ब्लॉकिंग (अवरोधन), जैसा कि लूप नेस्ट ऑप्टिमाइज़ेशन में होता है, जहाँ समस्या को स्पष्ट रूप से उपयुक्त आकार के टुकड़ों में विभाजित किया जाता है - यह कैश का भी इष्टतम उपयोग कर सकता है, लेकिन केवल तभी जब कलनविधि किसी विशेष मशीन के विशिष्ट कैश आकार के लिए समस्वरित किया जाता है।

अन्य पदानुक्रमित भंडारण प्रणालियों, जैसे गैर-समान मेमोरी एक्सेस या आभासी मेमोरी, के साथ-साथ कैश के कई स्तरों के संबंध में भी यही लाभ विद्यमान है: एक बार एक उप-समस्या अधिक छोटी हो जाती है, इसे पदानुक्रम के दिए गए स्तर के अन्तर्गत उच्च (धीमे) स्तरों तक पहुँचे बिना हल किया जा सकता है।

राउंडऑफ नियंत्रण

गोलाकार अंकगणित संगणना में, उदाहरण के लिए फ़्लोटिंग-पॉइंट संख्याओं के साथ, विभाजन-और-जीत कलनविधि सतही समकक्ष पुनरावृत्त विधि की तुलना में अधिक सटीक परिणाम दे सकता है। उदाहरण के लिए, N संख्याओं को या तो एक साधारण लूप द्वारा जोड़ा जा सकता है जो प्रत्येक डेटा को एक चर में जोड़ता है, या एक डी एंड सी कलनविधि द्वारा जिसे जोड़ीदार योग जो डेटा समुच्चय को दो हिस्सों में तोड़ता है, प्रत्येक आधे के योग की पुनरावर्ती गणना करता है, और पुनः दो योगफल को जोड़ता है। जबकि दूसरी विधि पहले की तरह समान संख्या में जोड़ करती है और पुनरावर्ती कॉल के उपरिव्यय का भुगतान करती है, यह सामान्यतः अधिक सटीक होती है।^[10]

कार्यान्वयन के लिए विवाद

रिकर्सन

विभाजन-और-जीत कलनविधि को स्वाभाविक रूप से पुनरावर्ती प्रक्रियाओं के रूप में परिपालित किया जाता है। उस स्थिति में, वर्तमान में हल की जा रही आंशिक उप-समस्याओं को प्रक्रिया कॉल स्टैक में स्वचालित रूप से संग्रहीत किया जाता है। एक पुनरावर्ती कार्य एक ऐसा कार्य है जो स्वयं को अपनी परिभाषा में आह्वान करता है।

स्पष्ट ढेर

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

स्टैक का आकार

डी एंड सी कलनविधि के पुनरावर्ती कार्यान्वयन में, यह सुनिश्चित करना चाहिए कि पुनरावर्तन स्टैक के लिए पर्याप्त मेमोरी आवंटित की गई है, अन्यथा स्टैक ओवरफ़्लो स्टैक ओवरफ्लो के कारण निष्पादन विफल हो सकता है। डी एंड सी कलनविधि जो समय-कुशल होते हैं, प्रायः अपेक्षाकृत कम पुनरावर्तन गहराई होती है। उदाहरण के लिए, क्विकसॉर्ट कलनविधि को परिपालित किया जा सकता है ताकि इसे कभी भी $n$ वस्तुओं को क्रमबद्ध करने के लिए अधिक $\log _{2}n$ नीड़ बद्ध पुनरावर्ती कॉल की आवश्यकता न हो।

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

आधार मामलों का चयन

किसी भी पुनरावर्ती कलनविधि में, आधार समस्याओं की चयन में पर्याप्त स्वतंत्रता होती है, छोटी उप-समस्याएं जिन्हें पुनरावर्तन को समाप्त करने के लिए सीधे हल किया जाता है।

सबसे छोटे या सरलतम संभावित आधार समस्याओं को चुनना अधिक सुरुचिपूर्ण है और सामान्यतः सरल कार्यक्रमों की ओर जाता है, क्योंकि विचार करने के लिए कम समस्याएं होते हैं और उन्हें हल करना आसान होता है। उदाहरण के लिए, एक एफ एफ टी कलनविधि पुनरावर्तन को रोक सकता है जब इनपुट एक एकल नमूना होता है, और क्विकसॉर्ट लिस्ट-सॉर्टिंग कलनविधि तब रुक सकता है जब इनपुट रिक्त सूची हो; दोनों उदाहरणों में, विचार करने के लिए केवल एक आधार समस्या है, और इसके लिए किसी प्रसंस्करण की आवश्यकता नहीं है।

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

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

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

इस विचार के सामान्यीकृत संस्करण को पुनरावर्तन "अनरोलिंग" या "कोर्सनिंग" के रूप में जाना जाता है, और आधार समस्याओं को बढ़ाने की प्रक्रिया को स्वचालित करने के लिए विभिन्न तकनीकों का प्रस्ताव किया गया है।^[11]

इस विचार के सामान्यीकृत संस्करण को रिकर्सन अनोलिंग या मोटे होने के रूप में जाना जाता है, और आधार मामले को बढ़ाने की प्रक्रिया को स्वचालित करने के लिए विभिन्न तकनीकों का प्रस्ताव दिया गया है।^[12]

अतिव्यापी उप-समस्याओं के लिए गतिशील प्रोग्रामिंग

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

यह भी देखें

संदर्भ

↑ Blahut, Richard (14 May 2014). Fast Algorithms for Signal Processing. Cambridge University Press. pp. 139–143. ISBN 978-0-511-77637-3.
↑ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (31 July 2009). Introduction to Algorithms. MIT Press. ISBN 978-0-262-53305-8.
↑ Brassard, G., and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.
↑ Anany V. Levitin, Introduction to the Design and Analysis of Algorithms (Addison Wesley, 2002).
↑ ^5.0 ^5.1 ^5.2 Donald E. Knuth, The Art of Computer Programming: Volume 3, Sorting and Searching, second edition (Addison-Wesley, 1998).
↑ Heideman, M. T., D. H. Johnson, and C. S. Burrus, "Gauss and the history of the fast Fourier transform", IEEE ASSP Magazine, 1, (4), 14–21 (1984).
↑ Knuth, Donald (1998). The Art of Computer Programming: Volume 3 Sorting and Searching. p. 159. ISBN 0-201-89685-0.
↑ Karatsuba, Anatolii A.; Yuri P. Ofman (1962). "Умножение многозначных чисел на автоматах". Doklady Akademii Nauk SSSR. 146: 293–294. Translated in Karatsuba, A.; Ofman, Yu. (1963). "Multiplication of Multidigit Numbers on Automata". Soviet Physics Doklady. 7: 595–596. Bibcode:1963SPhD....7..595K.
↑ M. Frigo; C. E. Leiserson; H. Prokop (1999). "Cache-oblivious algorithms". Proc. 40th Symp. On the Foundations of Computer Science: 285–297. doi:10.1109/SFFCS.1999.814600. ISBN 0-7695-0409-4. S2CID 62758836.
↑ Nicholas J. Higham, "The accuracy of floating-point summation", SIAM J. Scientific Computing 14 (4), 783–799 (1993).
↑ Frigo, M.; Johnson, S. G. (February 2005). "The design and implementation of FFTW3" (PDF). Proceedings of the IEEE. 93 (2): 216–231. CiteSeerX 10.1.1.66.3097. doi:10.1109/JPROC.2004.840301. S2CID 6644892.
↑ Radu Rugina and Martin Rinard, "Recursion unrolling for divide and conquer programs" in Languages and Compilers for Parallel Computing, chapter 3, pp. 34–48. Lecture Notes in Computer Science vol. 2017 (Berlin: Springer, 2001).

[1] Blahut, Richard (14 May 2014). Fast Algorithms for Signal Processing. Cambridge University Press. pp. 139–143. ISBN 978-0-511-77637-3.

[CormenLeiserson2009-2] Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (31 July 2009). Introduction to Algorithms. MIT Press. ISBN 978-0-262-53305-8.

[3] Brassard, G., and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.

[4] Anany V. Levitin, Introduction to the Design and Analysis of Algorithms (Addison Wesley, 2002).

[Knuth3-5] 5.0 ^5.1 ^5.2 Donald E. Knuth, The Art of Computer Programming: Volume 3, Sorting and Searching, second edition (Addison-Wesley, 1998).

[Heideman84-6] Heideman, M. T., D. H. Johnson, and C. S. Burrus, "Gauss and the history of the fast Fourier transform", IEEE ASSP Magazine, 1, (4), 14–21 (1984).

[7] Knuth, Donald (1998). The Art of Computer Programming: Volume 3 Sorting and Searching. p. 159. ISBN 0-201-89685-0.

[8] Karatsuba, Anatolii A.; Yuri P. Ofman (1962). "Умножение многозначных чисел на автоматах". Doklady Akademii Nauk SSSR. 146: 293–294. Translated in Karatsuba, A.; Ofman, Yu. (1963). "Multiplication of Multidigit Numbers on Automata". Soviet Physics Doklady. 7: 595–596. Bibcode:1963SPhD....7..595K.

[cahob-9] M. Frigo; C. E. Leiserson; H. Prokop (1999). "Cache-oblivious algorithms". Proc. 40th Symp. On the Foundations of Computer Science: 285–297. doi:10.1109/SFFCS.1999.814600. ISBN 0-7695-0409-4. S2CID 62758836.

[10] Nicholas J. Higham, "The accuracy of floating-point summation", SIAM J. Scientific Computing 14 (4), 783–799 (1993).

[fftw-11] Frigo, M.; Johnson, S. G. (February 2005). "The design and implementation of FFTW3" (PDF). Proceedings of the IEEE. 93 (2): 216–231. CiteSeerX 10.1.1.66.3097. doi:10.1109/JPROC.2004.840301. S2CID 6644892.

[12] Radu Rugina and Martin Rinard, "Recursion unrolling for divide and conquer programs" in Languages and Compilers for Parallel Computing, chapter 3, pp. 34–48. Lecture Notes in Computer Science vol. 2017 (Berlin: Springer, 2001).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

@@ Line 2: / Line 2: @@
 [[कंप्यूटर विज्ञान]] में, विभाजन और जीत एक [[कलन विधि]] डिजाइन प्रतिमान है। विभाजन और जीत कलनविधि एक समस्या  को पुनरावर्ततः समान या संबंधित प्रकार की दो या दो से अधिक उप-समस्याओं में तब तक खंडित करता है, जब तक कि ये सीधे हल करने के लिए पर्याप्त सरल न हो जाएं। उप-समस्याओं के समाधान को तब मूल समस्या का समाधान करने के लिए संयोजित किया जाता है।
-विभाजन और जीत तकनीक कई समस्याओं के लिए कुशल कलनविधि का आधार है, जैसे [[छँटाई एल्गोरिथ्म|पृथक्करण एल्गोरिथ्म]] (उदाहरण के लिए, त्वरित सॉर्ट, [[मर्ज़ सॉर्ट]]),  बृहत्संख्या को गुणा करना (जैसे, करात्सुबा कलनविधि ), बिंदुओं की निकटतम जोड़ी खोजना, वाक्यात्मक विश्लेषण (उदाहरण के लिए, टॉप-डाउन पार्सर्स अर्थात शीर्ष पाद पद विन्यासक) और असतत फूरियर रूपांतरण (एफ एफ टी) की गणना करना।<ref>{{cite book |last1=Blahut |first1=Richard |title=Fast Algorithms for Signal Processing |date=14 May 2014 |publisher=Cambridge University Press |isbn=978-0-511-77637-3 |pages=139–143}}</ref>
+विभाजन और जीत तकनीक कई समस्याओं के लिए कुशल कलनविधि का आधार है, जैसे [[छँटाई एल्गोरिथ्म|पृथक्करण कलन विधि]] (उदाहरण के लिए, त्वरित सॉर्ट, [[मर्ज़ सॉर्ट]]),  बृहत्संख्या को गुणा करना (जैसे, करात्सुबा कलनविधि ), बिंदुओं की निकटतम जोड़ी खोजना, वाक्यात्मक विश्लेषण (उदाहरण के लिए, टॉप-डाउन पार्सर्स अर्थात शीर्ष पाद पद विन्यासक) और असतत फूरियर रूपांतरण (एफ एफ टी) की गणना करना।<ref>{{cite book |last1=Blahut |first1=Richard |title=Fast Algorithms for Signal Processing |date=14 May 2014 |publisher=Cambridge University Press |isbn=978-0-511-77637-3 |pages=139–143}}</ref>
-कुशल विभाजन और जीत कलनविधि अभिकल्पना करना कठिन हो सकता है। जैसा कि गणितीय आगमन में होता है, प्रायः समस्या को पुनरावर्ती समाधान करके उत्तरदायी बनाने के लिए सामान्यीकरण करना आवश्यक होता है। विभाजन और जीत कलनविधि की शुद्धता सामान्यतः [[गणितीय प्रेरण]] द्वारा सिद्ध होती है, और इसकी कम्प्यूटेशनल लागत अक्सर [[पुनरावृत्ति संबंध]]ों को हल करके निर्धारित की जाती है।
+कुशल विभाजन और जीत कलनविधि अभिकल्पना करना कठिन हो सकता है। जैसा कि गणितीय आगमन में होता है, प्रायः समस्या को पुनरावर्ती समाधान करके उत्तरदायी बनाने के लिए सामान्यीकरण करना आवश्यक होता है। विभाजन और जीत कलनविधि की शुद्धता सामान्यतः [[गणितीय प्रेरण]] द्वारा सिद्ध होती है, और इसकी अभिकलनात्मक लागत प्रायः [[पुनरावृत्ति संबंध|पुनरावृत्ति संबंधों]] को हल करके निर्धारित की जाती है।
 == फूट डालो और राज करो ==
-[[File:Merge sort algorithm diagram.svg|thumb|बढ़ते क्रम में सूची (38, 27, 43, 3, 9, 82, 10) को क्रमबद्ध करने के लिए फूट डालो और जीतो दृष्टिकोण। ऊपरी आधा: सब्लिस्ट्स में विभाजन; मध्य: एक-तत्व सूची तुच्छ रूप से क्रमबद्ध है; निचला आधा: सॉर्ट किए गए सबलिस्ट्स की रचना।]]फूट डालो और जीतो प्रतिमान का उपयोग अक्सर किसी समस्या का इष्टतम समाधान खोजने के लिए किया जाता है। इसका मूल विचार दी गई समस्या को दो या अधिक समान, लेकिन सरल, उप-समस्याओं में विघटित करना है, उन्हें बारी-बारी से हल करना और दी गई समस्या को हल करने के लिए उनके समाधानों की रचना करना है। पर्याप्त सरलता की समस्याएं सीधे हल हो जाती हैं।
+[[File:Merge sort algorithm diagram.svg|thumb|बढ़ते क्रम में सूची (38, 27, 43, 3, 9, 82, 10) को क्रमबद्ध करने के लिए विभाजन और जीत दृष्टिकोण। ऊपरी आधा: सब्लिस्ट्स में विभाजन; मध्य: एक-तत्व सूची तुच्छ रूप से क्रमबद्ध है; निचला आधा: सॉर्ट किए गए सबलिस्ट्स की रचना।]]विभाजन और जीत प्रतिमान का उपयोग प्रायः किसी समस्या का इष्टतम समाधान खोजने के लिए किया जाता था। इसका मूल विचार दी गई समस्या को दो या अधिक समान, लेकिन सरल, उप-समस्याओं में वियोजित करना है, उन्हें बारी-बारी से समाधान करना और दी गई समस्या को समाधान करने के लिए उनके समाधानों की रचना करना है। पर्याप्त सरलता की समस्याएं सीधे हो जाती हैं।
-उदाहरण के लिए, n प्राकृतिक संख्याओं की दी गई सूची को क्रमबद्ध करने के लिए, इसे लगभग n/2 संख्याओं की दो सूचियों में विभाजित करें, उनमें से प्रत्येक को बारी-बारी से क्रमबद्ध करें, और दी गई सूची का क्रमबद्ध संस्करण प्राप्त करने के लिए दोनों परिणामों को उचित रूप से इंटरलीव करें (देखें) चित्र)। इस दृष्टिकोण को मर्ज सॉर्ट एल्गोरिथम के रूप में जाना जाता है।
+उदाहरण के लिए, n प्राकृतिक संख्याओं की दी गई सूची को क्रमबद्ध करने के लिए, इसे लगभग n /2 संख्याओं मे प्रत्येक की दो सूचियों में विभाजित करें, उनमें से प्रत्येक को बारी-बारी से क्रमबद्ध करें, और दी गई सूची के क्रमबद्ध संस्करण को प्राप्त करने के लिए दोनों परिणामों को उचित रूप से अंतरापत्र करें ( चित्र देखें)। इस दृष्टिकोण को मर्ज सॉर्ट कलनविधि के रूप में जाना जाता है।
-विभाजित करें और जीतें नाम को कभी-कभी एल्गोरिदम पर लागू किया जाता है जो प्रत्येक समस्या को केवल एक उप-समस्या तक कम कर देता है, जैसे बाइनरी खोज एल्गोरिदम एक क्रमबद्ध सूची में रिकॉर्ड खोजने के लिए (या संख्यात्मक एल्गोरिदम में इसका एनालॉग, रूट-खोज के लिए द्विभाजन एल्गोरिदम) कलन विधि)।<ref name="CormenLeiserson2009">{{cite book|author1=Thomas H. Cormen|author2=Charles E. Leiserson|author3=Ronald L. Rivest|author4=Clifford Stein|title=Introduction to Algorithms|url=https://books.google.com/books?id=aefUBQAAQBAJ&q=%22Divide-and-conquer%22|date=31 July 2009|publisher=MIT Press|isbn=978-0-262-53305-8}}</ref> इन एल्गोरिदम को सामान्य डिवाइड-एंड-कॉनकॉर एल्गोरिदम की तुलना में अधिक कुशलता से लागू किया जा सकता है; विशेष रूप से, यदि वे [[पूंछ पुनरावर्तन]] का उपयोग करते हैं, तो उन्हें साधारण [[पाश (कंप्यूटिंग)]] में परिवर्तित किया जा सकता है। हालांकि, इस व्यापक परिभाषा के तहत, प्रत्येक एल्गोरिदम जो रिकर्सन या लूप का उपयोग करता है, उसे विभाजन और जीत एल्गोरिदम के रूप में माना जा सकता है। इसलिए, कुछ लेखकों का मानना है कि फूट डालो और जीतो नाम का उपयोग तभी किया जाना चाहिए जब प्रत्येक समस्या दो या दो से अधिक उप-समस्याएं उत्पन्न कर सकती है।<ref>Brassard, G., and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.</ref> एकल-उप-समस्या वर्ग के बजाय नाम घटाना और जीतना प्रस्तावित किया गया है।<ref>Anany V. Levitin, ''Introduction to the Design and Analysis of Algorithms'' (Addison Wesley, 2002).</ref>
+"विभाजन और जीत" नाम कभी-कभी कलनविधि पर लागू होता है जो प्रत्येक समस्या को केवल एक उप-समस्या तक घटाता है, जैसे कि बाइनरी सर्च कलनविधि जो एक क्रमबद्ध सूची में रिकॉर्ड खोजने के लिए (या संख्यात्मक अभिकलन में इसका अनुरूप , मूलनिर्धारण के लिए द्विभाजन कलनविधि ) किया जाता है।<ref name="CormenLeiserson2009">{{cite book|author1=Thomas H. Cormen|author2=Charles E. Leiserson|author3=Ronald L. Rivest|author4=Clifford Stein|title=Introduction to Algorithms|url=https://books.google.com/books?id=aefUBQAAQBAJ&q=%22Divide-and-conquer%22|date=31 July 2009|publisher=MIT Press|isbn=978-0-262-53305-8}}</ref> सामान्य विभाजन और जीत कलनविधि की तुलना में इन कलनविधि को अधिक कुशलता से लागू किया जा सकता है; विशेष रूप से, यदि वे [[पूंछ पुनरावर्तन|टेल रिकर्सन]] का उपयोग करते हैं, तो उन्हें साधारण [[पाश (कंप्यूटिंग)|सरल लूप (कंप्यूटिंग)]] में परिवर्तित किया जा सकता है। यद्यपि, इस व्यापक परिभाषा के अंतर्गत, प्रत्येक कलनविधि जो रिकर्सन या लूप का उपयोग करता है, उसे "विभाजन और जीत कलनविधि" के रूप में माना जा सकता है। इसलिए, कुछ लेखकों का मानना है कि "विभाजन और जीत" नाम का उपयोग केवल तभी किया जाना चाहिए जब प्रत्येक समस्या दो या दो से अधिक उप-समस्याएं उत्पन्न कर सकती है।<ref>Brassard, G., and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.</ref>  एकल-उप-समस्या वर्ग के स्थान पर ह्रास और जीत नाम प्रस्तावित किया गया है।<ref>Anany V. Levitin, ''Introduction to the Design and Analysis of Algorithms'' (Addison Wesley, 2002).</ref>
-फूट डालो और जीतो का एक महत्वपूर्ण अनुप्रयोग अनुकूलन में है,{{Examples|date=October 2017}} जहां यदि प्रत्येक चरण पर एक स्थिर कारक द्वारा खोज स्थान को कम (छंटाई) किया जाता है, तो समग्र एल्गोरिथ्म में प्रूनिंग चरण के समान विषम जटिलता होती है, जिसमें प्रूनिंग कारक (ज्यामितीय श्रृंखला को जोड़कर) पर निर्भर करता है; इसे [[छँटाई और खोज]] के रूप में जाना जाता है।
+विभाजन और जीत का एक महत्वपूर्ण अनुप्रयोग अनुकूलीकरण में है,{{Examples|date=October 2017}} जहां यदि प्रत्येक चरण पर एक स्थिर कारक द्वारा खोज स्थान को कम ("छंटनी") किया जाता है, तो समग्र कलनविधि में प्रूनिंग चरण के समान विषम जटिलता होती है, साथ में प्रूनिंग कारक स्थिरांक पर निर्भर करता है (ज्यामितीय श्रृंखला को जोड़कर); इसे [[छँटाई और खोज|प्रून एंड सर्च]]  के रूप में जाना जाता है।
 == प्रारंभिक ऐतिहासिक उदाहरण ==
-इन एल्गोरिदम के शुरुआती उदाहरण प्राथमिक रूप से घटते हैं और जीतते हैं - मूल समस्या क्रमिक रूप से एकल उप-समस्याओं में टूट जाती है, और वास्तव में इसे पुनरावृत्त रूप से हल किया जा सकता है।
+इन कलनविधि के प्रारंभिक उदाहरण प्राथमिक रूप से ह्रास और जीत हैं - मूल समस्या क्रमिक रूप से एकल उप-समस्याओं में खंडित किया जाता है, और वास्तव में इसे पुनरावृत्त रूप से समाधान किया जा सकता है।
-बाइनरी खोज, एक कमी-और-जीत एल्गोरिथ्म जहां उप-समस्याएं लगभग आधे मूल आकार की होती हैं, का एक लंबा इतिहास रहा है। जबकि कंप्यूटर पर एल्गोरिथम का एक स्पष्ट विवरण 1946 में [[जॉन मौचली]] के एक लेख में दिखाई दिया, खोज की सुविधा के लिए वस्तुओं की एक क्रमबद्ध सूची का उपयोग करने का विचार कम से कम 200 ईसा पूर्व [[बेबिलोनिया]] तक था।<ref name=Knuth3/>एक अन्य प्राचीन कमी-और-जीत एल्गोरिथ्म [[यूक्लिडियन एल्गोरिथ्म]] है जो संख्याओं को छोटे और छोटे समतुल्य उपसमस्याओं में घटाकर दो संख्याओं के सबसे बड़े सामान्य विभाजक की गणना करता है, जो कई शताब्दियों ईसा पूर्व की है।
+बाइनरी खोज, एक कमी-और-जीत कलन विधि जहां उप-समस्याएं लगभग आधे मूल आकार की होती हैं, का एक लंबा इतिहास रहा है। जबकि कंप्यूटर पर एल्गोरिथम का एक स्पष्ट विवरण 1946 में [[जॉन मौचली]] के एक लेख में दिखाई दिया, खोज की सुविधा के लिए वस्तुओं की एक क्रमबद्ध सूची का उपयोग करने का विचार कम से कम 200 ईसा पूर्व [[बेबिलोनिया]] तक था।<ref name=Knuth3/>एक अन्य प्राचीन कमी-और-जीत कलन विधि [[यूक्लिडियन एल्गोरिथ्म|यूक्लिडियन कलन विधि]] है जो संख्याओं को छोटे और छोटे समतुल्य उपसमस्याओं में घटाकर दो संख्याओं के सबसे बड़े सामान्य विभाजक की गणना करता है, जो कई शताब्दियों ईसा पूर्व की है।
-कई उप-समस्याओं के साथ विभाजित और जीत एल्गोरिथ्म का एक प्रारंभिक उदाहरण [[कार्ल फ्रेडरिक गॉस]] का 1805 का विवरण है जिसे अब कूली-तुकी एफएफटी एल्गोरिदम कहा जाता है। कूली-तुकी फास्ट फूरियर ट्रांसफॉर्म (एफएफटी) एल्गोरिदम।<ref name=Heideman84>Heideman, M. T., D. H. Johnson, and C. S. Burrus, "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.331.4791&rep=rep1&type=pdf Gauss and the history of the fast Fourier transform]", IEEE ASSP Magazine, 1, (4), 14–21 (1984).</ref> हालांकि उन्होंने मात्रात्मक रूप से [[एल्गोरिदम का विश्लेषण]] नहीं किया, और एफएफटी तब तक व्यापक नहीं हुए जब तक कि उन्हें एक सदी बाद फिर से खोजा नहीं गया।
+कई उप-समस्याओं के साथ विभाजित और जीत कलन विधि का एक प्रारंभिक उदाहरण [[कार्ल फ्रेडरिक गॉस]] का 1805 का विवरण है जिसे अब कूली-तुकी एफएफटी एल्गोरिदम कहा जाता है। कूली-तुकी फास्ट फूरियर ट्रांसफॉर्म (एफएफटी) एल्गोरिदम।<ref name=Heideman84>Heideman, M. T., D. H. Johnson, and C. S. Burrus, "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.331.4791&rep=rep1&type=pdf Gauss and the history of the fast Fourier transform]", IEEE ASSP Magazine, 1, (4), 14–21 (1984).</ref> हालांकि उन्होंने मात्रात्मक रूप से [[एल्गोरिदम का विश्लेषण]] नहीं किया, और एफएफटी तब तक व्यापक नहीं हुए जब तक कि उन्हें एक सदी बाद फिर से खोजा नहीं गया।
-एक प्रारंभिक दो-उप-समस्या डी एंड सी एल्गोरिथ्म जो विशेष रूप से कंप्यूटरों के लिए विकसित किया गया था और ठीक से विश्लेषण किया गया था, मर्ज सॉर्ट एल्गोरिथ्म है, जिसका आविष्कार [[जॉन वॉन न्यूमैन]] ने 1945 में किया था।<ref>{{ cite book | last=Knuth | first=Donald | author-link=Donald Knuth | year=1998 | title=The Art of Computer Programming: Volume 3 Sorting and Searching | url=https://archive.org/details/artofcomputerpro03knut | url-access=limited | page=[https://archive.org/details/artofcomputerpro03knut/page/159 159] | isbn=0-201-89685-0 }}</ref>
+एक प्रारंभिक दो-उप-समस्या डी एंड सी कलन विधि जो विशेष रूप से कंप्यूटरों के लिए विकसित किया गया था और ठीक से विश्लेषण किया गया था, मर्ज सॉर्ट कलन विधि है, जिसका आविष्कार [[जॉन वॉन न्यूमैन]] ने 1945 में किया था।<ref>{{ cite book | last=Knuth | first=Donald | author-link=Donald Knuth | year=1998 | title=The Art of Computer Programming: Volume 3 Sorting and Searching | url=https://archive.org/details/artofcomputerpro03knut | url-access=limited | page=[https://archive.org/details/artofcomputerpro03knut/page/159 159] | isbn=0-201-89685-0 }}</ref>
-एक अन्य उल्लेखनीय उदाहरण 1960 में अनातोली अलेक्सीविच करात्सुबा द्वारा आविष्कृत करात्सुबा एल्गोरिद्म है। अनातोली ए. करात्सुबा<ref>{{cite journal| last=Karatsuba | first=Anatolii A. | author-link=Anatolii Alexeevitch Karatsuba |author2=Yuri P. Ofman |author-link2=Yuri Petrovich Ofman | year=1962 | title=Умножение многозначных чисел на автоматах | journal=[[Doklady Akademii Nauk SSSR]] | volume=146 | pages=293–294}} Translated in {{cite journal| title=Multiplication of Multidigit Numbers on Automata | journal=Soviet Physics Doklady | volume=7 | year=1963 | pages=595–596 | bibcode=1963SPhD....7..595K |url={{Google books|MrkOAAAAIAAJ|plainurl=true}} | last1=Karatsuba | first1=A. | last2=Ofman | first2=Yu. }}</ref> जो दो n-अंकीय संख्याओं का गुणा कर सकता है <math>O(n^{\log_2 3})</math> संचालन ([[बिग ओ नोटेशन]] में)। इस एल्गोरिथ्म ने [[एंड्री कोलमोगोरोव]] के 1956 के अनुमान को खारिज कर दिया <math>\Omega(n^2)</math> उस कार्य के लिए संचालन की आवश्यकता होगी।
+एक अन्य उल्लेखनीय उदाहरण 1960 में अनातोली अलेक्सीविच करात्सुबा द्वारा आविष्कृत करात्सुबा एल्गोरिद्म है। अनातोली ए. करात्सुबा<ref>{{cite journal| last=Karatsuba | first=Anatolii A. | author-link=Anatolii Alexeevitch Karatsuba |author2=Yuri P. Ofman |author-link2=Yuri Petrovich Ofman | year=1962 | title=Умножение многозначных чисел на автоматах | journal=[[Doklady Akademii Nauk SSSR]] | volume=146 | pages=293–294}} Translated in {{cite journal| title=Multiplication of Multidigit Numbers on Automata | journal=Soviet Physics Doklady | volume=7 | year=1963 | pages=595–596 | bibcode=1963SPhD....7..595K |url={{Google books|MrkOAAAAIAAJ|plainurl=true}} | last1=Karatsuba | first1=A. | last2=Ofman | first2=Yu. }}</ref> जो दो n-अंकीय संख्याओं का गुणा कर सकता है <math>O(n^{\log_2 3})</math> संचालन ([[बिग ओ नोटेशन]] में)। इस कलन विधि ने [[एंड्री कोलमोगोरोव]] के 1956 के अनुमान को खारिज कर दिया <math>\Omega(n^2)</math> उस कार्य के लिए संचालन की आवश्यकता होगी।
 फूट डालो और जीतो एल्गोरिद्म के एक अन्य उदाहरण के रूप में, जिसमें मूल रूप से कंप्यूटर शामिल नहीं थे, [[डोनाल्ड नुथ]] उस विधि को देते हैं जो एक डाकघर आमतौर पर मेल को रूट करने के लिए उपयोग करता है: पत्रों को अलग-अलग भौगोलिक क्षेत्रों के लिए अलग-अलग बैग में सॉर्ट किया जाता है, इनमें से प्रत्येक बैग को स्वयं सॉर्ट किया जाता है। छोटे उप-क्षेत्रों के लिए बैचों में, और इसी तरह जब तक वे वितरित नहीं हो जाते।<ref name=Knuth3>Donald E. Knuth, ''The Art of Computer Programming: Volume 3, Sorting and Searching'', second edition (Addison-Wesley, 1998).</ref> यह एक [[आपको कामयाबी मिले]] से संबंधित है, जिसका वर्णन IBM [[आईबीएम 80 सीरीज कार्ड सॉर्टर्स]]| पंच-कार्ड सॉर्टिंग मशीनों के लिए 1929 की शुरुआत में किया गया था।<ref name=Knuth3/>
@@ Line 29: / Line 30: @@
 === कठिन समस्याओं का समाधान ===
-फूट डालो और जीतो अवधारणात्मक रूप से कठिन समस्याओं को हल करने के लिए एक शक्तिशाली उपकरण है: इसके लिए केवल समस्या को उप-समस्याओं में तोड़ने, तुच्छ मामलों को हल करने और उप-समस्याओं को मूल समस्या से जोड़ने का एक तरीका है। इसी तरह, घटाना और जीतना केवल समस्या को एक छोटी समस्या में कम करने की आवश्यकता है, जैसे हनोई पहेली का क्लासिक टॉवर, जो ऊंचाई के टावर को कम कर देता है <math>n</math> ऊंचाई के टॉवर को स्थानांतरित करने के लिए <math>n-1</math>.
+विभाजन-और-जीत अवधारणात्मक रूप से कठिन समस्याओं को हल करने के लिए एक शक्तिशाली उपकरण है: इसके लिए केवल समस्या को उप-समस्याओं में खंडित करने, तुच्छ समस्याओं को हल करने और उप-समस्याओं को मूल समस्या से जोड़ने का एक तरीका है। इसी तरह, ह्रास-और-जीत केवल समस्या को एक छोटी समस्या में कम करने की आवश्यकता है, जैसे हनोई पहेली का क्लासिक टॉवर, जो <math>n</math> ऊंचाई के टॉवर को स्थानांतरित कर  <math>n-1</math> ऊंचाई के टावर तक कम कर देता हैं।
 === एल्गोरिथम दक्षता ===
-फूट डालो और जीतो प्रतिमान अक्सर कुशल एल्गोरिदम की खोज में मदद करता है। यह कुंजी थी, उदाहरण के लिए, करात्सुबा की तेजी से गुणन विधि, क्विकसॉर्ट और मर्जसॉर्ट एल्गोरिदम, मैट्रिक्स गुणन के लिए [[सड़क एल्गोरिथ्म]], और तेजी से फूरियर रूपांतरण।
+विभाजन-और-जीत प्रतिमान प्रायः कुशल कलनविधि की खोज में सहायता करता है। उदाहरण के लिए, यह, करात्सुबा की तीव्र गुणन विधि, क्विकसॉर्ट और मर्जसॉर्ट कलनविधि, मैट्रिक्स गुणन के लिए स्ट्रैसन कलनविधि और फास्ट फूरियर ट्रांसफॉर्म्स (एफ एफ टी) की कुंजी थी।
-इन सभी उदाहरणों में, डी एंड सी दृष्टिकोण ने समाधान की उपगामी जटिलता में सुधार किया। उदाहरण के लिए, यदि (ए) रिकर्सन (कंप्यूटर विज्ञान) का आकार स्थिर है, तो समस्या को विभाजित करने और आंशिक समाधानों के संयोजन का कार्य समस्या के आकार के समानुपाती होता है <math>n</math>, और (बी) एक परिबद्ध संख्या है <math>p</math> आकार की उप-समस्याओं की ~ <math>n/p</math> प्रत्येक चरण में, तब फूट डालो और जीतो एल्गोरिथम की लागत होगी <math>O(n\log_{p}n)</math>.
+इन सभी उदाहरणों में, डी एंड सी दृष्टिकोण ने समाधान की उपगामी लागत में सुधार किया। उदाहरण के लिए, यदि (ए) आधार समस्याओं का आकार स्थिर-परिबद्ध है, तो समस्या को विभाजित करने और आंशिक समाधानों के संयोजन का कार्य समस्या के आकार <math>n</math> के समानुपाती होता है और प्रत्येक (बी) चरण में,~ <math>n/p</math> आकार की एक  <math>p</math>  परिबद्ध संख्या संख्या की उप- समस्याएं हैं, तब विभाजन-और-जीत कलनविधि की लागत <math>O(n\log_{p}n)</math> होगी।
-=== समानता ===
+=== समांतरवाद ===
-मल्टी-प्रोसेसर मशीनों, विशेष रूप से साझा-मेमोरी सिस्टम में निष्पादन के लिए डिवाइड-एंड-कॉनकोर एल्गोरिदम को स्वाभाविक रूप से अनुकूलित किया जाता है, जहां प्रोसेसर के बीच डेटा के संचार को पहले से नियोजित करने की आवश्यकता नहीं होती है क्योंकि अलग-अलग प्रोसेसर पर अलग-अलग उप-समस्याओं को निष्पादित किया जा सकता है।
+मल्टी-प्रोसेसर मशीनों, विशेष रूप से शेयर्ड-मेमोरी सिस्टम में निष्पादन के लिए विभाजन-और-जीत कलनविधि को स्वाभाविक रूप से अनुकूलित किया जाता है, जहां प्रोसेसर के बीच डेटा के संचार को पहले से नियोजित करने की आवश्यकता नहीं होती है क्योंकि विभिन्न प्रोसेसर पर विभिन्न उप-समस्याओं को निष्पादित किया जा सकता है।
 === मेमोरी एक्सेस ===
-फूट डालो और जीतो एल्गोरिदम स्वाभाविक रूप से [[मेमोरी कैश]] का कुशल उपयोग करते हैं। इसका कारण यह है कि एक बार एक उप-समस्या काफी छोटी हो जाती है, इसे और इसकी सभी उप-समस्याओं को, सिद्धांत रूप में, धीमी मुख्य मेमोरी तक पहुंच के बिना कैश के भीतर हल किया जा सकता है। इस तरह से कैश का दोहन करने के लिए डिज़ाइन किया गया एल्गोरिदम कैश-बेखबर एल्गोरिदम कहा जाता है। कैश-बेखबर, क्योंकि इसमें कैश आकार को एक स्पष्ट पैरामीटर के रूप में शामिल नहीं किया गया है।<ref name="cahob">{{cite journal | author = M. Frigo |author2=C. E. Leiserson |author3=H. Prokop | title = Cache-oblivious algorithms | journal = Proc. 40th Symp. On the Foundations of Computer Science |pages=285–297 | year = 1999|url=https://dspace.mit.edu/bitstream/handle/1721.1/80568/43558192-MIT.pdf;sequence=2|doi=10.1109/SFFCS.1999.814600 |isbn=0-7695-0409-4 |s2cid=62758836 }}</ref> इसके अलावा, डी एंड सी एल्गोरिदम को महत्वपूर्ण एल्गोरिदम (जैसे, सॉर्टिंग, एफएफटी, और मैट्रिक्स गुणन) के लिए डिज़ाइन किया जा सकता है ताकि वे इष्टतम कैश-बेखबर एल्गोरिदम हो सकें - वे कैश आकार की परवाह किए बिना एक एसिम्प्टोटिक अर्थ में कैश का उपयोग संभवतः इष्टतम तरीके से करते हैं। इसके विपरीत, कैश का दोहन करने का पारंपरिक तरीका ब्लॉकिंग है, जैसा कि [[पाश घोंसला अनुकूलन]] में होता है, जहाँ समस्या को स्पष्ट रूप से उपयुक्त आकार के टुकड़ों में विभाजित किया जाता है - यह कैश का भी बेहतर उपयोग कर सकता है, लेकिन केवल तभी जब एल्गोरिथ्म विशिष्ट के लिए ट्यून किया जाता है किसी विशेष मशीन का कैश आकार।
+विभाजन और जीत एल्गोरिदम स्वाभाविक रूप से [[मेमोरी कैश]] का कुशल उपयोग करते हैं। इसका कारण यह है कि एक बार एक उप-समस्या अधिक छोटी हो जाती है, तो इसे और इसकी सभी उप-समस्याओं को, सिद्धांत रूप में, धीमी मुख्य मेमोरी तक पहुंचे बिना कैश के भीतर हल किया जा सकता है। इस तरह से कैश का समुपयोजन करने के लिए परिकलन किया गया कलनविधि कैश-अब्लिवीअस कहा जाता है, क्योंकि इसमें कैश आकार को एक स्पष्ट मापदण्ड के रूप में सम्मिलित नहीं किया जाता है।<ref name="cahob">{{cite journal | author = M. Frigo |author2=C. E. Leiserson |author3=H. Prokop | title = Cache-oblivious algorithms | journal = Proc. 40th Symp. On the Foundations of Computer Science |pages=285–297 | year = 1999|url=https://dspace.mit.edu/bitstream/handle/1721.1/80568/43558192-MIT.pdf;sequence=2|doi=10.1109/SFFCS.1999.814600 |isbn=0-7695-0409-4 |s2cid=62758836 }}</ref> इसके अतिरिक्त, डी एंड सी कलनविधि को महत्वपूर्ण कलनविधि के लिए परिकलन किया जा सकता है (उदाहरण के लिए, सॉर्टिंग, एफएफटी, और मैट्रिक्स गुणन) इष्टतम कैश-अब्लिवीअस कलनविधि होने के लिए - वे कैश का उपयोग संभवत: इष्टतम तरीके से करते हैं, एक स्पर्शोन्मुख अर्थ में, चाहे कैचे का आकार कुछ भी हो। इसके विपरीत, कैश का समुपयोजन करने का पारंपरिक तरीका है ब्लॉकिंग (अवरोधन), जैसा कि लूप नेस्ट ऑप्टिमाइज़ेशन में होता है, जहाँ समस्या को स्पष्ट रूप से उपयुक्त आकार के टुकड़ों में विभाजित किया जाता है - यह कैश का भी इष्टतम उपयोग कर सकता है, लेकिन केवल तभी जब कलनविधि किसी विशेष मशीन के विशिष्ट कैश आकार के लिए समस्वरित किया जाता है।
-अन्य पदानुक्रमित भंडारण प्रणालियों के संबंध में समान लाभ मौजूद है, जैसे कि [[गैर-समान मेमोरी एक्सेस]] या [[आभासी मेमोरी]], साथ ही साथ कैश के कई स्तरों के लिए: एक बार उप-समस्या काफी छोटी हो जाती है, इसे दिए गए स्तर के भीतर हल किया जा सकता है पदानुक्रम, उच्च (धीमे) स्तरों तक पहुँच के बिना।
+अन्य पदानुक्रमित भंडारण प्रणालियों, जैसे [[गैर-समान मेमोरी एक्सेस]] या [[आभासी मेमोरी]], के साथ-साथ कैश के कई स्तरों के संबंध में भी यही लाभ विद्यमान है: एक बार एक उप-समस्या अधिक छोटी हो जाती है, इसे पदानुक्रम के दिए गए स्तर के अन्तर्गत उच्च (धीमे) स्तरों तक पहुँचे बिना हल किया जा सकता है।
 === राउंडऑफ नियंत्रण ===
-गोलाकार अंकगणितीय संगणनाओं में, उदा. [[तैरनेवाला स्थल]] नंबरों के साथ, एक डिवाइड-एंड-कॉनकॉर एल्गोरिथम सतही समकक्ष पुनरावृत्त विधि की तुलना में अधिक सटीक परिणाम दे सकता है। उदाहरण के लिए, एन नंबरों को या तो एक साधारण लूप द्वारा जोड़ा जा सकता है जो प्रत्येक डेटा को एक चर में जोड़ता है, या एक डी एंड सी एल्गोरिथ्म द्वारा [[जोड़ीदार योग]] कहा जाता है जो डेटा सेट को दो हिस्सों में तोड़ता है, प्रत्येक आधे के योग की पुनरावर्ती गणना करता है, और फिर जोड़ता है दो रकम। जबकि दूसरी विधि पहले की तरह समान संख्या में जोड़ करती है और पुनरावर्ती कॉल के ओवरहेड का भुगतान करती है, यह आमतौर पर अधिक सटीक होती है।<ref>Nicholas J. Higham, "[https://pdfs.semanticscholar.org/5c17/9d447a27c40a54b2bf8b1b2d6819e63c1a69.pdf The accuracy of floating-point summation]", ''SIAM J. Scientific Computing'' '''14''' (4), 783–799 (1993).</ref>
+गोलाकार अंकगणित संगणना में, उदाहरण के लिए [[तैरनेवाला स्थल|फ़्लोटिंग-पॉइंट]] संख्याओं के साथ, विभाजन-और-जीत कलनविधि सतही समकक्ष पुनरावृत्त विधि की तुलना में अधिक सटीक परिणाम दे सकता है। उदाहरण के लिए, N संख्याओं को या तो एक साधारण लूप द्वारा जोड़ा जा सकता है जो प्रत्येक डेटा को एक चर में जोड़ता है, या एक डी एंड सी कलनविधि द्वारा जिसे [[जोड़ीदार योग]] जो डेटा समुच्चय को दो हिस्सों में तोड़ता है, प्रत्येक आधे के योग की पुनरावर्ती गणना करता है, और पुनः दो योगफल को जोड़ता है। जबकि दूसरी विधि पहले की तरह समान संख्या में जोड़ करती है और पुनरावर्ती कॉल के उपरिव्यय का भुगतान करती है, यह सामान्यतः अधिक सटीक होती है।<ref>Nicholas J. Higham, "[https://pdfs.semanticscholar.org/5c17/9d447a27c40a54b2bf8b1b2d6819e63c1a69.pdf The accuracy of floating-point summation]", ''SIAM J. Scientific Computing'' '''14''' (4), 783–799 (1993).</ref>
-== कार्यान्वयन के मुद्दे ==
+== कार्यान्वयन के लिए विवाद ==
 === रिकर्सन ===
-फूट डालो और जीतो एल्गोरिदम को स्वाभाविक रूप से रिकर्सन (कंप्यूटर विज्ञान) के रूप में लागू किया जाता है। उस स्थिति में, वर्तमान में हल की जा रही आंशिक उप-समस्याओं को स्वचालित रूप से [[कॉल स्टैक]] में संग्रहीत किया जाता है। एक पुनरावर्ती कार्य एक ऐसा कार्य है जो स्वयं को अपनी परिभाषा में बुलाता है।
+विभाजन-और-जीत कलनविधि को स्वाभाविक रूप से पुनरावर्ती प्रक्रियाओं के रूप में परिपालित किया जाता है। उस स्थिति में, वर्तमान में हल की जा रही आंशिक उप-समस्याओं को प्रक्रिया [[कॉल स्टैक]] में स्वचालित रूप से संग्रहीत किया जाता है। एक पुनरावर्ती कार्य एक ऐसा कार्य है जो स्वयं को अपनी परिभाषा में आह्वान करता है।
 === स्पष्ट ढेर ===
-विभाजन और जीत एल्गोरिदम को एक गैर-पुनरावर्ती प्रोग्राम द्वारा भी कार्यान्वित किया जा सकता है जो आंशिक उप-समस्याओं को कुछ स्पष्ट डेटा संरचना, जैसे स्टैक (डेटा संरचना), [[कतार (डेटा संरचना)]], या [[प्राथमिकता कतार]] में संग्रहीत करता है। यह दृष्टिकोण उप-समस्या के चुनाव में अधिक स्वतंत्रता की अनुमति देता है जिसे अगले हल किया जाना है, एक विशेषता जो कुछ अनुप्रयोगों में महत्वपूर्ण है - उदा। इन [[चौड़ाई पहली रिकर्सन]]|ब्रेड्थ-फर्स्ट रिकर्सन और फंक्शन ऑप्टिमाइज़ेशन के लिए [[शाखा और बंधन]] मेथड। यह दृष्टिकोण प्रोग्रामिंग भाषाओं में मानक समाधान भी है जो पुनरावर्ती प्रक्रियाओं के लिए समर्थन प्रदान नहीं करता है।
+विभाजन-और-जीत कलनविधि को एक गैर-पुनरावर्ती प्रोग्राम द्वारा भी परिपालित किया जा सकता है जो आंशिक उप-समस्याओं को कुछ स्पष्ट डेटा संरचना, जैसे कि स्टैक (डेटा संरचना), [[कतार (डेटा संरचना)]], या [[प्राथमिकता कतार]] में संग्रहीत करता है। यह दृष्टिकोण उप-समस्या की पसंद में अधिक स्वतंत्रता की अनुमति देता है जिसे आगे हल किया जाना है, एक विशेषता जो कुछ अनुप्रयोगों में महत्वपूर्ण है - उदाहरण के लिए इन [[चौड़ाई पहली रिकर्सन|ब्रेड्थ-फर्स्ट पुनरावर्तन]]  में और कार्य अनुकूलन के लिए ब्रांच-एंड-बाउंड विधि। यह दृष्टिकोण क्रमादेशन भाषा में मानक समाधान भी है जो पुनरावर्ती प्रक्रियाओं के लिए समर्थन प्रदान नहीं करता है।
-=== ढेर का आकार ===
+=== स्टैक का आकार ===
-डी एंड सी एल्गोरिदम के पुनरावर्ती कार्यान्वयन में, किसी को यह सुनिश्चित करना चाहिए कि रिकर्सन स्टैक के लिए पर्याप्त मेमोरी आवंटित की गई है, अन्यथा [[स्टैक ओवरफ़्लो]] के कारण निष्पादन विफल हो सकता है। डी एंड सी एल्गोरिदम जो समय-कुशल होते हैं, अक्सर अपेक्षाकृत कम पुनरावर्तन गहराई होती है। उदाहरण के लिए, क्विकसॉर्ट एल्गोरिथम को लागू किया जा सकता है ताकि इसे कभी भी अधिक की आवश्यकता न हो <math>\log_2 n</math> क्रमबद्ध करने के लिए नेस्टेड पुनरावर्ती कॉल <math>n</math> सामान।
+डी एंड सी कलनविधि के पुनरावर्ती कार्यान्वयन में, यह सुनिश्चित करना चाहिए कि पुनरावर्तन स्टैक के लिए पर्याप्त मेमोरी आवंटित की गई है, अन्यथा [[स्टैक ओवरफ़्लो]] स्टैक ओवरफ्लो के कारण निष्पादन विफल हो सकता है। डी एंड सी कलनविधि जो समय-कुशल होते हैं, प्रायः अपेक्षाकृत कम पुनरावर्तन गहराई होती है। उदाहरण के लिए, क्विकसॉर्ट कलनविधि को परिपालित किया जा सकता है ताकि इसे कभी भी <math>n</math> वस्तुओं को क्रमबद्ध करने के लिए अधिक <math>\log_2 n</math> नीड़ बद्ध  पुनरावर्ती कॉल की आवश्यकता न हो।
-रिकर्सिव प्रक्रियाओं का उपयोग करते समय स्टैक ओवरफ्लो से बचना मुश्किल हो सकता है क्योंकि कई कंपाइलर मानते हैं कि रिकर्सन स्टैक मेमोरी का एक सन्निहित क्षेत्र है, और कुछ इसके लिए एक निश्चित मात्रा में स्थान आवंटित करते हैं। कंपाइलर पुनरावर्ती स्टैक में अधिक जानकारी भी सहेज सकते हैं, जो कड़ाई से आवश्यक है, जैसे रिटर्न एड्रेस, अपरिवर्तनीय पैरामीटर और प्रक्रिया के आंतरिक चर। इस प्रकार, रिकर्सिव प्रक्रिया के पैरामीटर और आंतरिक चर को कम करके या एक स्पष्ट स्टैक संरचना का उपयोग करके स्टैक ओवरफ़्लो का जोखिम कम किया जा सकता है।
+पुनरावर्ती प्रक्रियाओं का उपयोग करते समय स्टैक ओवरफ्लो को टालना कठिन हो सकता है क्योंकि कई संकलक मानते हैं कि रिकर्सन स्टैक मेमोरी का एक सन्निहित क्षेत्र है, और कुछ इसके लिए एक निश्चित मात्रा में स्थान आवंटित करते हैं। संकलक पुनरावर्ती स्टैक में अधिक जानकारी भी सहेज सकते हैं, जो दृढ़तः आवश्यक है, जैसे प्रतिगमन पता, अपरिवर्तनीय मापदण्ड और प्रक्रिया के आंतरिक चर। इस प्रकार, पुनरावर्ती प्रक्रिया के मापदण्ड और आंतरिक चर को कम करके या एक स्पष्ट स्टैक संरचना का उपयोग करके स्टैक ओवरफ़्लो के विपत्त‍ि को कम किया जा सकता है।
 === आधार मामलों का चयन ===
-किसी भी पुनरावर्ती एल्गोरिदम में, आधार मामलों की पसंद में काफी स्वतंत्रता होती है, छोटी उप-समस्याएं जो पुनरावर्तन को समाप्त करने के लिए सीधे हल हो जाती हैं।
+किसी भी पुनरावर्ती कलनविधि में, आधार समस्याओं की चयन में पर्याप्त स्वतंत्रता होती है, छोटी उप-समस्याएं जिन्हें पुनरावर्तन को समाप्त करने के लिए सीधे हल किया जाता है।
-सबसे छोटे या सरलतम संभावित आधार मामलों को चुनना अधिक सुरुचिपूर्ण है और आमतौर पर सरल कार्यक्रमों की ओर जाता है, क्योंकि विचार करने के लिए कम मामले होते हैं और उन्हें हल करना आसान होता है। उदाहरण के लिए, एक FFT एल्गोरिथम रिकर्सन को रोक सकता है जब इनपुट एक नमूना होता है, और क्विकॉर्ट लिस्ट-सॉर्टिंग एल्गोरिथम तब रुक सकता है जब इनपुट खाली सूची हो; दोनों उदाहरणों में, विचार करने के लिए केवल एक आधार मामला है, और इसके लिए किसी प्रसंस्करण की आवश्यकता नहीं है।
+सबसे छोटे या सरलतम संभावित आधार समस्याओं को चुनना अधिक सुरुचिपूर्ण है और सामान्यतः सरल कार्यक्रमों की ओर जाता है, क्योंकि विचार करने के लिए कम समस्याएं होते हैं और उन्हें हल करना आसान होता है। उदाहरण के लिए, एक एफ एफ टी कलनविधि पुनरावर्तन को रोक सकता है जब इनपुट एक एकल नमूना होता है, और क्विकसॉर्ट लिस्ट-सॉर्टिंग कलनविधि तब रुक सकता है जब इनपुट रिक्त सूची हो; दोनों उदाहरणों में, विचार करने के लिए केवल एक आधार समस्या है, और इसके लिए किसी प्रसंस्करण की आवश्यकता नहीं है।
-दूसरी ओर, दक्षता में अक्सर सुधार होता है यदि अपेक्षाकृत बड़े आधार मामलों में पुनरावर्तन को रोक दिया जाता है, और इन्हें गैर-पुनरावर्ती रूप से हल किया जाता है, जिसके परिणामस्वरूप एक [[हाइब्रिड एल्गोरिदम]] होता है। यह रणनीति पुनरावर्ती कॉल के ओवरहेड से बचाती है जो बहुत कम या कोई काम नहीं करती है और विशेष गैर-पुनरावर्ती एल्गोरिदम के उपयोग की अनुमति भी दे सकती है, जो उन आधार मामलों के लिए स्पष्ट पुनरावर्तन से अधिक कुशल हैं। सरल हाइब्रिड पुनरावर्ती एल्गोरिथम के लिए एक सामान्य प्रक्रिया बेस केस को शॉर्ट-सर्किट करना है, जिसे आर्म्स-लेंथ रिकर्सन के रूप में भी जाना जाता है। इस मामले में, क्या अगले चरण का परिणाम होगा कि अनावश्यक फ़ंक्शन कॉल से बचने के लिए फ़ंक्शन कॉल से पहले बेस केस की जाँच की जाती है। उदाहरण के लिए, एक पेड़ में, एक बच्चे के नोड की पुनरावृत्ति करने के बजाय और फिर जाँच करें कि क्या यह अशक्त है, पुनरावर्ती से पहले अशक्त जाँच; बाइनरी ट्री पर कुछ एल्गोरिदम में आधे फ़ंक्शन कॉल से बचा जाता है। चूंकि एक डी एंड सी एल्गोरिदम अंततः प्रत्येक समस्या या उप-समस्या उदाहरण को बड़ी संख्या में आधार उदाहरणों में कम कर देता है, ये अक्सर एल्गोरिदम की समग्र लागत पर हावी होते हैं, खासकर जब विभाजन/उपरि में शामिल होना कम होता है। ध्यान दें कि ये विचार इस बात पर निर्भर नहीं करते हैं कि संकलक द्वारा या एक स्पष्ट स्टैक द्वारा पुनरावर्तन लागू किया गया है या नहीं।
+दूसरी ओर, दक्षता में प्रायः सुधार होता है यदि अपेक्षाकृत बड़े आधार समस्याओं में पुनरावर्तन को रोक दिया जाता है, और इन्हें गैर-पुनरावर्ती रूप से हल किया जाता है, जिसके परिणामस्वरूप एक [[हाइब्रिड एल्गोरिदम|हाइब्रिड कलनविधि]] होता है। यह रणनीति पुनरावर्ती कॉल के उपरिव्यय से बचाती है जो बहुत कम या कोई काम नहीं करती है और विशेष गैर-पुनरावर्ती कलनविधि के उपयोग की अनुमति भी दे सकती है, जो उन आधार समस्याओं के लिए, स्पष्ट पुनरावर्तन से अधिक कुशल हैं। सरल हाइब्रिड पुनरावर्ती कलनविधि के लिए आधार समस्या का शॉर्ट-सर्किट करना एक सामान्य प्रक्रिया है , जिसे आर्म्स-लेंथ पुनरावर्तन के रूप में भी जाना जाता है। इस समस्या में,फ़ंक्शन कॉल से पहले, एक अनावश्यक फ़ंक्शन कॉल को टालकर, आधार समस्या में अगले चरण का परिणाम क्या होगा वह जाँच की जाती है। उदाहरण के लिए, एक पेड़ में, एक शिशु आसंधि की पुनरावृत्ति करने के अलावा और फिर जाँच करें कि क्या यह अशक्त है, पुनरावर्ती से पहले अशक्त जाँच करना; बाइनरी ट्री पर कुछ कलनविधि में आधे फ़ंक्शन कॉल को टालता है। चूंकि डी एंड सी कलनविधि अंततः प्रत्येक समस्या या उप-समस्या अवस्था को बड़ी संख्या में आधार अवस्थाओं में कम कर देता है, ये प्रायः कलनविधि की समग्र लागत पर हावी होते हैं, विशेष रूप से जब विभाजन/उपरिव्यय मिलन कम होता है। ध्यान दें कि ये विचार इस बात पर निर्भर नहीं करते हैं कि संकलक द्वारा या एक स्पष्ट स्टैक द्वारा पुनरावर्तन परिपालित किया गया है या नहीं।
-इस प्रकार, उदाहरण के लिए, सॉर्ट किए जाने वाले आइटमों की संख्या पर्याप्त रूप से कम होने के बाद, क्विकसॉर्ट के कई लाइब्रेरी कार्यान्वयन सरल लूप-आधारित [[सम्मिलन सॉर्ट]] (या समान) एल्गोरिथम पर स्विच हो जाएंगे। ध्यान दें कि, यदि खाली सूची एकमात्र आधार मामला था, तो सूची को क्रमबद्ध करना <math>n</math> प्रविष्टियां अधिकतम रूप से आवश्यक होंगी <math>n</math> क्विकॉर्ट कॉल जो कुछ नहीं करेगी लेकिन तुरंत वापस आ जाएगी। आधार मामलों को आकार 2 या उससे कम की सूचियों में बढ़ाने से उनमें से अधिकतर कुछ भी नहीं करने वाले कॉल समाप्त हो जाएंगे, और आम तौर पर 2 से बड़ा आधार मामला आमतौर पर फ़ंक्शन-कॉल ओवरहेड या स्टैक मैनिपुलेशन में बिताए गए समय के अंश को कम करने के लिए उपयोग किया जाता है।
+इस प्रकार, उदाहरण के लिए, क्रमबद्ध किए जाने वाले वस्तुओं की संख्या पर्याप्त रूप से कम होने के बाद, क्विकसॉर्ट के कई लाइब्रेरी कार्यान्वयन सरल लूप-आधारित [[सम्मिलन सॉर्ट]] (या समान) कलनविधि पर परिवर्तित हो जाएंगे। ध्यान दें कि, यदि अपूरित सूची एकमात्र आधार समस्या था, तो सूची को <math>n</math> प्रविष्टियों में क्रमबद्ध करने पर  अधिकतम रूप से <math>n</math> क्विकसॉर्ट कॉल प्रवेश होंगी जो कुछ नहीं करेगी लेकिन तुरंत वापस आ जाएगी। आधार समस्याओं को आकार 2 या उससे कम की सूचियों में बढ़ाने से उनमें से अधिकतर अप्रचालन अनुदेश कॉल समाप्त हो जाएंगे, और सामान्यतः 2 से बड़ा आधार समस्या विशिष्ट रूप से  फ़ंक्शन-कॉल उपरिव्यय या स्टैक परिचालन में बिताए गए समय के अंश को कम करने के लिए उपयोग किया जाता है।
-वैकल्पिक रूप से, कोई भी बड़े आधार मामलों को नियोजित कर सकता है जो अभी भी एक विभाजन और जीत एल्गोरिथ्म का उपयोग करते हैं, लेकिन निश्चित आकारों के पूर्व निर्धारित सेट के लिए एल्गोरिथ्म को लागू करते हैं जहां एल्गोरिथ्म पूरी तरह से [[लूप खोलना]] कोड में हो सकता है जिसमें कोई पुनरावर्तन, लूप या [[सशर्त (प्रोग्रामिंग)]] नहीं है। ) ([[आंशिक मूल्यांकन]] की तकनीक से संबंधित)। उदाहरण के लिए, इस दृष्टिकोण का उपयोग कुछ कुशल एफएफटी कार्यान्वयनों में किया जाता है, जहां आधार मामले निश्चित आकार के सेट के लिए डिवाइड-एंड-कॉनकेयर एफएफटी एल्गोरिदम के अनियंत्रित कार्यान्वयन होते हैं।<ref name="fftw">{{cite journal | author = Frigo, M. |author2=Johnson, S. G. | url = http://www.fftw.org/fftw-paper-ieee.pdf | title = The design and implementation of FFTW3 | journal = Proceedings of the IEEE | volume = 93 | issue = 2 |date=February 2005 | pages = 216–231 | doi = 10.1109/JPROC.2004.840301|citeseerx=10.1.1.66.3097 |s2cid=6644892 }}</ref> इस रणनीति को कुशलतापूर्वक लागू करने के लिए वांछित अलग-अलग आधार मामलों की बड़ी संख्या का उत्पादन करने के लिए [[स्रोत-कोड पीढ़ी]] विधियों का उपयोग किया जा सकता है।<ref name="fftw"/>
+वैकल्पिक रूप से, कोई भी बड़े आधार समस्याओं को नियोजित कर सकता है जो अभी भी विभाजन-और-जीत कलनविधि का उपयोग करते हैं, लेकिन निश्चित आकारों के पूर्व निर्धारित समुच्चय के लिए कलनविधि परिपालन करते हैं जहां कलनविधि पूरी तरह से कोड में अनियंत्रित हो सकता है जिसमें कोई पुनरावर्तन, लूप या [[सशर्त (प्रोग्रामिंग)]] नहीं है। इस रणनीति को कुशलतापूर्वक परिपालन करने के लिए वांछित विभिन्न आधार समस्याओं की बड़ी संख्या का उत्पादन करने के लिए स्रोत-कोड जनरेशन विधियों का उपयोग किया जा सकता है।
+इस विचार के सामान्यीकृत संस्करण को पुनरावर्तन "अनरोलिंग" या "कोर्सनिंग" के रूप में जाना जाता है, और आधार समस्याओं को बढ़ाने की प्रक्रिया को स्वचालित करने के लिए विभिन्न तकनीकों का प्रस्ताव किया गया है।<ref name="fftw">{{cite journal | author = Frigo, M. |author2=Johnson, S. G. | url = http://www.fftw.org/fftw-paper-ieee.pdf | title = The design and implementation of FFTW3 | journal = Proceedings of the IEEE | volume = 93 | issue = 2 |date=February 2005 | pages = 216–231 | doi = 10.1109/JPROC.2004.840301|citeseerx=10.1.1.66.3097 |s2cid=6644892 }}</ref>
 इस विचार के सामान्यीकृत संस्करण को रिकर्सन अनोलिंग या मोटे होने के रूप में जाना जाता है, और आधार मामले को बढ़ाने की प्रक्रिया को स्वचालित करने के लिए विभिन्न तकनीकों का प्रस्ताव दिया गया है।<ref>Radu Rugina and Martin Rinard, "[http://people.csail.mit.edu/rinard/paper/lcpc00.pdf Recursion unrolling for divide and conquer programs]" in ''Languages and Compilers for Parallel Computing'', chapter 3, pp. 34–48.  ''Lecture Notes in Computer Science'' vol. 2017 (Berlin: Springer, 2001).</ref>
-=== अतिव्यापी उप-समस्याओं के लिए [[गतिशील प्रोग्रामिंग]] ===
+=== अतिव्यापी उप-समस्याओं के लिए गतिशील प्रोग्रामिंग ===
-कुछ समस्याओं के लिए, शाखित पुनरावृत्ति एक ही उप-समस्या का कई बार मूल्यांकन कर सकती है। ऐसे मामलों में इन अतिव्यापी उपसमस्याओं के समाधानों को पहचानने और सहेजने के लायक हो सकता है, एक तकनीक को आमतौर पर ज्ञापन के रूप में जाना जाता है। सीमा तक अनुसरण करने पर, यह [[नीचे-ऊपर डिजाइन]] | बॉटम-अप डिवाइड-एंड-कॉनकॉर एल्गोरिदम जैसे डायनेमिक प्रोग्रामिंग की ओर जाता है।
+कुछ समस्याओं के लिए, शाखित पुनरावृत्ति एक ही उप-समस्या का कई बार मूल्यांकन कर सकती है। ऐसे समस्याओं में इन अतिव्यापी उपसमस्याओं के समाधानों को पहचानने और सुरक्षित रखने के योग्य हो सकता है, एक तकनीक जो सामान्यतः ज्ञापन के रूप में जाना जाता है। एक सीमा तक इसका पालन किया जाता है, यह डायनेमिक प्रोग्रामिंग जैसे बॉटम-अप विभाजन-और-जीत कलनविधि की ओर जाता है ।
 == यह भी देखें ==
-{{Commons category|Divide-and-conquer algorithms}}
 * एकरा–बाजी विधि
-* [[विघटित एकत्रीकरण समारोह]]
+* [[विघटित एकत्रीकरण समारोह|विघटित एकत्रीकरण क्रिया]]
 * फोर्क-जॉइन मॉडल
 * [[मास्टर प्रमेय (एल्गोरिदम का विश्लेषण)]]
 * गणितीय प्रेरण
 * [[मानचित्र छोटा करना]]
-* [[अनुमानी (कंप्यूटर विज्ञान)]]
+* [[अनुमानी (कंप्यूटर विज्ञान)|अन्वेषणात्मक (कंप्यूटर विज्ञान)]]
 == संदर्भ ==
-{{Reflist}}{{Algorithmic paradigms}}
+{{Reflist}}{{Authority control}}
-{{Authority control}}
-{{DEFAULTSORT:Divide And Conquer Algorithm}}[[Category: फूट डालो और जीतो एल्गोरिदम | फूट डालो और जीतो एल्गोरिदम ]] [[Category: एल्गोरिदम]] [[Category: अनुकूलन एल्गोरिदम और तरीके]]
+{{DEFAULTSORT:Divide And Conquer Algorithm}}
-[[Category: Machine Translated Page]]
+[[Category:All articles needing examples|Divide And Conquer Algorithm]]
-[[Category:Created On 13/02/2023]]
+[[Category:Articles needing examples from October 2017|Divide And Conquer Algorithm]]
+[[Category:Articles with invalid date parameter in template|Divide And Conquer Algorithm]]
+[[Category:Created On 13/02/2023|Divide And Conquer Algorithm]]
+[[Category:Lua-based templates|Divide And Conquer Algorithm]]
+[[Category:Machine Translated Page|Divide And Conquer Algorithm]]
+[[Category:Pages with script errors|Divide And Conquer Algorithm]]
+[[Category:Short description with empty Wikidata description|Divide And Conquer Algorithm]]
+[[Category:Templates Vigyan Ready|Divide And Conquer Algorithm]]
+[[Category:Templates that add a tracking category|Divide And Conquer Algorithm]]
+[[Category:Templates that generate short descriptions|Divide And Conquer Algorithm]]
+[[Category:Templates using TemplateData|Divide And Conquer Algorithm]]
+[[Category:अनुकूलन एल्गोरिदम और तरीके|Divide And Conquer Algorithm]]
+[[Category:एल्गोरिदम|Divide And Conquer Algorithm]]
+[[Category:फूट डालो और जीतो एल्गोरिदम| फूट डालो और जीतो एल्गोरिदम ]]

Anonymous

Search

विभाजन और जीत कलनविधि (डिवाइड एंड कॉन्कर): Difference between revisions

Namespaces

More

Page actions

Latest revision as of 10:33, 24 February 2023

Contents

फूट डालो और राज करो

प्रारंभिक ऐतिहासिक उदाहरण