संगणनात्मक सम्मिश्रता: Difference between revisions

Revision as of 23:24, 16 February 2023

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

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

चूंकि एल्गोरिथम चलाने के लिए आवश्यक संसाधनों की मात्रा सामान्यतः निविष्ट के आकार के साथ भिन्न होती है, जटिलता को सामान्यतः एक फलन के रूप में व्यक्त किया जाता है $n \to f (n)$ , जहाँ $n$ निविष्ट का आकार है और $f (n)$ या तो सबसे खराब स्थिति जटिलता है (आकार के सभी निविष्ट पर आवश्यक संसाधनों की अधिकतम मात्रा $n$ ) या औसत-स्थिति जटिलता (आकार के सभी निविष्ट पर संसाधनों की मात्रा का औसत $n$ ). समय जटिलता सामान्यतः आकार के निविष्ट पर आवश्यक प्रारंभिक संचालन की संख्या के रूप में व्यक्त की जाती है $n$ , जहां यह माना जाता है कि किसी दिए गए कंप्यूटर पर प्रारंभिक संचालन एक निरंतर समय लेता है और एक भिन्न कंप्यूटर पर चलने पर केवल एक स्थिर कारक से परिवर्तितता है। अंतरिक्ष जटिलता सामान्यतः आकार के निविष्ट पर एल्गोरिथम द्वारा आवश्यक स्मृति की मात्रा के रूप में व्यक्त $n$ की जाती है।

संसाधन

समय

जिस संसाधन को सबसे अधिक माना जाता है, वह समय है। जब योग्यता के बिना जटिलता का उपयोग किया जाता है, तो इसका अर्थ सामान्यतः समय जटिलता होता है।

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

अंश जटिलता

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

अंतरिक्ष

एक अन्य महत्वपूर्ण संसाधन कंप्यूटर स्मरणशक्ति का आकार है जो एल्गोरिथम चलाने के लिए आवश्यक है।

संचार

वितरित संगणना के वर्ग के लिए जो सामान्यतः कई, अंतःक्रियात्मक दलों द्वारा निष्पादित किया जाता है, जो संसाधन सबसे अधिक रुचि का है वह संचार जटिलता है। निष्पादन पार्टियों के बीच संचार की यह आवश्यक मात्रा है।

अन्य

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

कई एल्गोरिथम के लिए गणना के समय उपयोग किए जाने वाले पूर्णांक का आकार सीमित नहीं है, और यह विचार करना यथार्थवादी नहीं है कि अंकगणितीय संचालन एक निरंतर समय लेता हैं। इसलिए, समय की जटिलता, जिसे सामान्यतः इस संदर्भ में जटिलता कहा जाता है, अंकगणितीय जटिलता से बहुत बड़ी हो सकती है। उदाहरण के लिए, एक निर्धारक की गणना की अंकगणितीय जटिलता $n \times n$ पूर्णांक मैट्रिक्स है $O(n^{3})$ सामान्यतः एल्गोरिथम (गाऊसी उन्मूलन)। उसी एल्गोरिथम की बिट्स जटिलता में घातीय कार्य है $n$ , क्योंकि गणना के समय गुणांकों का आकार तेजी से बढ़ सकता है। दूसरी ओर, यदि एल्गोरिथम को मॉड्यूलर अंकगणित, बहु-मॉड्यूलर अंकगणित के साथ जोड़ा जाता है, तो बिट्स जटिलता को कम किया जा सकता है $O ~ (n 4)$ .

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

सभी संभावित निविष्ट पर एल्गोरिथम के चरणों की संख्या की गणना करना असंभव है। चूंकि जटिलता सामान्यतः निविष्ट के आकार के साथ बढ़ती है, जटिलता को सामान्यतः आकार के कार्य के रूप में व्यक्त किया जाता है $n$ (बिट्स में) निविष्ट का, और इसलिए, जटिलता का एक कार्य $n$ है . चूंकि, एक ही आकार के विभिन्न निविष्ट के लिए एल्गोरिथम की जटिलता नाटकीय रूप से भिन्न हो सकती है। इसलिए, कई जटिलता कार्यों का सामान्यतः उपयोग किया जाता है।

सबसे खराब स्थिति जटिलता आकार के सभी निविष्टों पर अधिकतम जटिलता $n$ है , और औसत-केस जटिलता आकार के सभी निविष्टों पर जटिलता का औसत $n$ है (यह समझ में आता है, क्योंकि किसी दिए गए आकार के संभावित निविष्ट की संख्या परिमित है)। सामान्यतः, जब जटिलता का उपयोग आगे निर्दिष्ट किए बिना किया जाता है, तो यह सबसे खराब समय की जटिलता होती है।

स्पर्शोन्मुख जटिलता

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

इन कारणों से, सामान्यतः बड़े पैमाने पर जटिलता के व्यवहार पर ध्यान केंद्रित किया जाता है, जो इसके स्पर्शोन्मुख विश्लेषण पर $n$ है अनंत की ओर जाता है। इसलिए, जटिलता सामान्यतः बिग ओ नोटेशन का उपयोग करके व्यक्त की जाती है।

उदाहरण के लिए, पूर्णांक गुणन के लिए सामान्यतः एल्गोरिथम में $O(n^{2}),$ जटिलता होती है। इसका मतलब है कि एक $c_{u}$ स्थिर है, कि अधिकतम दो पूर्णांकों का गुणन $n$ अंकों से कम समय में $c_{u}n^{2}.$ किया जा सकता है। यह सीमा इस अर्थ में तेज है कि सबसे खराब स्थिति जटिलता और औसत स्थिति जटिलता है $\Omega (n^{2}),$ जिसका अर्थ है कि $c_{l}$ स्थिर है जैसे कि $c_{l}n^{2}.$ जटिलताएँ इससे बड़ी हैं। इन जटिलताओं में मूलांक प्रकट नहीं होता है, क्योंकि मूलांक के परिवर्तितने से केवल $c_{u}$ और $c_{l}.$ स्थिरांक परिवर्तितते होती हैं।

गणना के प्रतिरूप

जटिलता का मूल्यांकन गणना के एक प्रतिरूप की पसंद पर निर्भर करता है, जिसमें समय की एक इकाई में किए जाने वाले मौलिक कार्यों को परिभाषित करना सम्मलित है। जब गणना के प्रतिरूप को स्पष्ट रूप से निर्दिष्ट नहीं किया जाता है, तो इसका मतलब सामान्यतः मल्टीटेप ट्यूरिंग मशीन के रूप में होता है।

नियतात्मक प्रतिरूप

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

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

गैर-नियतात्मक संगणना

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

