विभाजन-और-कन्कर एल्गोरिथ्म: Difference between revisions

Latest revision as of 09:18, 28 June 2023

इस प्रकार के कंप्यूटर विज्ञान में विभाजित करें और विजय एल्गोरिथ्म डिजाइन प्रतिमान है। डिवाइड-एंड-कॉनकोर एल्गोरिदम रिकर्सन (कंप्यूटर विज्ञान) समस्या को ही या संबंधित प्रकार की दो या दो से अधिक उप-समस्याओं में तोड़ देता है। जब तक कि ये सीधे हल करने के लिए पर्याप्त सरल न हो जाएं उप-समस्याओं के समाधान को तब मूल समस्या का समाधान देने के लिए संयोजित किया जाता है।

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

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

विभाजन और विजय

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

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

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

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

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

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

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

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

प्रारंभिक दो-उप-समस्या डी एंड सी एल्गोरिथ्म जो विशेष रूप से कंप्यूटरों के लिए विकसित किया गया था और ठीक से विश्लेषण किया गया था मर्ज सॉर्ट एल्गोरिथ्म है जिसका आविष्कार जॉन वॉन न्यूमैन ने 1945 में किया था।^[7]

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

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

लाभ

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

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

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

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

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

समानता

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

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

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

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

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

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

कार्यान्वयन के उदेश समुच्चय

रिकर्सन

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

स्पष्ट ढेर

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

ढेर का आकार

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

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

आधार स्थितियों का चयन

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

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

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

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

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

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

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

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

यह भी देखें

संदर्भ

↑ Blahut, Richard (14 May 2014). सिग्नल प्रोसेसिंग के लिए फास्ट एल्गोरिदम. 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). एल्गोरिदम का परिचय. 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). "कैश-बेखबर एल्गोरिदम". 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).
↑ ^11.0 ^11.1 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). सिग्नल प्रोसेसिंग के लिए फास्ट एल्गोरिदम. 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). एल्गोरिदम का परिचय. 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). "कैश-बेखबर एल्गोरिदम". 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] 11.0 ^11.1 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 1: / Line 1: @@
 {{Short description|Algorithms which recursively solve subproblems}}
