संगणनात्मक सम्मिश्रता

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

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

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

संसाधन

समय

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

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

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

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

अंतरिक्ष

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

संचार

Main article: मुख्य लेख: संचार जटिलता

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

अन्य

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

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

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

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

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

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

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

See also: यह भी देखें: एसिम्प्टोटिक कम्प्यूटेशनल जटिलता

सामान्यतः सबसे खराब स्थिति और औसत स्थिति की सम्मिश्रता की स्पष्ट गणना करना कठिन होता है। इसके अतिरिक्त, ये त्रुटिहीन मान थोड़ा व्यावहारिक अनुप्रयोग प्रदान करते हैं, क्योंकि कंप्यूटर या अभिकलन के प्रतिरूप में कोई भी परिवर्तन सम्मिश्रता को कुछ हद तक परिवर्तित कर देता है। इसके अतिरिक्त, संसाधनों का उपयोग छोटे मूल्यों के लिए महत्वपूर्ण 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, व्यावहारिक निहितार्थ के साथ कि एनपी समस्याओं के सबसे खराब स्थितियों हल करने के लिए आंतरिक रूप से कठिन हैं, अर्थात निविष्ट की रोचक लंबाई के लिए किसी भी उचित समय अवधि (दशकों!) से अधिक समय लेते हैं।

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

Main articles: मुख्य लेख: समानांतर कंप्यूटिंग and और वितरित कंप्यूटिंग

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

पर गणना के लिए आवश्यक समय 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