यहां तक कि जब इस प्रकार का एक संगणना प्रतिरूप अभी तक यथार्थवादी नहीं है, तो इसका सैद्धांतिक महत्व है, ज्यादातर पी = एनपी समस्या से संबंधित है, जो बहुपद समय और गैर-नियतात्मक बहुपद समय को कम से कम ऊपरी सीमा के रूप में लेने से गठित जटिलता वर्गों की पहचान पर सवाल उठाता है। नियतात्मक कंप्यूटर पर एनपी-एल्गोरिथम का अनुकरण करने में सामान्यतः घातीय समय लगता है। एक समस्या जटिलता वर्ग एनपी (जटिलता) में है, यदि इसे गैर-नियतात्मक मशीन पर बहुपद समय में हल किया जाता है। एक समस्या एनपी-पूर्ण है यदि, मोटे तौर पर, यह एनपी में है और किसी भी अन्य एनपी समस्या से आसान नहीं है। कई जुझारू समस्याएं, जैसे कि नैपसैक समस्या, ट्रैवलिंग सेल्समैन की समस्या, और बूलियन संतुष्टि समस्या एनपी-पूर्ण हैं। इन सभी समस्याओं के लिए, सबसे प्रसिद्ध एल्गोरिथम में घातीय जटिलता है। यदि इन समस्याओं में से किसी एक को निर्धारक मशीन पर बहुपद समय में हल किया जा सकता है, तो सभी एनपी समस्याओं को बहुपद समय में भी हल किया जा सकता है, और एक पी = एनपी होगा। यह सामान्यतः अनुमान लगाया जाता है P ≠ NP, व्यावहारिक निहितार्थ के साथ कि एनपी समस्याओं के सबसे खराब स्थितियों हल करने के लिए आंतरिक रूप से कठिन हैं, अर्थात निविष्ट की रोचक लंबाई के लिए किसी भी उचित समय अवधि (दशकों!) से अधिक समय लेते हैं।

समानांतर और वितरित संगणना

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

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

मुख्य जटिलता समस्या इस प्रकार एल्गोरिथम डिजाइन करने के लिए है कि प्रोसेसर की संख्या द्वारा गणना समय का उत्पाद एक प्रोसेसर पर समान गणना के लिए आवश्यक समय के जितना संभव हो उतना करीब है।

क्वांटम अभिकलन

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

क्वांटम कंप्यूटर का उपयोग करके हल की गई समस्याओं की जटिलता कक्षाओं का अध्ययन करने के लिए क्वांटम जटिलता सिद्धांत विकसित किया गया है। इसका उपयोग पोस्ट-क्वांटम क्रिप्टोग्राफी में किया जाता है, जिसमें क्रिप्टोग्राफिक प्रोटोकॉल डिजाइन करना सम्मलित है जो क्वांटम कंप्यूटरों द्वारा हमलों के प्रतिरोधी हैं।

समस्या जटिलता (निचली सीमा)

किसी समस्या की जटिलता अज्ञात एल्गोरिथम सहित समस्या को हल करने वाले एल्गोरिथम की कम से कम जटिलता रहती है। इस प्रकार किसी समस्या की जटिलता किसी भी एल्गोरिथम की जटिलता से अधिक नहीं होती है जो समस्याओं को हल करती है।

यह इस प्रकार है कि हर जटिलता जो कि बिग ओ नोटेशन के साथ व्यक्त की जाती है, एल्गोरिथम की जटिलता के साथ-साथ संबंधित समस्या भी है।

दूसरी ओर, समस्या की जटिलता के लिए सामान्यतः गैर-तुच्छ निचली सीमाएँ प्राप्त करना कठिन होता है, और ऐसी निचली सीमाएँ प्राप्त करने के कुछ तरीके हैं।

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

की एक अरैखिक निचली सीमा $\Omega (n\log n)$ छँटाई एल्गोरिथम के लिए आवश्यक तुलनाओं की संख्या के लिए जाना जाता है। इस प्रकार सबसे अच्छा छँटाई एल्गोरिथम इष्टतम हैं, क्योंकि उनकी जटिलता है $O(n\log n).$ यह निचली सीमा इस तथ्य से उत्पन्न होती है कि वहाँ हैं $n!$ आदेश देने के तरीके $n$ वस्तुओं। जैसा कि प्रत्येक तुलना दो भागों में विभाजित होती है, यह सेट $n!$ आदेश, की संख्या $N$ सभी आदेशों को भिन्न करने के लिए आवश्यक तुलनाओं को सत्यापित करना चाहिए $2^{N}>n!,$ जो ये दर्शाता हे $N=\Omega (n\log n),$ ।

जटिलता की निचली सीमा प्राप्त करने के लिए एक मानक विधि में एक समस्या को दूसरी समस्या में घटाना सम्मलित करता है। अधिक त्रुटिहीन रूप से, मान लीजिए कि कोई समस्या को सांकेतिक शब्दों में परिवर्तित सकता है $A$ आकार का $n$ आकार की एक उप-समस्या में $f (n)$ एक समस्या का $B$ , और यह कि जटिलता $A$ है $\Omega (g(n)).$ सामान्यता के नुकसान के बिना, कोई यह मान सकता है कि प्रकार्य $f$ , $n$ साथ बढ़ता है और एक उलटा कार्य $h$ करता है। फिर समस्या की जटिलता $B$ है $\Omega (g(h(n))).$ यह वह विधि है जिसका प्रयोग यह सिद्ध करना करने के लिए किया जाता है कि, यदि पी ≠ एनपी (एक अनसुलझा अनुमान), प्रत्येक एनपी-पूर्ण समस्या की जटिलता है $\Omega (n^{k}),$ प्रत्येक सकारात्मक पूर्णांक $k$ के लिए है।

एल्गोरिथम डिजाइन में उपयोग

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

यह एक गलत धारणा है कि मूरे के नियम के परिणामस्वरूप एल्गोरिथम की जटिलता का मूल्यांकन कम महत्वपूर्ण हो जाएगा, जो आधुनिक कंप्यूटरों की शक्ति की घातीय वृद्धि को मानता है। यह शक्ति वृद्धि बड़े निविष्ट डेटा (बिग डेटा) के साथ काम करने की अनुमति देती है। उदाहरण के लिए, जब कोई कुछ सैकड़ों प्रविष्टियों की सूची को वर्णानुक्रम में क्रमबद्ध करना चाहता है, जैसे किसी पुस्तक की ग्रंथ सूची, तो किसी भी एल्गोरिथम को एक सेकंड से भी कम समय में अच्छी प्रकार से काम करना चाहिए। दूसरी ओर, एक लाख प्रविष्टियों की सूची के लिए (उदाहरण के लिए, एक बड़े शहर के फोन नंबर), आवश्यक प्राथमिक एल्गोरिथम $O(n^{2})$ तुलनाओं को एक ट्रिलियन तुलना करनी होगी, जिसके लिए प्रति सेकंड 10 मिलियन तुलनाओं की गति से लगभग तीन घंटे की आवश्यकता होगी। दूसरी ओर, जल्दी से सुलझाएं और मर्ज़ सॉर्ट के लिए केवल आवश्यकता होती है $n\log _{2}n$ तुलना (पूर्व के लिए औसत-स्थितियों की जटिलता के रूप में, पश्चात के लिए सबसे खराब-जटिलता के रूप में)। के लिए $n = 1,000,000$ , यह लगभग 30,000,000 तुलनाएँ देता है, जो प्रति सेकंड 10 मिलियन तुलनाओं पर केवल 3 सेकंड का समय लेगा।

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

यह भी देखें

