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

Latest revision as of 16:04, 5 September 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))).$ यह वह विधि है जिसका प्रयोग यह सिद्ध करना करने के लिए किया जाता है कि, यदि P ≠ NP (अनसुलझा अनुमान), प्रत्येक एनपी-पूर्ण समस्या की सम्मिश्रता है $\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 1: / Line 1: @@
-{{Short description|Amount of resources to perform an algorithm}}
+[[कंप्यूटर विज्ञान]] में संगणनात्मक सम्मिश्रता या कलनविधि की सम्मिश्रता को चलाने के लिए आवश्यक संसाधनों की मात्रा है। विशेष ध्यान [[समय जटिलता|समय सम्मिश्रता]] (सामान्यतः आवश्यक प्राथमिक संचालन की संख्या से मापा जाता है) और [[अंतरिक्ष जटिलता|अंतरिक्ष सम्मिश्रता]] आवश्यकताओं को दिया जाता है। [[कम्प्यूटेशनल समस्या|संगणनात्मक समस्या]] की सम्मिश्रता सर्वश्रेष्ठ कलनविधि की सम्मिश्रता है जो समस्या को हल करने की अनुमति देती है।
-{{no footnotes|date=December 2017}}
-[[कंप्यूटर विज्ञान]] में, कम्प्यूटेशनल जटिलता या केवल एक एल्गोरिथ्म की जटिलता इसे चलाने के लिए आवश्यक संसाधनों की मात्रा है। विशेष ध्यान [[समय जटिलता]] (आमतौर पर आवश्यक प्राथमिक संचालन की संख्या से मापा जाता है) और [[अंतरिक्ष जटिलता]] आवश्यकताओं को दिया जाता है। [[कम्प्यूटेशनल समस्या]] की जटिलता सर्वश्रेष्ठ एल्गोरिदम की जटिलता है जो समस्या को हल करने की अनुमति देती है।
-स्पष्ट रूप से दिए गए एल्गोरिदम की जटिलता के अध्ययन को [[एल्गोरिदम का विश्लेषण]] कहा जाता है, जबकि समस्याओं की जटिलता के अध्ययन को [[कम्प्यूटेशनल जटिलता सिद्धांत]] कहा जाता है। दोनों क्षेत्र अत्यधिक संबंधित हैं, क्योंकि एक [[कलन विधि]] की जटिलता हमेशा इस एल्गोरिथम द्वारा हल की गई समस्या की जटिलता पर एक [[ऊपरी सीमा]] होती है। इसके अलावा, कुशल एल्गोरिदम को डिजाइन करने के लिए, हल करने के लिए समस्या की जटिलता के लिए विशिष्ट एल्गोरिदम की जटिलता की तुलना करना अक्सर मौलिक होता है। इसके अलावा, ज्यादातर मामलों में, किसी समस्या की जटिलता के बारे में केवल एक ही बात पता चलती है कि यह सबसे कुशल ज्ञात एल्गोरिदम की जटिलता से कम है। इसलिए, एल्गोरिदम और जटिलता सिद्धांत के विश्लेषण के बीच एक बड़ा ओवरलैप है।
+स्पष्ट रूप से दिए गए कलनविधि की सम्मिश्रता के अध्ययन को [[एल्गोरिदम का विश्लेषण|कलनविधि का विश्लेषण]] कहा जाता है, जबकि समस्याओं की सम्मिश्रता के अध्ययन को [[कम्प्यूटेशनल जटिलता सिद्धांत|संगणनात्मक सम्मिश्रता सिद्धांत]] कहा जाता है। दोनों क्षेत्र अत्यधिक संबंधित हैं, क्योंकि [[कलन विधि]] की सम्मिश्रता निरंतर कलनविधि द्वारा हल की गई समस्या की सम्मिश्रता पर [[ऊपरी सीमा]] होती है। इसके अतिरिक्त, कुशल कलनविधि को डिजाइन करने के लिए, हल करने के लिए समस्या की सम्मिश्रता के लिए विशिष्ट कलनविधि की सम्मिश्रता की तुलना करना अधिकांशतः मौलिक होता है। इसके अतिरिक्त, ज्यादातर स्थितियों में, किसी समस्या की सम्मिश्रता के बारे में केवल एक ही बात पता चलती है कि यह सबसे कुशल ज्ञात कलनविधि की सम्मिश्रता से कम है। इसलिए, कलनविधि और सम्मिश्रता सिद्धांत के विश्लेषण के बीच बड़ा अधिव्यापन है।
-चूंकि एल्गोरिदम चलाने के लिए आवश्यक संसाधनों की मात्रा आम तौर पर इनपुट के आकार के साथ भिन्न होती है, जटिलता को आमतौर पर एक फ़ंक्शन के रूप में व्यक्त किया जाता है {{math|''n'' → ''f''(''n'')}}, कहाँ {{math|''n''}} इनपुट का आकार है और {{math|''f''(''n'')}} या तो [[सबसे खराब स्थिति जटिलता]] है (आकार के सभी इनपुट पर आवश्यक संसाधनों की अधिकतम मात्रा {{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''}} की जाती है।
 == संसाधन ==
 === समय ===
-जिस संसाधन को सबसे अधिक माना जाता है वह समय है। जब योग्यता के बिना जटिलता का उपयोग किया जाता है, तो इसका अर्थ आमतौर पर समय जटिलता होता है।
+जिस संसाधन को सबसे अधिक माना जाता है, वह समय है। जब योग्यता के बिना सम्मिश्रता का उपयोग किया जाता है, तो इसका अर्थ सामान्यतः समय सम्मिश्रता होता है।
-कम्प्यूटेशनल जटिलता सिद्धांत में समय की सामान्य इकाइयों (सेकंड, मिनट आदि) का उपयोग नहीं किया जाता है क्योंकि वे एक विशिष्ट कंप्यूटर की पसंद और प्रौद्योगिकी के विकास पर बहुत अधिक निर्भर हैं। उदाहरण के लिए, एक कंप्यूटर आज 1960 के दशक के कंप्यूटर की तुलना में काफी तेजी से एक एल्गोरिथम निष्पादित कर सकता है; हालाँकि, यह एल्गोरिथम की आंतरिक विशेषता नहीं है, बल्कि [[कंप्यूटर हार्डवेयर]] में तकनीकी प्रगति का परिणाम है। जटिलता सिद्धांत एल्गोरिदम की आंतरिक समय की आवश्यकताओं को मापने का प्रयास करता है, यानी, मूल समय की कमी एक एल्गोरिदम किसी भी कंप्यूटर पर रखेगी। यह गणना के दौरान निष्पादित किए जाने वाले प्राथमिक कार्यों की संख्या की गणना करके प्राप्त किया जाता है। यह माना जाता है कि ये ऑपरेशन किसी दिए गए मशीन पर निरंतर समय लेते हैं (अर्थात, इनपुट के आकार से प्रभावित नहीं होते हैं), और अक्सर इन्हें चरण कहा जाता है।
+संगणनात्मक सम्मिश्रता सिद्धांत में समय की सामान्यतः इकाइयों (सेकंड, मिनट आदि) का उपयोग नहीं किया जाता है क्योंकि वे विशिष्ट कंप्यूटर की पसंद और प्रौद्योगिकी के विकास पर बहुत अधिक निर्भर हैं। उदाहरण के लिए, एक कंप्यूटर आज 1960 के दशक के कंप्यूटर की तुलना में अधिक तेजी से कलनविधि निष्पादित कर सकता है; चूंकि, यह कलनविधि की आंतरिक विशेषता नहीं है, अपितु [[कंप्यूटर हार्डवेयर]] में तकनीकी प्रगति का परिणाम है। सम्मिश्रता सिद्धांत कलनविधि की आंतरिक समय की आवश्यकताओं को मापने का प्रयास करता है, अर्थात, मूल समय की कमी कलनविधि किसी भी कंप्यूटर पर रखती है। यह गणना के समय निष्पादित किए जाने वाले प्राथमिक कार्यों की संख्या की गणना करके प्राप्त किया जाता है। यह माना जाता है कि ये ऑपरेशन किसी दिए गए मशीन पर निरंतर समय लेता हैं (अर्थात, निविष्ट के बनावट से प्रभावित नहीं होते हैं), और अधिकांशतः इन्हें चरण कहा जाता है।
-=== बिट जटिलता ===
+=== [[अंश]] सम्मिश्रता ===
-{{anchor|bit complexity}}
+औपचारिक रूप से, [[अंश]] सम्मिश्रता कलनविधि को चलाने के लिए आवश्यक बिट्स पर संचालन की संख्या को संदर्भित करती है। संगणना के अधिकांश प्रारूप के साथ, यह एक स्थिर कारक तक समय की सम्मिश्रता के समान है। [[कंप्यूटर]] पर, [[मशीन शब्द]]ों पर आवश्यक संचालन की संख्या भी [[अंश]] सम्मिश्रता के समानुपाती होती है। तो, समय सम्मिश्रता और [[अंश]] सम्मिश्रता गणना के यथार्थवादी प्रारूप के बराबर हैं।
-औपचारिक रूप से, [[अंश]] जटिलता एक एल्गोरिथ्म को चलाने के लिए आवश्यक बिट्स पर संचालन की संख्या को संदर्भित करती है। संगणना के अधिकांश मॉडलों के साथ, यह एक स्थिर कारक तक समय की जटिलता के बराबर है। [[कंप्यूटर]] पर, [[मशीन शब्द]]ों पर आवश्यक संचालन की संख्या भी बिट जटिलता के समानुपाती होती है। तो, समय जटिलता और बिट जटिलता गणना के यथार्थवादी मॉडल के बराबर हैं।
 === अंतरिक्ष ===
-एक अन्य महत्वपूर्ण संसाधन कंप्यूटर मेमोरी का आकार है जो एल्गोरिदम चलाने के लिए आवश्यक है।
+एक अन्य महत्वपूर्ण संसाधन कंप्यूटर स्मरणशक्ति का बनावट है जो कलनविधि चलाने के लिए आवश्यक है।
 === संचार ===
-{{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>
+कुछ समस्याओं का समाधान, विशेष रूप से [[कंप्यूटर बीजगणित]] और संगणनात्मक बीजगणितीय ज्यामिति में, बहुत बड़ा हो सकता है। ऐसे स्थितियों में, प्रक्षेपण के अधिकतम बनावट से सम्मिश्रता कम होती है, क्योंकि प्रक्षेपण लिखा जाना चाहिए। उदाहरण के लिए, बहुपद समीकरणों की प्रणाली {{mvar|n}} डिग्री के बहुपद समीकरण {{mvar|d}} में {{mvar|n}} अनिश्चित तक हो सकता है <math>d^n</math> [[जटिल संख्या]] समाधान, यदि समाधान की संख्या परिमित है (यह बेज़ाउट प्रमेय है)। जैसा कि इन समाधानों को लिखा जाना चाहिए, इस समस्या की सम्मिश्रता है <math>\Omega(d^n).</math> इस समस्या के लिए, सम्मिश्रता का कलनविधि <math>d^{O(n)}</math> जाना जाता है, जिसे इस प्रकार असम्बद्ध रूप से अर्ध-इष्टतम माना जा सकता है।
-अधिकांश समस्याओं को हल करने के लिए, सभी इनपुट डेटा को पढ़ने की आवश्यकता होती है, जिसे सामान्य रूप से डेटा के आकार के अनुपात में समय की आवश्यकता होती है। इस प्रकार, ऐसी समस्याओं में एक जटिलता होती है जो कम से कम [[रैखिक समय]] होती है, जो कि बड़े ओमेगा संकेतन का उपयोग करते हुए एक जटिलता है <math>\Omega(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|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> स्टर्लिंग के सूत्र द्वारा।
+सम्मिश्रता की निचली सीमा प्राप्त करने के लिए मानक विधि में एक समस्या को दूसरी समस्या में घटाना सम्मलित करता है। अधिक त्रुटिहीन रूप से, मान लीजिए कि कोई समस्या को सांकेतिक शब्दों में परिवर्तित सकता है {{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> यह वह विधि है जिसका प्रयोग यह सिद्ध करना करने के लिए किया जाता है कि, यदि P ≠ NP (अनसुलझा अनुमान), प्रत्येक एनपी-पूर्ण समस्या की सम्मिश्रता है <math>\Omega(n^k),</math> प्रत्येक सकारात्मक पूर्णांक {{mvar|k}} के लिए है।
-जटिलता की निचली सीमा प्राप्त करने के लिए एक मानक विधि में एक समस्या को दूसरी समस्या में घटाना शामिल है। अधिक सटीक रूप से, मान लीजिए कि कोई समस्या को सांकेतिक शब्दों में बदल सकता है {{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}}.
+== कलनविधि डिजाइन में उपयोग ==
-== [[एल्गोरिथम डिजाइन]] में प्रयोग करें ==
+कलनविधि की सम्मिश्रता का मूल्यांकन इसकी डिज़ाइन का महत्वपूर्ण भाग है, क्योंकि यह अपेक्षित प्रदर्शन पर उपयुक्त जानकारी देता है।
-एल्गोरिथम की जटिलता का मूल्यांकन एल्गोरिथम डिज़ाइन का एक महत्वपूर्ण हिस्सा है, क्योंकि यह अपेक्षित प्रदर्शन पर उपयोगी जानकारी देता है।
+यह गलत धारणा है कि मूरे के नियम के परिणामस्वरूप कलनविधि की सम्मिश्रता का मूल्यांकन कम महत्वपूर्ण हो जाएगा, जो आधुनिक कंप्यूटरों की शक्ति की [[घातीय वृद्धि]] को मानता है। यह शक्ति वृद्धि बड़े निविष्ट डेटा (बिग डेटा) के साथ काम करने की अनुमति देती है। उदाहरण के लिए, जब कोई कुछ सैकड़ों प्रविष्टियों की सूची को वर्णानुक्रम में क्रमबद्ध करना चाहता है, जैसे किसी पुस्तक की [[ग्रंथ सूची]], तो किसी भी कलनविधि को एक सेकंड से भी कम समय में अच्छी प्रकार से काम करना चाहिए। दूसरी ओर, एक लाख प्रविष्टियों की सूची के लिए (उदाहरण के लिए, बड़े शहर के फोन नंबर), आवश्यक प्राथमिक कलनविधि <math>O(n^2)</math> तुलनाओं को एक ट्रिलियन तुलना करनी होगी, जिसके लिए प्रति सेकंड 10 मिलियन तुलनाओं की गति से लगभग तीन घंटे की आवश्यकता होगी। दूसरी ओर, [[जल्दी से सुलझाएं|क्विक सॉर्ट]] और [[मर्ज़ सॉर्ट]] के लिए केवल आवश्यकता होती है <math>n\log_2 n</math> तुलना (पूर्व के लिए औसत-स्थितियों की सम्मिश्रता के रूप में, पश्चात के लिए सबसे खराब-सम्मिश्रता के रूप में)। के लिए {{math|1=''n'' = 1,000,000}}, यह लगभग 30,000,000 तुलनाएँ देता है, जो प्रति सेकंड 10 मिलियन तुलनाओं पर केवल 3 सेकंड का समय लेगा।
-यह एक आम ग़लतफ़हमी है कि मूर के नियम के परिणामस्वरूप एल्गोरिदम की जटिलता का मूल्यांकन कम महत्वपूर्ण हो जाएगा, जो आधुनिक कंप्यूटरों की शक्ति की [[घातीय वृद्धि]] को मानता है। यह गलत है क्योंकि यह शक्ति वृद्धि बड़े इनपुट डेटा (बिग डेटा) के साथ काम करने की अनुमति देती है। उदाहरण के लिए, जब कोई कुछ सैकड़ों प्रविष्टियों की सूची को वर्णानुक्रम में क्रमबद्ध करना चाहता है, जैसे किसी पुस्तक की [[ग्रंथ सूची]], तो किसी भी एल्गोरिदम को एक सेकंड से भी कम समय में अच्छी तरह से काम करना चाहिए। दूसरी ओर, एक लाख प्रविष्टियों की सूची के लिए (उदाहरण के लिए, एक बड़े शहर के फोन नंबर), आवश्यक प्राथमिक एल्गोरिदम <math>O(n^2)</math> तुलनाओं को एक ट्रिलियन तुलना करनी होगी, जिसके लिए प्रति सेकंड 10 मिलियन तुलनाओं की गति से लगभग तीन घंटे की आवश्यकता होगी। दूसरी ओर, [[जल्दी से सुलझाएं]] और [[मर्ज़ सॉर्ट]] के लिए केवल आवश्यकता होती है <math>n\log_2 n</math> तुलना (पूर्व के लिए औसत-मामले की जटिलता के रूप में, बाद के लिए सबसे खराब-जटिलता के रूप में)। के लिए {{math|1=''n'' = 1,000,000}}, यह लगभग 30,000,000 तुलनाएँ देता है, जो प्रति सेकंड 10 मिलियन तुलनाओं पर केवल 3 सेकंड का समय लेगा।
+इस प्रकार सम्मिश्रता का मूल्यांकन किसी भी कार्यान्वयन से पहले कई अकुशल कलनविधि को समाप्त करने की अनुमति दे सकता है। इसका उपयोग सभी प्रकारों के परीक्षण के बिना जटिल कलनविधि को ट्यून करने के लिए भी किया जा सकता है। जटिल कलनविधि के सबसे महंगे चरणों का निर्धारण करके, सम्मिश्रता का अध्ययन इन चरणों पर ध्यान केंद्रित करने की अनुमति देता है जिससे की कार्यान्वयन की दक्षता में सुधार के प्रयास किए जा सकें।
-इस प्रकार जटिलता का मूल्यांकन किसी भी कार्यान्वयन से पहले कई अकुशल एल्गोरिदम को समाप्त करने की अनुमति दे सकता है। इसका उपयोग सभी प्रकारों के परीक्षण के बिना जटिल एल्गोरिदम को ट्यून करने के लिए भी किया जा सकता है। एक जटिल एल्गोरिथ्म के सबसे महंगे चरणों का निर्धारण करके, जटिलता का अध्ययन इन चरणों पर ध्यान केंद्रित करने की अनुमति देता है ताकि कार्यान्वयन की दक्षता में सुधार के प्रयास किए जा सकें।
 == यह भी देखें ==
-* [[गणितीय कार्यों की कम्प्यूटेशनल जटिलता]]
+* [[Index.php?title=गणितीय कार्यों की अभिकलनात्मक जटिलता|गणितीय कार्यों की संगणनात्मक सम्मिश्रता]]
-* [[चीनी डाकिया समस्या जटिलता सूची]]
+* [[Index.php?title=चीनी डाकिया समस्या जटिलता सूची|चीनी डाकिया समस्या सम्मिश्रता सूची]]
 ==संदर्भ==
@@ Line 159: / Line 150: @@
 |location=USA
 |isbn=0-534-95097-3
-}}[[Category: एल्गोरिदम का विश्लेषण]] [[Category: कम्प्यूटेशनल जटिलता सिद्धांत]] [[Category: कम्प्यूटेशनल संसाधन]]
+}}
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
 [[Category:Created On 13/02/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:एल्गोरिदम का विश्लेषण]]
+[[Category:कम्प्यूटेशनल जटिलता सिद्धांत]]
+[[Category:कम्प्यूटेशनल संसाधन]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 16:04, 5 September 2023

Contents

संसाधन

समय

अंश सम्मिश्रता

अंतरिक्ष

संचार

अन्य

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

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

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

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

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

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

समस्या सम्मिश्रता (निचली सीमा)

कलनविधि डिजाइन में उपयोग

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 16:04, 5 September 2023

संसाधन

समय

अंश सम्मिश्रता

अंतरिक्ष

संचार

अन्य

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

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

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

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

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

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

समस्या सम्मिश्रता (निचली सीमा)

कलनविधि डिजाइन में उपयोग

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories