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

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

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

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

संसाधन

समय

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

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

बिट जटिलता

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

अंतरिक्ष

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

संचार

Main article: communication complexity

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

अन्य

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

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

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

== इनपुट आकार == के एक समारोह के रूप में जटिलता

Only time complexity is considered in this section, but everything applies (with slight modifications) to the complexity with respect to other resources

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

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

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

See also: Asymptotic computational complexity

आमतौर पर सबसे खराब स्थिति और औसत स्थिति की जटिलता की ठीक-ठीक गणना करना कठिन होता है। इसके अलावा, ये सटीक मान थोड़ा व्यावहारिक अनुप्रयोग प्रदान करते हैं, क्योंकि कंप्यूटर या अभिकलन के मॉडल में कोई भी परिवर्तन जटिलता को कुछ हद तक बदल देगा। इसके अलावा, संसाधनों का उपयोग छोटे मूल्यों के लिए महत्वपूर्ण नहीं है 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}.$

गणना के मॉडल

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

नियतात्मक मॉडल

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

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

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

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

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

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

Main articles: Parallel computing and Distributed computing

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

पर गणना के लिए आवश्यक समय 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)).$ सामान्यता के नुकसान के बिना, कोई यह मान सकता है कि function 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