संदर्भ

Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge, ISBN 978-0-521-42426-4, Zbl 1193.68112
Du, Ding-Zhu; Ko, Ker-I (2000), Theory of Computational Complexity, John Wiley & Sons, ISBN 978-0-471-34506-0
Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5
Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press
van Leeuwen, Jan, ed. (1990), Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, ISBN 978-0-444-88071-0
Papadimitriou, Christos (1994), Computational Complexity (1st ed.), Addison Wesley, ISBN 0-201-53082-1
Sipser, Michael (2006), Introduction to the Theory of Computation (2nd ed.), USA: Thomson Course Technology, ISBN 0-534-95097-3

@@ Line 5: / Line 5: @@
 स्पष्ट रूप से दिए गए एल्गोरिथम की जटिलता के अध्ययन को [[एल्गोरिदम का विश्लेषण|एल्गोरिथम का विश्लेषण]] कहा जाता है, जबकि समस्याओं की जटिलता के अध्ययन को [[कम्प्यूटेशनल जटिलता सिद्धांत|अभिकलनात्मक जटिलता सिद्धांत]] कहा जाता है। दोनों क्षेत्र अत्यधिक संबंधित हैं, क्योंकि एक [[कलन विधि]] की जटिलता निरंतर इस एल्गोरिथम द्वारा हल की गई समस्या की जटिलता पर एक [[ऊपरी सीमा]] होती है। इसके अतिरिक्त, कुशल एल्गोरिथम को डिजाइन करने के लिए, हल करने के लिए समस्या की जटिलता के लिए विशिष्ट एल्गोरिथम की जटिलता की तुलना करना अधिकांशतः मौलिक होता है। इसके अतिरिक्त, ज्यादातर स्थितियों में, किसी समस्या की जटिलता के बारे में केवल एक ही बात पता चलती है कि यह सबसे कुशल ज्ञात एल्गोरिथम की जटिलता से कम है। इसलिए, एल्गोरिथम और जटिलता सिद्धांत के विश्लेषण के बीच एक बड़ा अधिव्यापन है।
-चूंकि एल्गोरिथम चलाने के लिए आवश्यक संसाधनों की मात्रा सामान्यतः निविष्ट के आकार के साथ भिन्न होती है, जटिलता को सामान्यतः एक फलन के रूप में व्यक्त किया जाता है {{math|''n'' → ''f''(''n'')}}, जहाँ {{math|''n''}} निविष्ट का आकार है और {{math|''f''(''n'')}} या तो [[Index.php?title=सबसे खराब जटिलता स्थिति|सबसे खराब स्थिति जटिलता]] है (आकार के सभी निविष्ट पर आवश्यक संसाधनों की अधिकतम मात्रा {{math|''n''}}) या औसत-स्थिति जटिलता (आकार के सभी निविष्ट पर संसाधनों की मात्रा का औसत {{math|''n''}}). समय जटिलता सामान्यतः आकार के निविष्ट पर आवश्यक प्रारंभिक संचालन की संख्या के रूप में व्यक्त की जाती है {{math|''n''}}, जहां यह माना जाता है कि किसी दिए गए कंप्यूटर पर प्रारंभिक संचालन एक निरंतर समय लेता है और एक भिन्न कंप्यूटर पर चलने पर केवल एक स्थिर कारक से बदलता है। अंतरिक्ष जटिलता सामान्यतः आकार के निविष्ट पर एल्गोरिथम द्वारा आवश्यक [[स्मृति]] की मात्रा के रूप में व्यक्त {{math|''n''}} की जाती है।
+चूंकि एल्गोरिथम चलाने के लिए आवश्यक संसाधनों की मात्रा सामान्यतः निविष्ट के आकार के साथ भिन्न होती है, जटिलता को सामान्यतः एक फलन के रूप में व्यक्त किया जाता है {{math|''n'' → ''f''(''n'')}}, जहाँ {{math|''n''}} निविष्ट का आकार है और {{math|''f''(''n'')}} या तो [[Index.php?title=सबसे खराब जटिलता स्थिति|सबसे खराब स्थिति जटिलता]] है (आकार के सभी निविष्ट पर आवश्यक संसाधनों की अधिकतम मात्रा {{math|''n''}}) या औसत-स्थिति जटिलता (आकार के सभी निविष्ट पर संसाधनों की मात्रा का औसत {{math|''n''}}). समय जटिलता सामान्यतः आकार के निविष्ट पर आवश्यक प्रारंभिक संचालन की संख्या के रूप में व्यक्त की जाती है {{math|''n''}}, जहां यह माना जाता है कि किसी दिए गए कंप्यूटर पर प्रारंभिक संचालन एक निरंतर समय लेता है और एक भिन्न कंप्यूटर पर चलने पर केवल एक स्थिर कारक से परिवर्तितता है। अंतरिक्ष जटिलता सामान्यतः आकार के निविष्ट पर एल्गोरिथम द्वारा आवश्यक [[स्मृति]] की मात्रा के रूप में व्यक्त {{math|''n''}} की जाती है।
 == संसाधन ==
@@ Line 22: / Line 22: @@
 === संचार ===
-{{Main article|communication complexity}}
+{{Main article|मुख्य लेख: संचार जटिलता}}
 वितरित संगणना के वर्ग के लिए जो सामान्यतः कई, अंतःक्रियात्मक दलों द्वारा निष्पादित किया जाता है, जो संसाधन सबसे अधिक रुचि का है वह संचार जटिलता है। निष्पादन पार्टियों के बीच संचार की यह आवश्यक मात्रा है।
 === अन्य ===
-अंकगणितीय संक्रियाओं की संख्या एक अन्य संसाधन है जिसका सामान्यतः उपयोग किया जाता है। इस स्थितियों में, एक अंकगणितीय जटिलता की बात करता है। यदि कोई गणना के समय होने वाली संख्याओं के [[द्विआधारी प्रतिनिधित्व]] के आकार पर एक ऊपरी सीमा जानता है, तो समय की जटिलता सामान्यतः एक स्थिर कारक द्वारा अंकगणितीय जटिलता का उत्पाद है।
+अंकगणितीय संक्रियाओं की संख्या एक अन्य संसाधन है जिसका सामान्यतः उपयोग किया जाता है। इस स्थितियों में, अंकगणितीय जटिलता की बात करी गई है। यदि कोई गणना के समय होने वाली संख्याओं के [[द्विआधारी प्रतिनिधित्व]] के आकार पर एक ऊपरी सीमा है, तो समय की जटिलता सामान्यतः एक स्थिर कारक द्वारा अंकगणितीय जटिलता का उत्पाद होता है।
 {{anchor|bit complexity}}