-[[कंप्यूटर विज्ञान]] में, फूट डालो और जीतो [[एल्गोरिथ्म डिजाइन प्रतिमान]] है। डिवाइड-एंड-कॉनकोर एल्गोरिदम [[ रिकर्सन (कंप्यूटर विज्ञान) |रिकर्सन (कंप्यूटर विज्ञान)]]  समस्या को ही या संबंधित प्रकार की दो या दो से अधिक उप-समस्याओं में तोड़ देता है, जब तक कि ये सीधे हल करने के लिए पर्याप्त सरल न हो जाएं। उप-समस्याओं के समाधान को तब मूल समस्या का समाधान देने के लिए संयोजित किया जाता है।
+इस प्रकार के [[कंप्यूटर विज्ञान]] में विभाजित करें और विजय [[एल्गोरिथ्म डिजाइन प्रतिमान]] है। डिवाइड-एंड-कॉनकोर एल्गोरिदम [[ रिकर्सन (कंप्यूटर विज्ञान) |रिकर्सन (कंप्यूटर विज्ञान)]] समस्या को ही या संबंधित प्रकार की दो या दो से अधिक उप-समस्याओं में तोड़ देता है। जब तक कि ये सीधे हल करने के लिए पर्याप्त सरल न हो जाएं उप-समस्याओं के समाधान को तब मूल समस्या का समाधान देने के लिए संयोजित किया जाता है।
-विभाजन और जीत तकनीक कई समस्याओं के लिए कुशल एल्गोरिदम का आधार है, जैसे [[छँटाई एल्गोरिथ्म]] (उदाहरण के लिए, त्वरित सॉर्ट, [[ मर्ज़ सॉर्ट |मर्ज़ सॉर्ट]] ), गुणन एल्गोरिदम (उदाहरण के लिए, [[करत्सुबा [[ कलन विधि |कलन विधि]] ]]), अंक समस्या की निकटतम जोड़ी ढूंढना, वाक्य रचनात्मक विश्लेषण (उदाहरण के लिए, [[टॉप-डाउन पार्सर]]्स), और असतत फूरियर ट्रांसफॉर्म ([[[[असतत फूरियर रूपांतरण]]]]) की गणना करना।<ref>{{cite book |last1=Blahut |first1=Richard |title=सिग्नल प्रोसेसिंग के लिए फास्ट एल्गोरिदम|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=सिग्नल प्रोसेसिंग के लिए फास्ट एल्गोरिदम|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) को क्रमबद्ध करने के लिए फूट डालो और जीतो दृष्टिकोण। ऊपरी आधा: सब्लिस्ट्स में विभाजन; मध्य: -तत्व सूची तुच्छ रूप से क्रमबद्ध है; निचला आधा: सॉर्ट किए गए सबलिस्ट्स की रचना।]]फूट डालो और जीतो प्रतिमान का उपयोग अक्सर किसी समस्या का इष्टतम समाधान खोजने के लिए किया जाता है। इसका मूल विचार दी गई समस्या को दो या अधिक समान, लेकिन सरल, उप-समस्याओं में विघटित करना है, उन्हें बारी-बारी से हल करना और दी गई समस्या को हल करने के लिए उनके समाधानों की रचना करना है। पर्याप्त सरलता की समस्याएं सीधे हल हो जाती हैं।
-उदाहरण के लिए, n प्राकृतिक संख्याओं की दी गई सूची को क्रमबद्ध करने के लिए, इसे लगभग n/2 संख्याओं की दो सूचियों में विभाजित करें, उनमें से प्रत्येक को बारी-बारी से क्रमबद्ध करें, और दी गई सूची का क्रमबद्ध संस्करण प्राप्त करने के लिए दोनों परिणामों को उचित रूप से इंटरलीव करें (देखें) चित्र)। इस दृष्टिकोण को मर्ज सॉर्ट एल्गोरिथम के रूप में जाना जाता है।
-विभाजित करें और जीतें नाम को कभी-कभी एल्गोरिदम पर लागू किया जाता है जो प्रत्येक समस्या को केवल उप-समस्या तक कम कर देता है, जैसे बाइनरी खोज एल्गोरिदम क्रमबद्ध सूची में रिकॉर्ड खोजने के लिए (या संख्यात्मक एल्गोरिदम में इसका एनालॉग, रूट-खोज के लिए द्विभाजन एल्गोरिदम) कलन विधि)।<ref name="CormenLeiserson2009">{{cite book|author1=Thomas H. Cormen|author2=Charles E. Leiserson|author3=Ronald L. Rivest|author4=Clifford Stein|title=एल्गोरिदम का परिचय|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>
+== विभाजन और विजय ==
-फूट डालो और जीतो का महत्वपूर्ण अनुप्रयोग अनुकूलन में है, जहां यदि प्रत्येक चरण में स्थिर कारक द्वारा खोज स्थान को कम (छंटनी) किया जाता है, तो समग्र एल्गोरिथ्म में प्रूनिंग चरण के समान विषम जटिलता होती है, जिसमें प्रूनिंग कारक (ज्यामितीय श्रृंखला को जोड़कर) पर निर्भर करता है; इसे [[छँटाई और खोज]] के रूप में जाना जाता है।
+[[File:Merge sort algorithm diagram.svg|thumb|बढ़ते क्रम में सूची (38, 27, 43, 3, 9, 82, 10) को क्रमबद्ध करने के लिए विभाजित करें और विजय दृष्टिकोण। ऊपरी आधा: सब्लिस्ट्स में विभाजन; मध्य: -तत्व सूची सामान्य रूप से क्रमबद्ध है; निचला आधा: सॉर्ट किए गए सबलिस्ट्स की रचना।]]'''विभाजन और विजय''' प्रतिमान का उपयोग अधिकांशतः किसी समस्या का इष्टतम समाधान खोजने के लिए किया जाता है। इसका मूल विचार दी गई समस्या को दो या अधिक समान किन्तु सरल उप-समस्याओं में विघटित करना है उन्हें बारी-बारी से हल करना और दी गई समस्या को हल करने के लिए उनके समाधानों की रचना करना है। पर्याप्त सरलता की समस्याएं सीधे हल हो जाती हैं।उदाहरण के लिए n प्राकृतिक संख्याओं की दी गई सूची को क्रमबद्ध करने के लिए, इसे लगभग n/2 संख्याओं की दो सूचियों में विभाजित करें, उनमें से प्रत्येक को बारी-बारी से क्रमबद्ध करें और दी गई सूची का क्रमबद्ध संस्करण प्राप्त करने के लिए दोनों परिणामों को उचित रूप से इंटरलीव करें (देखें) चित्र)। इस दृष्टिकोण को मर्ज सॉर्ट एल्गोरिथम के रूप में जाना जाता है।
+विभाजित करें और विजय नाम को कभी-कभी एल्गोरिदम पर प्रयुक्त किया जाता है जो प्रत्येक समस्या को केवल उप-समस्या तक कम कर देता है जैसे की बाइनरी की खोज एल्गोरिदम क्रमबद्ध सूची में रिकॉर्ड खोजने के लिए (या संख्यात्मक एल्गोरिदम में इसका एनालॉग रूट-खोज के लिए द्विभाजन एल्गोरिदम कलन विधि है।)<ref name="CormenLeiserson2009">{{cite book|author1=Thomas H. Cormen|author2=Charles E. Leiserson|author3=Ronald L. Rivest|author4=Clifford Stein|title=एल्गोरिदम का परिचय|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>
+विभाजित करें और विजय का महत्वपूर्ण अनुप्रयोग अनुकूलन में है जहां यदि प्रत्येक चरण में स्थिर कारक द्वारा खोज स्थान को कम (प्रुनेद) किया जाता है तो समग्र एल्गोरिथ्म में प्रूनिंग चरण के समान विषम जटिलता होती है जिसमें प्रूनिंग कारक (ज्यामितीय श्रृंखला को जोड़कर) पर निर्भर करता है इसे [[छँटाई और खोज|प्रुनेद और खोज]] के रूप में जाना जाता है।
 == प्रारंभिक ऐतिहासिक उदाहरण ==
-इन एल्गोरिदम के शुरुआती उदाहरण मुख्य रूप से घटते हैं और जीतते हैं - मूल समस्या क्रमिक रूप से एकल उप-समस्याओं में टूट जाती है, और वास्तव में इसे पुनरावृत्त रूप से हल किया जा सकता है।
+इन एल्गोरिदम के प्रारंभिक उदाहरण मुख्य रूप से घटते हैं और जीतते हैं - मूल समस्या क्रमिक रूप से एकल उप-समस्याओं में टूट जाती है और वास्तव में इसे पुनरावृत्त रूप से हल किया जा सकता है।
+बाइनरी खोज कमी-और-विजय एल्गोरिथ्म जहां उप-समस्याएं लगभग आधे मूल आकार की होती हैं और इसका लम्बे समय तक इतिहास रहा है। जबकि कंप्यूटर पर एल्गोरिथ्म का स्पष्ट विवरण 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> चूंकि उन्होंने मात्रात्मक रूप से [[एल्गोरिदम का विश्लेषण]] नहीं किया और एफएफटी तब तक व्यापक नहीं हुए जब तक कि उन्हें एक सदी बाद फिर से खोजा नहीं गयाथा।
-बाइनरी खोज, कमी-और-जीत एल्गोरिथ्म जहां उप-समस्याएं लगभग आधे मूल आकार की होती हैं, का लंबा इतिहास रहा है। जबकि कंप्यूटर पर एल्गोरिथ्म का स्पष्ट विवरण 1946 में [[जॉन मौचली]] के लेख में दिखाई दिया, खोज की सुविधा के लिए वस्तुओं की क्रमबद्ध सूची का उपयोग करने का विचार कम से कम 200 ईसा पूर्व [[ बेबिलोनिया |बेबिलोनिया]] तक था।<ref name=Knuth3/> अन्य प्राचीन कमी-और-जीत एल्गोरिथ्म [[यूक्लिडियन एल्गोरिथ्म]] है जो संख्याओं को छोटे और छोटे समतुल्य उपसमस्याओं में घटाकर दो संख्याओं के सबसे बड़े सामान्य विभाजक की गणना करता है, जो कई शताब्दियों ईसा पूर्व की है।
+प्रारंभिक दो-उप-समस्या डी एंड सी एल्गोरिथ्म जो विशेष रूप से कंप्यूटरों के लिए विकसित किया गया था और ठीक से विश्लेषण किया गया था मर्ज सॉर्ट एल्गोरिथ्म है जिसका आविष्कार [[जॉन वॉन न्यूमैन]] ने 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>
-कई उप-समस्याओं के साथ विभाजित और जीत एल्गोरिथ्म का प्रारंभिक उदाहरण [[कार्ल फ्रेडरिक गॉस]] का 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> हालांकि उन्होंने मात्रात्मक रूप से [[एल्गोरिदम का विश्लेषण]] नहीं किया, और एफएफटी तब तक व्यापक नहीं हुए जब तक कि उन्हें सदी बाद फिर से खोजा नहीं गया।
+अन्य उल्लेखनीय उदाहरण 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> जो <math>O(n^{\log_2 3})</math> संचालन ([[बिग ओ नोटेशन]] में) दो n-अंकीय संख्याओं का गुणा कर सकता है। इस एल्गोरिथ्म ने [[एंड्री कोलमोगोरोव]] के 1956 के अनुमान को खारिज कर दिया की उस कार्य के लिए <math>\Omega(n^2)</math> संचालन की आवश्यकता होती है।
-प्रारंभिक दो-उप-समस्या डी एंड सी एल्गोरिथ्म जो विशेष रूप से कंप्यूटरों के लिए विकसित किया गया था और ठीक से विश्लेषण किया गया था, मर्ज सॉर्ट एल्गोरिथ्म है, जिसका आविष्कार [[जॉन वॉन न्यूमैन]] ने 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>
+विभाजित करें और विजय एल्गोरिद्म के अन्य उदाहरण के रूप में जिसमें मूल रूप से कंप्यूटर सम्मिलित नहीं थे [[डोनाल्ड नुथ]] उस विधि को देते हैं जो डाकघर सामान्यतः मेल को रूट करने के लिए उपयोग करता है: पत्रों को अलग-अलग भौगोलिक क्षेत्रों के लिए अलग-अलग बैग में सॉर्ट किया जाता है इनमें से प्रत्येक बैग को स्वयं प्रथक किया जाता है। छोटे उप-क्षेत्रों के लिए बैचों में, और इसी तरह जब तक वे वितरित नहीं होते हैं।<ref name="Knuth3">Donald E. Knuth, ''The Art of Computer Programming: Volume 3, Sorting and Searching'', second edition (Addison-Wesley, 1998).</ref> यह [[ आपको कामयाबी मिले |आपको कामयाबी मिले]] से संबंधित है जिसका वर्णन आईबीएम 80 सीरीज़ कार्ड सॉर्टर्स है। पंच-कार्ड सॉर्टिंग मशीनों के लिए 1929 की प्रारंभ में किया गया था।<ref name="Knuth3" />
-अन्य उल्लेखनीय उदाहरण 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 28: / Line 31: @@
 === कठिन समस्याओं का समाधान ===
-फूट डालो और जीतो अवधारणात्मक रूप से कठिन समस्याओं को हल करने के लिए शक्तिशाली उपकरण है: इसके लिए केवल समस्या को उप-समस्याओं में तोड़ने, तुच्छ मामलों को हल करने और उप-समस्याओं को मूल समस्या से जोड़ने का तरीका है। इसी तरह, घटाना और जीतना केवल समस्या को छोटी समस्या में कम करने की आवश्यकता है, जैसे हनोई पहेली का क्लासिक टॉवर, जो ऊंचाई के टावर को कम कर देता है <math>n</math> ऊंचाई के टॉवर को स्थानांतरित करने के लिए <math>n-1</math>.
+विभाजित करें और विजय अवधारणात्मक रूप से कठिन समस्याओं को हल करने के लिए एक शक्तिशाली उपकरण है: इसके लिए केवल समस्या को उप-समस्याओं में तोड़ने,सामान्य स्थितियों को हल करने और उप-समस्याओं को मूल समस्या से जोड़ने का एक विधि है। इसी तरह, कमी और जीत के लिए केवल एक छोटी समस्या को कम करने की आवश्यकता होती है जैसे कि हनोई पहेली का क्लासिक टॉवर जो ऊंचाई के टॉवर <math>n-1</math> को स्थानांतरित करने के लिए ऊंचाई के टॉवर <math>n</math> को कम करता है।
 === एल्गोरिथम दक्षता ===
-फूट डालो और जीतो प्रतिमान अक्सर कुशल एल्गोरिदम की खोज में मदद करता है। यह कुंजी थी, उदाहरण के लिए, करात्सुबा की तेजी से गुणन विधि, क्विकसॉर्ट और मर्जसॉर्ट एल्गोरिदम, मैट्रिक्स गुणन के लिए [[सड़क एल्गोरिथ्म]], और तेजी से फूरियर रूपांतरण।
+विभाजित करें और विजय प्रतिमान अधिकांशतः कुशल एल्गोरिदम की खोज में सहायता करता है। यह कुंजी थी उदाहरण के लिए करात्सुबा की तेजी से गुणन विधि क्विकसॉर्ट और मर्जसॉर्ट एल्गोरिदम आव्युह गुणन के लिए [[सड़क एल्गोरिथ्म]] और तेजी से फूरियर रूपांतरण है।
-इन सभी उदाहरणों में, डी एंड सी दृष्टिकोण ने समाधान की उपगामी जटिलता में सुधार किया। उदाहरण के लिए, यदि (ए) रिकर्सन (कंप्यूटर विज्ञान) का आकार स्थिर है, तो समस्या को विभाजित करने और आंशिक समाधानों के संयोजन का कार्य समस्या के आकार के समानुपाती होता है <math>n</math>, और (बी) परिबद्ध संख्या है <math>p</math> आकार की उप-समस्याओं की ~ <math>n/p</math> प्रत्येक चरण में, तब फूट डालो और जीतो एल्गोरिथम की लागत होगी <math>O(n\log_{p}n)</math>.
+इन सभी उदाहरणों में, डी एंड सी दृष्टिकोण ने समाधान की उपगामी निवेश में सुधार किया। और उदाहरण के लिए, यदि (ए) आधार स्थियो में निरंतर-सीमित आकार है तो समस्या को विभाजित करने और आंशिक समाधानों के संयोजन का कार्य समस्या के आकार <math>n</math> के समानुपाती होता है और (बी) की उप-समस्याओं की एक परिबद्ध संख्या <math>p</math> होती है आकार ~ n/p प्रत्येक चरण में तब डिवाइड-एंड-कॉनकॉर एल्गोरिथ्म की निवेश <math>O(n\log_{p}n)</math> होती है |
 === समानता ===
-मल्टी-प्रोसेसर मशीनों, विशेष रूप से साझा-मेमोरी सिस्टम में निष्पादन के लिए विभाजित और जीत एल्गोरिदम स्वाभाविक रूप से अनुकूलित होते हैं, जहां प्रोसेसर के बीच डेटा के संचार को पहले से नियोजित करने की आवश्यकता नहीं होती है क्योंकि अलग-अलग प्रोसेसर पर अलग-अलग उप-समस्याओं को निष्पादित किया जा सकता है।
+मल्टी-प्रोसेसर मशीनों, विशेष रूप से साझा-मेमोरी प्रणाली में निष्पादन के लिए विभाजित और विजय एल्गोरिदम स्वाभाविक रूप से अनुकूलित होते हैं जहां प्रोसेसर के बीच डेटा के संचार को पहले से नियोजित करने की आवश्यकता नहीं होती है क्योंकि अलग-अलग प्रोसेसर पर अलग-अलग उप-समस्याओं को निष्पादित किया जा सकता है।
 === मेमोरी एक्सेस ===
-फूट डालो और जीतो एल्गोरिदम स्वाभाविक रूप से [[मेमोरी कैश]] का कुशल उपयोग करते हैं। इसका कारण यह है कि बार उप-समस्या काफी छोटी हो जाती है, इसे और इसकी सभी उप-समस्याओं को, सिद्धांत रूप में, धीमी मुख्य मेमोरी तक पहुंच के बिना कैश के भीतर हल किया जा सकता है। इस तरह से कैश का दोहन करने के लिए डिज़ाइन किया गया एल्गोरिदम कैश-बेखबर एल्गोरिदम कहा जाता है। कैश-बेखबर, क्योंकि इसमें कैश आकार को स्पष्ट पैरामीटर के रूप में शामिल नहीं किया गया है।<ref name="cahob">{{cite journal | author = M. Frigo |author2=C. E. Leiserson |author3=H. Prokop | title = कैश-बेखबर एल्गोरिदम| 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 = कैश-बेखबर एल्गोरिदम| 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>\log_2 n</math> आइटमों को सॉर्ट <math>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 name="fftw"/>
-इस विचार के सामान्यीकृत संस्करण को रिकर्सन अनोलिंग या मोटे होने के रूप में जाना जाता है, और आधार मामले को बढ़ाने की प्रक्रिया को स्वचालित करने के लिए विभिन्न तकनीकों का प्रस्ताव दिया गया है।<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>
+इस विचार के सामान्यीकृत संस्करण को रिकर्सन अनरोलिंग या मोटे होने के रूप में जाना जाता है और आधार स्थितियों को बढ़ाने की प्रक्रिया को स्वचालित करने के लिए विभिन्न तकनीकों का प्रस्ताव दिया गया है।<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>
 === अतिव्यापी उप-समस्याओं के लिए [[गतिशील प्रोग्रामिंग]] ===
-कुछ समस्याओं के लिए, शाखित पुनरावृत्ति ही उप-समस्या का कई बार मूल्यांकन कर सकती है। ऐसे मामलों में इन अतिव्यापी उपसमस्याओं के समाधानों को पहचानने और सहेजने के लायक हो सकता है, तकनीक को आमतौर पर ज्ञापन के रूप में जाना जाता है। सीमा तक अनुसरण करने पर, यह [[नीचे-ऊपर डिजाइन]] | बॉटम-अप डिवाइड-एंड-कॉनकॉर एल्गोरिदम जैसे डायनेमिक प्रोग्रामिंग की ओर जाता है।
+कुछ समस्याओं के लिए, शाखित पुनरावृत्ति ही उप-समस्या का कई बार मूल्यांकन कर सकती है। ऐसे स्थितियों में इन अतिव्यापी उपसमस्याओं के समाधानों को पहचानने और बचत के लायक हो सकता है, इस विधि को सामान्यतः विज्ञापन के रूप में जाना जाता है। जिसे सीमा तक अनुसरण करने पर, यह [[नीचे-ऊपर डिजाइन]] बॉटम-अप डिवाइड-एंड-कॉनकॉर एल्गोरिदम जैसे डायनेमिक प्रोग्रामिंग की ओर जाता है।
 == यह भी देखें ==
@@ Line 81: / Line 82: @@
 {{Commons category|Divide-and-conquer algorithms}}
 * एकरा–बाजी विधि
-* [[विघटित एकत्रीकरण समारोह]]
+* [[विघटित एकत्रीकरण समारोह|विघटित एकत्रीकरण फंक्शन]]
 * फोर्क-जॉइन मॉडल
 * [[मास्टर प्रमेय (एल्गोरिदम का विश्लेषण)]]
@@ Line 93: / Line 94: @@
 {{Authority control}}
-{{DEFAULTSORT:Divide And Conquer Algorithm}}[[Category: फूट डालो और जीतो एल्गोरिदम | फूट डालो और जीतो एल्गोरिदम ]] [[Category: एल्गोरिदम]] [[Category: अनुकूलन एल्गोरिदम और तरीके]]
+{{DEFAULTSORT:Divide And Conquer Algorithm}}
-[[Category: Machine Translated Page]]
+[[Category:Collapse templates|Divide And Conquer Algorithm]]
-[[Category:Created On 31/05/2023]]
+[[Category:Commons category link is locally defined|Divide And Conquer Algorithm]]
+[[Category:Created On 31/05/2023|Divide And Conquer Algorithm]]
+[[Category:Lua-based templates|Divide And Conquer Algorithm]]
+[[Category:Machine Translated Page|Divide And Conquer Algorithm]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists|Divide And Conquer Algorithm]]
+[[Category:Pages with script errors|Divide And Conquer Algorithm]]
+[[Category:Sidebars with styles needing conversion|Divide And Conquer Algorithm]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready|Divide And Conquer Algorithm]]
+[[Category:Templates generating microformats|Divide And Conquer Algorithm]]
+[[Category:Templates that add a tracking category|Divide And Conquer Algorithm]]
+[[Category:Templates that are not mobile friendly|Divide And Conquer Algorithm]]
+[[Category:Templates that generate short descriptions|Divide And Conquer Algorithm]]
+[[Category:Templates using TemplateData|Divide And Conquer Algorithm]]
+[[Category:Wikipedia metatemplates|Divide And Conquer Algorithm]]
+[[Category:अनुकूलन एल्गोरिदम और तरीके|Divide And Conquer Algorithm]]
+[[Category:एल्गोरिदम|Divide And Conquer Algorithm]]
+[[Category:फूट डालो और जीतो एल्गोरिदम| फूट डालो और जीतो एल्गोरिदम ]]

v t e Well-known computer science algorithms
Categories	Minimax Sorting Search Streaming
Paradigms	Backtracking Brute-force search Divide and conquer Dynamic programming Greedy Sweep line Recursion
Other	Binary search Breadth-first search Depth-first search Topological sorting
List of algorithms

Anonymous

Search

विभाजन-और-कन्कर एल्गोरिथ्म: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 09:18, 28 June 2023

Contents

विभाजन और विजय

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