-कई एल्गोरिथम के लिए गणना के समय उपयोग किए जाने वाले पूर्णांक का आकार सीमित नहीं है, और यह विचार करना यथार्थवादी नहीं है कि अंकगणितीय संचालन एक निरंतर समय लेते हैं। इसलिए, समय की जटिलता, जिसे सामान्यतः इस संदर्भ में थोड़ी जटिलता कहा जाता है, अंकगणितीय जटिलता से बहुत बड़ी हो सकती है। उदाहरण के लिए, एक के निर्धारक की गणना की अंकगणितीय जटिलता {{math|''n''×''n''}} [[पूर्णांक मैट्रिक्स]] है <math>O(n^3)</math> सामान्यतः एल्गोरिथम (गाऊसी उन्मूलन) के लिए। उसी एल्गोरिथम की बिट जटिलता में घातीय कार्य है {{mvar|n}}, क्योंकि गणना के समय गुणांकों का आकार तेजी से बढ़ सकता है। दूसरी ओर, यदि इन एल्गोरिथम को [[मॉड्यूलर अंकगणित]] | बहु-मॉड्यूलर अंकगणित के साथ जोड़ा जाता है, तो बिट जटिलता को कम किया जा सकता है {{math|[[soft O notation|''O''<sup>~</sup>(''n''<sup>4</sup>)]]}}.
+कई एल्गोरिथम के लिए गणना के समय उपयोग किए जाने वाले पूर्णांक का आकार सीमित नहीं है, और यह विचार करना यथार्थवादी नहीं है कि अंकगणितीय संचालन एक निरंतर समय लेता हैं। इसलिए, समय की जटिलता, जिसे सामान्यतः इस संदर्भ में जटिलता कहा जाता है, अंकगणितीय जटिलता से बहुत बड़ी हो सकती है। उदाहरण के लिए, एक निर्धारक की गणना की अंकगणितीय जटिलता {{math|''n''×''n''}} [[पूर्णांक मैट्रिक्स]] है <math>O(n^3)</math> सामान्यतः एल्गोरिथम (गाऊसी उन्मूलन)। उसी एल्गोरिथम की बिट्स जटिलता में घातीय कार्य है {{mvar|n}}, क्योंकि गणना के समय गुणांकों का आकार तेजी से बढ़ सकता है। दूसरी ओर, यदि एल्गोरिथम को [[मॉड्यूलर अंकगणित]], बहु-मॉड्यूलर अंकगणित के साथ जोड़ा जाता है, तो बिट्स जटिलता को कम किया जा सकता है {{math|[[soft O notation|''O''<sup>~</sup>(''n''<sup>4</sup>)]]}}.
 [[छँटाई]] और खोज एल्गोरिथम में, सामान्यतः जिस संसाधन पर विचार किया जाता है, वह प्रविष्टि तुलनाओं की संख्या है। यह सामान्यतः समय की जटिलता का एक अच्छा माध्यम है यदि डेटा उपयुक्त रूप से व्यवस्थित हो।
-== निविष्ट आकार == के एक समारोह के रूप में जटिलता
+{{hatnote|इस खंड में केवल समय जटिलता पर विचार किया जा रहा है, लेकिन अन्य संसाधनों के संबंध में जटिलता के लिए सब कुछ (मामूली संशोधनों के साथ) लागू होता है।}}
-{{hatnote|Only time complexity is considered in this section, but everything applies (with slight modifications) to the complexity with respect to other resources}}
+सभी संभावित निविष्ट पर एल्गोरिथम के चरणों की संख्या की गणना करना असंभव है। चूंकि जटिलता सामान्यतः निविष्ट के आकार के साथ बढ़ती है, जटिलता को सामान्यतः आकार के कार्य के रूप में व्यक्त किया जाता है {{math|''n''}} (बिट्स में) निविष्ट का, और इसलिए, जटिलता का एक कार्य {{math|''n''}} है . चूंकि, एक ही आकार के विभिन्न निविष्ट के लिए एल्गोरिथम की जटिलता नाटकीय रूप से भिन्न हो सकती है। इसलिए, कई जटिलता कार्यों का सामान्यतः उपयोग किया जाता है।
-सभी संभावित निविष्ट पर एल्गोरिथम के चरणों की संख्या की गणना करना असंभव है। चूंकि जटिलता सामान्यतः निविष्ट के आकार के साथ बढ़ती है, जटिलता को सामान्यतः आकार के कार्य के रूप में व्यक्त किया जाता है {{math|''n''}} (बिट्स में) निविष्ट का, और इसलिए, जटिलता का एक कार्य है {{math|''n''}}. चूंकि, एक ही आकार के विभिन्न निविष्ट के लिए एल्गोरिथम की जटिलता नाटकीय रूप से भिन्न हो सकती है। इसलिए, कई जटिलता कार्यों का सामान्यतः उपयोग किया जाता है।
-सबसे खराब स्थिति जटिलता आकार के सभी निविष्टों पर अधिकतम जटिलता है {{mvar|n}}, और औसत-केस जटिलता आकार के सभी निविष्टों पर जटिलता का औसत है {{mvar|n}} (यह समझ में आता है, क्योंकि किसी दिए गए आकार के संभावित निविष्ट की संख्या परिमित है)। सामान्यतः, जब जटिलता का उपयोग आगे निर्दिष्ट किए बिना किया जाता है, तो यह सबसे खराब समय की जटिलता है जिसे माना जाता है।
+सबसे खराब स्थिति जटिलता आकार के सभी निविष्टों पर अधिकतम जटिलता {{mvar|n}} है , और औसत-केस जटिलता आकार के सभी निविष्टों पर जटिलता का औसत {{mvar|n}} है (यह समझ में आता है, क्योंकि किसी दिए गए आकार के संभावित निविष्ट की संख्या परिमित है)। सामान्यतः, जब जटिलता का उपयोग आगे निर्दिष्ट किए बिना किया जाता है, तो यह सबसे खराब समय की जटिलता होती है।
 == स्पर्शोन्मुख जटिलता ==
-{{see also|Asymptotic computational complexity}}
+{{see also|यह भी देखें: एसिम्प्टोटिक कम्प्यूटेशनल जटिलता}}
-सामान्यतः सबसे खराब स्थिति और औसत स्थिति की जटिलता की ठीक-ठीक गणना करना कठिन होता है। इसके अतिरिक्त, ये त्रुटिहीन मान थोड़ा व्यावहारिक अनुप्रयोग प्रदान करते हैं, क्योंकि कंप्यूटर या अभिकलन के मॉडल में कोई भी परिवर्तन जटिलता को कुछ हद तक बदल देगा। इसके अतिरिक्त, संसाधनों का उपयोग छोटे मूल्यों के लिए महत्वपूर्ण नहीं है {{mvar|n}}, और यह उसे, छोटे के लिए बनाता है {{mvar|n}}कार्यान्वयन में आसानी सामान्यतः कम जटिलता की तुलना में अधिक रोचक होती है।
-इन कारणों से, सामान्यतः बड़े पैमाने पर जटिलता के व्यवहार पर ध्यान केंद्रित किया जाता है {{mvar|n}}, जो इसके [[स्पर्शोन्मुख विश्लेषण]] पर है {{mvar|n}} अनंत की ओर जाता है। इसलिए, जटिलता सामान्यतः [[बिग ओ नोटेशन]] का उपयोग करके व्यक्त की जाती है।
+सामान्यतः सबसे खराब स्थिति और औसत स्थिति की जटिलता की स्पष्ट गणना करना कठिन होता है। इसके अतिरिक्त, ये त्रुटिहीन मान थोड़ा व्यावहारिक अनुप्रयोग प्रदान करते हैं, क्योंकि कंप्यूटर या अभिकलन के प्रतिरूप में कोई भी परिवर्तन जटिलता को कुछ हद तक परिवर्तित कर देता है। इसके अतिरिक्त, संसाधनों का उपयोग छोटे मूल्यों के लिए महत्वपूर्ण {{mvar|n}} नहीं है , और यह उसे, कार्यान्वयन में आसानी सामान्यतः कम जटिलता की तुलना में अधिक रोचक होती है।
-उदाहरण के लिए, पूर्णांक गुणन के लिए सामान्यतः एल्गोरिथम में जटिलता होती है <math>O(n^2),</math> इसका मतलब है कि एक स्थिर है <math>c_u</math> ऐसा कि अधिकतम दो पूर्णांकों का गुणन {{mvar|n}} अंकों से कम समय में किया जा सकता है <math>c_un^2.</math> यह सीमा इस अर्थ में तेज है कि सबसे खराब स्थिति जटिलता और औसत स्थिति जटिलता है <math>\Omega(n^2),</math> जिसका अर्थ है कि एक स्थिर है <math>c_l</math> जैसे कि ये जटिलताएँ इससे बड़ी हैं <math>c_ln^2.</math> इन जटिलताओं में [[मूलांक]] प्रकट नहीं होता है, क्योंकि मूलांक के बदलने से केवल स्थिरांक बदलते हैं <math>c_u</math> और <math>c_l.</math>
+इन कारणों से, सामान्यतः बड़े पैमाने पर जटिलता के व्यवहार पर ध्यान केंद्रित किया जाता है, जो इसके [[स्पर्शोन्मुख विश्लेषण]] पर {{mvar|n}} है अनंत की ओर जाता है। इसलिए, जटिलता सामान्यतः [[बिग ओ नोटेशन]] का उपयोग करके व्यक्त की जाती है।
+उदाहरण के लिए, पूर्णांक गुणन के लिए सामान्यतः एल्गोरिथम में <math>O(n^2),</math>जटिलता होती है। इसका मतलब है कि एक <math>c_u</math> स्थिर है, कि अधिकतम दो पूर्णांकों का गुणन {{mvar|n}} अंकों से कम समय में <math>c_un^2.</math> किया जा सकता है। यह सीमा इस अर्थ में तेज है कि सबसे खराब स्थिति जटिलता और औसत स्थिति जटिलता है <math>\Omega(n^2),</math> जिसका अर्थ है कि <math>c_l</math> स्थिर है जैसे कि <math>c_ln^2.</math> जटिलताएँ इससे बड़ी हैं। इन जटिलताओं में [[मूलांक]] प्रकट नहीं होता है, क्योंकि मूलांक के परिवर्तितने से केवल <math>c_u</math> और <math>c_l.</math> स्थिरांक परिवर्तितते होती हैं।
+== गणना के प्रतिरूप ==
+जटिलता का मूल्यांकन गणना के एक प्रतिरूप की पसंद पर निर्भर करता है, जिसमें समय की एक इकाई में किए जाने वाले मौलिक कार्यों को परिभाषित करना सम्मलित है। जब गणना के प्रतिरूप को स्पष्ट रूप से निर्दिष्ट नहीं किया जाता है, तो इसका मतलब सामान्यतः [[मल्टीटेप ट्यूरिंग मशीन]] के रूप में होता है।
-== गणना के मॉडल ==
+=== [[नियतात्मक मॉडल|नियतात्मक प्रतिरूप]] ===
-जटिलता का मूल्यांकन गणना के एक मॉडल की पसंद पर निर्भर करता है, जिसमें समय की एक इकाई में किए जाने वाले मौलिक कार्यों को परिभाषित करना सम्मलित है। जब गणना के मॉडल को स्पष्ट रूप से निर्दिष्ट नहीं किया जाता है, तो इसका मतलब सामान्यतः [[मल्टीटेप ट्यूरिंग मशीन]] के रूप में होता है।
+संगणना का एक नियतात्मक प्रतिरूप संगणना का एक प्रतिरूप है जैसे कि मशीन की क्रमिक अवस्थाएँ और किए जाने वाले संचालन पूरी प्रकार से पूर्ववर्ती अवस्था द्वारा निर्धारित किए जाते हैं। ऐतिहासिक रूप से, पहले नियतात्मक प्रतिरूप μ-पुनरावर्ती कार्य, [[लैम्ब्डा कैलकुलस|लैम्ब्डा कलन]] और [[ट्यूरिंग मशीन]] थे। [[रैंडम-एक्सेस मशीन]] (जिसे रैम-मशीन भी कहा जाता है) का प्रतिरूप भी व्यापक रूप से वास्तविक कंप्यूटरों के निकट समकक्ष के रूप में उपयोग किया जाता है।
-=== [[नियतात्मक मॉडल]] ===
+जब गणना का प्रतिरूप निर्दिष्ट नहीं किया जाता है, तो इसे सामान्यतः मल्टीटेप ट्यूरिंग मशीन माना जाता है। अधिकांश एल्गोरिथम के लिए, समय की जटिलता मल्टीटेप ट्यूरिंग मशीनों पर रैम-मशीनों के समान होती है, चूंकि इस समानता को प्राप्त करने के लिए मेमोरी में डेटा को कैसे संग्रहीत किया जाता है, इसमें कुछ देखभाल की आवश्यकता रहती है।
-संगणना का एक नियतात्मक मॉडल संगणना का एक मॉडल है जैसे कि मशीन की क्रमिक अवस्थाएँ और किए जाने वाले संचालन पूरी प्रकार से पूर्ववर्ती अवस्था द्वारा निर्धारित किए जाते हैं। ऐतिहासिक रूप से, पहले नियतात्मक मॉडल μ-पुनरावर्ती कार्य, [[लैम्ब्डा कैलकुलस]] और [[ट्यूरिंग मशीन]] थे। [[रैंडम-एक्सेस मशीन]] (जिसे रैम-मशीन भी कहा जाता है) का मॉडल भी व्यापक रूप से उपयोग किया जाता है, वास्तविक कंप्यूटरों के निकट समकक्ष के रूप में।
-जब गणना का मॉडल निर्दिष्ट नहीं किया जाता है, तो इसे सामान्यतः मल्टीटेप ट्यूरिंग मशीन माना जाता है। अधिकांश एल्गोरिथम के लिए, समय की जटिलता मल्टीटेप ट्यूरिंग मशीनों पर रैम-मशीनों के समान होती है, चूंकि इस समानता को प्राप्त करने के लिए मेमोरी में डेटा को कैसे संग्रहीत किया जाता है, इसमें कुछ देखभाल की आवश्यकता हो सकती है।
 === गैर-नियतात्मक संगणना ===
-एक गैर-नियतात्मक एल्गोरिथम | संगणना के गैर-नियतात्मक मॉडल, जैसे कि [[गैर-नियतात्मक ट्यूरिंग मशीन]], गणना के कुछ चरणों में कुछ विकल्प किए जा सकते हैं। जटिलता सिद्धांत में, एक साथ सभी संभावित विकल्पों पर विचार किया जाता है, और गैर-नियतात्मक समय जटिलता समय की आवश्यकता होती है, जब सबसे अच्छा विकल्प निरंतर किया जाता है। दूसरे शब्दों में, कोई यह मानता है कि संगणना एक साथ कई (समान) प्रोसेसरों पर आवश्यकतानुसार की जाती है, और गैर-नियतात्मक संगणना समय पहले प्रोसेसर द्वारा लगाया गया समय है जो संगणना को पूरा करता है। यह समानता आंशिक रूप से [[क्वांटम कम्प्यूटिंग]] के लिए विशिष्ट [[क्वांटम एल्गोरिदम|क्वांटम एल्गोरिथम]] चलाने में सुपरपोज़्ड [[उलझी हुई अवस्था]]ओं के माध्यम से उत्तरदायी है, जैसे उदा। शोर का एल्गोरिद्म | शोर का अभी तक केवल छोटे पूर्णांकों का गुणनखंडन ({{as of|2018|03|lc=yes}}: 21 = 3 × 7)।
+एक गैर-नियतात्मक एल्गोरिथम संगणना के गैर-नियतात्मक प्रतिरूप, जैसे कि [[गैर-नियतात्मक ट्यूरिंग मशीन]], गणना के कुछ चरणों में कुछ विकल्प किए जा सकते हैं। जटिलता सिद्धांत में, एक साथ सभी संभावित विकल्पों पर विचार किया जाता है, और गैर-नियतात्मक समय जटिलता समय की आवश्यकता होती है, जब सबसे अच्छा विकल्प निरंतर किया जाता है। दूसरे शब्दों में, कोई यह मानता है कि संगणना एक साथ कई (समान) प्रोसेसरों पर आवश्यकतानुसार की जाती है, और गैर-नियतात्मक संगणना समय पहले प्रोसेसर द्वारा लगाया गया समय है जो संगणना को पूरा करता है। यह समानता आंशिक रूप से [[क्वांटम कम्प्यूटिंग]] के लिए विशिष्ट [[क्वांटम एल्गोरिदम|क्वांटम एल्गोरिथम]] चलाने में सुपरपोज़्ड [[उलझी हुई अवस्था]]ओं के माध्यम से उत्तरदायी है, जैसे उदा शोर की एल्गोरिद्म |
-यहां तक कि जब इस प्रकार का एक संगणना मॉडल अभी तक यथार्थवादी नहीं है, तो इसका सैद्धांतिक महत्व है, ज्यादातर पी = एनपी समस्या से संबंधित है, जो बहुपद समय और गैर-नियतात्मक बहुपद समय को कम से कम ऊपरी सीमा के रूप में लेने से गठित जटिलता वर्गों की पहचान पर सवाल उठाता है। नियतात्मक कंप्यूटर पर एनपी-एल्गोरिथम का अनुकरण करने में सामान्यतः घातीय समय लगता है। एक समस्या जटिलता वर्ग [[एनपी (जटिलता)]] में है, यदि इसे गैर-नियतात्मक मशीन पर बहुपद समय में हल किया जा सकता है। एक समस्या एनपी-पूर्ण है यदि, मोटे तौर पर बोलना, यह एनपी में है और किसी भी अन्य एनपी समस्या से आसान नहीं है। कई जुझारू समस्याएं, जैसे कि नैपसैक समस्या, [[ट्रैवलिंग सेल्समैन की समस्या]], और [[बूलियन संतुष्टि समस्या]] एनपी-पूर्ण हैं। इन सभी समस्याओं के लिए, सबसे प्रसिद्ध एल्गोरिथम में घातीय जटिलता है। यदि इन समस्याओं में से किसी एक को निर्धारक मशीन पर बहुपद समय में हल किया जा सकता है, तो सभी एनपी समस्याओं को बहुपद समय में भी हल किया जा सकता है, और एक पी = एनपी होगा। {{As of|2017}} यह सामान्यतः अनुमान लगाया जाता है {{nowrap|P ≠ NP,}} व्यावहारिक निहितार्थ के साथ कि एनपी समस्याओं के सबसे खराब स्थितियों हल करने के लिए आंतरिक रूप से कठिन हैं, अर्थात निविष्ट की रोचक लंबाई के लिए किसी भी उचित समय अवधि (दशकों!) से अधिक समय लेते हैं।
+यहां तक कि जब इस प्रकार का एक संगणना प्रतिरूप अभी तक यथार्थवादी नहीं है, तो इसका सैद्धांतिक महत्व है, ज्यादातर पी = एनपी समस्या से संबंधित है, जो बहुपद समय और गैर-नियतात्मक बहुपद समय को कम से कम ऊपरी सीमा के रूप में लेने से गठित जटिलता वर्गों की पहचान पर सवाल उठाता है। नियतात्मक कंप्यूटर पर एनपी-एल्गोरिथम का अनुकरण करने में सामान्यतः घातीय समय लगता है। एक समस्या जटिलता वर्ग [[एनपी (जटिलता)]] में है, यदि इसे गैर-नियतात्मक मशीन पर बहुपद समय में हल किया जाता है। एक समस्या एनपी-पूर्ण है यदि, मोटे तौर पर, यह एनपी में है और किसी भी अन्य एनपी समस्या से आसान नहीं है। कई जुझारू समस्याएं, जैसे कि नैपसैक समस्या, [[ट्रैवलिंग सेल्समैन की समस्या]], और [[बूलियन संतुष्टि समस्या]] एनपी-पूर्ण हैं। इन सभी समस्याओं के लिए, सबसे प्रसिद्ध एल्गोरिथम में घातीय जटिलता है। यदि इन समस्याओं में से किसी एक को निर्धारक मशीन पर बहुपद समय में हल किया जा सकता है, तो सभी एनपी समस्याओं को बहुपद समय में भी हल किया जा सकता है, और एक पी = एनपी होगा। यह सामान्यतः अनुमान लगाया जाता है {{nowrap|P ≠ NP,}} व्यावहारिक निहितार्थ के साथ कि एनपी समस्याओं के सबसे खराब स्थितियों हल करने के लिए आंतरिक रूप से कठिन हैं, अर्थात निविष्ट की रोचक लंबाई के लिए किसी भी उचित समय अवधि (दशकों!) से अधिक समय लेते हैं।
 === समानांतर और वितरित संगणना ===
-{{main|Parallel computing|Distributed computing}}
+{{main|मुख्य लेख: समानांतर कंप्यूटिंग|और वितरित कंप्यूटिंग}}
-समानांतर और वितरित अभिकलन में कई प्रोसेसरों पर विभाजन की गणना होती है, जो एक साथ काम करते हैं। विभिन्न मॉडलों के बीच का अंतर मुख्य रूप से प्रोसेसर के बीच सूचना प्रसारित करने के तरीके में निहित है। सामान्यतः, समानांतर अभिकलन में प्रोसेसर के बीच डेटा ट्रांसमिशन बहुत तेज होता है, जबकि डिस्ट्रीब्यूटेड अभिकलन में, डेटा ट्रांसमिशन [[संगणक संजाल]] के माध्यम से किया जाता है और इसलिए यह बहुत धीमा होता है।
+समानांतर और वितरित अभिकलन में कई प्रोसेसरों पर विभाजन की गणना होती है, जो एक साथ काम करते हैं। विभिन्न प्रतिरूपों के बीच का अंतर मुख्य रूप से प्रोसेसर के बीच सूचना प्रसारित करने के तरीको में निहित है। सामान्यतः, समानांतर अभिकलन में प्रोसेसर के बीच डेटा ट्रांसमिशन बहुत तेज होता है, जबकि डिस्ट्रीब्यूटेड अभिकलन में, डेटा ट्रांसमिशन [[संगणक संजाल]] के माध्यम से किया जाता है और इसलिए यह बहुत धीमा होता है।
-पर गणना के लिए आवश्यक समय {{mvar|N}} प्रोसेसर कम से कम भागफल है {{mvar|N}} एक प्रोसेसर द्वारा आवश्यक समय की। वास्तव में यह सैद्धांतिक रूप से इष्टतम सीमा तक कभी नहीं पहुंचा जा सकता है, क्योंकि कुछ उप-कार्यों को समानांतर नहीं किया जा सकता है, और कुछ प्रोसेसरों को दूसरे प्रोसेसर से परिणाम का इंतजार करना पड़ सकता है।
+पर गणना के लिए आवश्यक समय {{mvar|N}} प्रोसेसर कम से कम भागफल {{mvar|N}} है। वास्तव में यह सैद्धांतिक रूप से इष्टतम सीमा तक कभी नहीं पहुंचा जा सकता है, क्योंकि कुछ उप-कार्यों को समानांतर नहीं किया जा सकता है, और कुछ प्रोसेसरों को दूसरे प्रोसेसर से परिणाम का इंतजार करना पड़ सकता है।
 मुख्य जटिलता समस्या इस प्रकार एल्गोरिथम डिजाइन करने के लिए है कि प्रोसेसर की संख्या द्वारा गणना समय का उत्पाद एक प्रोसेसर पर समान गणना के लिए आवश्यक समय के जितना संभव हो उतना करीब है।
 === क्वांटम अभिकलन ===
-[[एक कंप्यूटर जितना]] एक कंप्यूटर है जिसका अभिकलन का मॉडल [[क्वांटम यांत्रिकी]] पर आधारित होता है। चर्च-ट्यूरिंग थीसिस (जटिलता सिद्धांत) | चर्च-ट्यूरिंग थीसिस क्वांटम कंप्यूटरों पर लागू होता है; अर्थात, क्वांटम कंप्यूटर द्वारा हल की जा सकने वाली हर समस्या को ट्यूरिंग मशीन द्वारा भी हल किया जा सकता है। चूंकि, कुछ समस्याओं को मौलिक कंप्यूटर के अतिरिक्त क्वांटम कंप्यूटर का उपयोग करके सैद्धांतिक रूप से बहुत कम समय जटिलता के साथ हल किया जा सकता है। फिलहाल, यह विशुद्ध रूप से सैद्धांतिक है, क्योंकि कोई नहीं जानता कि एक कुशल क्वांटम कंप्यूटर कैसे बनाया जाए।
+[[एक कंप्यूटर जितना]] एक कंप्यूटर है जिसका अभिकलन का प्रतिरूप [[क्वांटम यांत्रिकी]] पर आधारित होता है। चर्च-ट्यूरिंग थीसिस (जटिलता सिद्धांत) | चर्च-ट्यूरिंग थीसिस क्वांटम कंप्यूटरों पर लागू होता है; अर्थात, क्वांटम कंप्यूटर द्वारा हल की जा सकने वाली हर समस्या को ट्यूरिंग मशीन द्वारा भी हल किया जा सकता है। चूंकि, कुछ समस्याओं को मौलिक कंप्यूटर के अतिरिक्त क्वांटम कंप्यूटर का उपयोग करके सैद्धांतिक रूप से बहुत कम समय जटिलता के साथ हल किया जा सकता है। फिलहाल, यह विशुद्ध रूप से सैद्धांतिक है, क्योंकि कोई नहीं जानता कि एक कुशल क्वांटम कंप्यूटर कैसे बनाया जाए।
 क्वांटम कंप्यूटर का उपयोग करके हल की गई समस्याओं की जटिलता कक्षाओं का अध्ययन करने के लिए [[क्वांटम जटिलता सिद्धांत]] विकसित किया गया है। इसका उपयोग [[पोस्ट-क्वांटम क्रिप्टोग्राफी]] में किया जाता है, जिसमें [[क्रिप्टोग्राफिक प्रोटोकॉल]] डिजाइन करना सम्मलित है जो क्वांटम कंप्यूटरों द्वारा हमलों के प्रतिरोधी हैं।
 == समस्या जटिलता (निचली सीमा) ==
-किसी समस्या की जटिलता अज्ञात एल्गोरिथम सहित समस्या को हल करने वाले एल्गोरिथम की कम से कम जटिलता है। इस प्रकार किसी समस्या की जटिलता किसी भी एल्गोरिथम की जटिलता से अधिक नहीं होती है जो समस्याओं को हल करती है।
+किसी समस्या की जटिलता अज्ञात एल्गोरिथम सहित समस्या को हल करने वाले एल्गोरिथम की कम से कम जटिलता रहती है। इस प्रकार किसी समस्या की जटिलता किसी भी एल्गोरिथम की जटिलता से अधिक नहीं होती है जो समस्याओं को हल करती है।
-यह इस प्रकार है कि हर जटिलता जो कि बड़े ओ नोटेशन के साथ व्यक्त की जाती है, एल्गोरिथम की जटिलता के साथ-साथ संबंधित समस्या भी है।
+यह इस प्रकार है कि हर जटिलता जो कि बिग ओ नोटेशन के साथ व्यक्त की जाती है, एल्गोरिथम की जटिलता के साथ-साथ संबंधित समस्या भी है।
 दूसरी ओर, समस्या की जटिलता के लिए सामान्यतः गैर-तुच्छ निचली सीमाएँ प्राप्त करना कठिन होता है, और ऐसी निचली सीमाएँ प्राप्त करने के कुछ तरीके हैं।
-अधिकांश समस्याओं को हल करने के लिए, सभी निविष्ट डेटा को पढ़ने की आवश्यकता होती है, जिसे सामान्यतः रूप से डेटा के आकार के अनुपात में समय की आवश्यकता होती है। इस प्रकार, ऐसी समस्याओं में एक जटिलता होती है जो कम से कम [[रैखिक समय]] होती है, जो कि बड़े ओमेगा संकेतन का उपयोग करते हुए एक जटिलता है <math>\Omega(n).</math>
+अधिकांश समस्याओं को हल करने के लिए, सभी निविष्ट डेटा को पढ़ने की आवश्यकता होती है, जिसे सामान्यतः रूप से डेटा के आकार के अनुपात में समय की आवश्यकता होती है। इस प्रकार, ऐसी समस्याओं में एक जटिलता होती है जो कम से कम [[रैखिक समय]] होती है, जो कि बिग ओमेगा संकेतन का उपयोग करते हुए एक जटिलता है <math>\Omega(n).</math>
-कुछ समस्याओं का समाधान, विशेष रूप से [[कंप्यूटर बीजगणित]] और [[कम्प्यूटेशनल बीजगणितीय ज्यामिति|अभिकलनात्मक बीजगणितीय ज्यामिति]] में, बहुत बड़ा हो सकता है। ऐसे स्थितियों में, आउटपुट के अधिकतम आकार से जटिलता कम होती है, क्योंकि आउटपुट लिखा जाना चाहिए। उदाहरण के लिए, बहुपद समीकरणों की एक प्रणाली | की प्रणाली {{mvar|n}} डिग्री के बहुपद समीकरण {{mvar|d}} में {{mvar|n}} अनिश्चित तक हो सकता है <math>d^n</math> [[जटिल संख्या]] समाधान, यदि समाधान की संख्या परिमित है (यह बेज़ाउट प्रमेय है)। जैसा कि इन समाधानों को लिखा जाना चाहिए, इस समस्या की जटिलता है <math>\Omega(d^n).</math> इस समस्या के लिए, जटिलता का एक एल्गोरिथम <math>d^{O(n)}</math> जाना जाता है, जिसे इस प्रकार असम्बद्ध रूप से अर्ध-इष्टतम माना जा सकता है।
+कुछ समस्याओं का समाधान, विशेष रूप से [[कंप्यूटर बीजगणित]] और [[कम्प्यूटेशनल बीजगणितीय ज्यामिति|अभिकलनात्मक बीजगणितीय ज्यामिति]] में, बहुत बड़ा हो सकता है। ऐसे स्थितियों में, प्रक्षेपण के अधिकतम आकार से जटिलता कम होती है, क्योंकि प्रक्षेपण लिखा जाना चाहिए। उदाहरण के लिए, बहुपद समीकरणों की एक प्रणाली {{mvar|n}} डिग्री के बहुपद समीकरण {{mvar|d}} में {{mvar|n}} अनिश्चित तक हो सकता है <math>d^n</math> [[जटिल संख्या]] समाधान, यदि समाधान की संख्या परिमित है (यह बेज़ाउट प्रमेय है)। जैसा कि इन समाधानों को लिखा जाना चाहिए, इस समस्या की जटिलता है <math>\Omega(d^n).</math> इस समस्या के लिए, जटिलता का एक एल्गोरिथम <math>d^{O(n)}</math> जाना जाता है, जिसे इस प्रकार असम्बद्ध रूप से अर्ध-इष्टतम माना जा सकता है।
-की एक अरैखिक निचली सीमा <math>\Omega(n\log n)</math> [[छँटाई एल्गोरिथ्म|छँटाई एल्गोरिथम]] के लिए आवश्यक तुलनाओं की संख्या के लिए जाना जाता है। इस प्रकार सबसे अच्छा छँटाई एल्गोरिथम इष्टतम हैं, क्योंकि उनकी जटिलता है <math>O(n\log n).</math> यह निचली सीमा इस तथ्य से उत्पन्न होती है कि वहाँ हैं {{math|''n''!}} आदेश देने के तरीके {{mvar|n}} वस्तुओं। जैसा कि प्रत्येक तुलना दो भागों में विभाजित होती है, यह सेट {{math|''n''!}} आदेश, की संख्या {{mvar|N}} सभी आदेशों को भिन्न करने के लिए आवश्यक तुलनाओं को सत्यापित करना चाहिए <math>2^N>n!,</math> जो ये दर्शाता हे <math>N =\Omega(n\log n),</math> स्टर्लिंग के सूत्र द्वारा।
+की एक अरैखिक निचली सीमा <math>\Omega(n\log n)</math> [[छँटाई एल्गोरिथ्म|छँटाई एल्गोरिथम]] के लिए आवश्यक तुलनाओं की संख्या के लिए जाना जाता है। इस प्रकार सबसे अच्छा छँटाई एल्गोरिथम इष्टतम हैं, क्योंकि उनकी जटिलता है <math>O(n\log n).</math> यह निचली सीमा इस तथ्य से उत्पन्न होती है कि वहाँ हैं {{math|''n''!}} आदेश देने के तरीके {{mvar|n}} वस्तुओं। जैसा कि प्रत्येक तुलना दो भागों में विभाजित होती है, यह सेट {{math|''n''!}} आदेश, की संख्या {{mvar|N}} सभी आदेशों को भिन्न करने के लिए आवश्यक तुलनाओं को सत्यापित करना चाहिए <math>2^N>n!,</math> जो ये दर्शाता हे <math>N =\Omega(n\log n),</math>।
-जटिलता की निचली सीमा प्राप्त करने के लिए एक मानक विधि में एक समस्या को दूसरी समस्या में घटाना सम्मलित है। अधिक त्रुटिहीन रूप से, मान लीजिए कि कोई समस्या को सांकेतिक शब्दों में बदल सकता है {{mvar|A}} आकार का {{mvar|n}} आकार की एक उप-समस्या में {{math|''f''(''n'')}} एक समस्या का {{mvar|B}}, और यह कि जटिलता {{mvar|A}} है <math>\Omega(g(n)).</math> सामान्यता के नुकसान के बिना, कोई यह मान सकता है कि function {{mvar|f}} साथ बढ़ता है {{mvar|n}} और एक उलटा कार्य करता है {{mvar|h}}. फिर समस्या की जटिलता {{mvar|B}} है <math>\Omega(g(h(n))).</math> यह वह विधि है जिसका प्रयोग यह सिद्ध करना करने के लिए किया जाता है कि, यदि पी ≠ एनपी (एक अनसुलझा अनुमान), प्रत्येक [[एनपी-पूर्ण समस्या]] की जटिलता है <math>\Omega(n^k),</math> प्रत्येक सकारात्मक पूर्णांक के लिए {{mvar|k}}.
+जटिलता की निचली सीमा प्राप्त करने के लिए एक मानक विधि में एक समस्या को दूसरी समस्या में घटाना सम्मलित करता है। अधिक त्रुटिहीन रूप से, मान लीजिए कि कोई समस्या को सांकेतिक शब्दों में परिवर्तित सकता है {{mvar|A}} आकार का {{mvar|n}} आकार की एक उप-समस्या में {{math|''f''(''n'')}} एक समस्या का {{mvar|B}}, और यह कि जटिलता {{mvar|A}} है <math>\Omega(g(n)).</math> सामान्यता के नुकसान के बिना, कोई यह मान सकता है कि प्रकार्य  {{mvar|f}}, {{mvar|n}}  साथ बढ़ता है और एक उलटा कार्य {{mvar|h}} करता है। फिर समस्या की जटिलता {{mvar|B}} है <math>\Omega(g(h(n))).</math> यह वह विधि है जिसका प्रयोग यह सिद्ध करना करने के लिए किया जाता है कि, यदि पी ≠ एनपी (एक अनसुलझा अनुमान), प्रत्येक [[एनपी-पूर्ण समस्या]] की जटिलता है <math>\Omega(n^k),</math> प्रत्येक सकारात्मक पूर्णांक {{mvar|k}} के लिए है।
 == एल्गोरिथम डिजाइन में उपयोग ==

Anonymous

Search

संगणनात्मक सम्मिश्रता: Difference between revisions

Namespaces

More

Page actions

Revision as of 23:24, 16 February 2023

Contents

संसाधन