EITC/IS/CCTF कम्प्यूटेशनल कॉम्प्लेक्सिटी थ्योरी फंडामेंटल्स कंप्यूटर विज्ञान की नींव के सैद्धांतिक पहलुओं पर यूरोपीय आईटी प्रमाणन कार्यक्रम है जो इंटरनेट में व्यापक रूप से उपयोग किए जाने वाले शास्त्रीय असममित सार्वजनिक-कुंजी क्रिप्टोग्राफी का आधार भी है।
EITC/IS/CCTF कम्प्यूटेशनल कॉम्प्लेक्सिटी थ्योरी फंडामेंटल्स के पाठ्यक्रम में कंप्यूटर विज्ञान की नींव पर सैद्धांतिक ज्ञान और बुनियादी अवधारणाओं पर कम्प्यूटेशनल मॉडल शामिल हैं जैसे नियतात्मक और गैर-निर्धारिती परिमित राज्य मशीन, नियमित भाषाएं, संदर्भ मुक्त व्याकरण और भाषा सिद्धांत, ऑटोमेटा सिद्धांत, ट्यूरिंग इस ईआईटीसी प्रमाणन के संदर्भ के रूप में व्यापक वीडियो उपदेशात्मक सामग्री को शामिल करते हुए, निम्नलिखित संरचना के भीतर मूलभूत सुरक्षा अनुप्रयोगों के लिए मशीनों, समस्याओं की निर्णायकता, पुनरावृत्ति, तर्क और एल्गोरिथम की जटिलता।
एक एल्गोरिथ्म की कम्प्यूटेशनल जटिलता इसे संचालित करने के लिए आवश्यक संसाधनों की मात्रा है। समय और स्मृति संसाधनों पर विशेष ध्यान दिया जाता है। किसी समस्या की जटिलता को इसे हल करने के लिए सर्वोत्तम एल्गोरिदम की जटिलता के रूप में परिभाषित किया गया है। एल्गोरिदम का विश्लेषण स्पष्ट रूप से दिए गए एल्गोरिदम की जटिलता का अध्ययन है, जबकि कम्प्यूटेशनल जटिलता सिद्धांत सर्वोत्तम ज्ञात एल्गोरिदम के साथ समस्याओं के समाधान की जटिलता का अध्ययन है। दोनों डोमेन आपस में जुड़े हुए हैं क्योंकि एक एल्गोरिथ्म की जटिलता हमेशा उस समस्या की जटिलता पर एक ऊपरी बाधा होती है जिसे वह हल करती है। इसके अलावा, कुशल एल्गोरिदम का निर्माण करते समय हल की जाने वाली समस्या की जटिलता के लिए एक निश्चित एल्गोरिथ्म की जटिलता की तुलना करना अक्सर आवश्यक होता है। अधिकांश परिस्थितियों में, किसी समस्या की कठिनाई के बारे में उपलब्ध एकमात्र जानकारी यह है कि यह सबसे कुशल ज्ञात तकनीकों की जटिलता से कम है। नतीजतन, एल्गोरिथ्म विश्लेषण और जटिलता सिद्धांत के बीच बहुत अधिक ओवरलैप है।
जटिलता सिद्धांत न केवल कंप्यूटर विज्ञान के आधार के रूप में कम्प्यूटेशनल मॉडल की नींव में बल्कि शास्त्रीय असममित क्रिप्टोग्राफी (तथाकथित सार्वजनिक-कुंजी क्रिप्टोग्राफी) की नींव में भी महत्वपूर्ण भूमिका निभाता है, जो आधुनिक नेटवर्क में व्यापक रूप से प्रसारित होता है, खासकर इंटरनेट में। सार्वजनिक-कुंजी एन्क्रिप्शन कुछ असममित गणितीय समस्याओं के कम्प्यूटेशनल कठिन पर आधारित है, उदाहरण के लिए, इसके प्रमुख कारकों में बड़ी संख्या का गुणनखंडीकरण (यह ऑपरेशन जटिलता सिद्धांत वर्गीकरण में एक कठिन समस्या है, क्योंकि हल करने के लिए कुशल शास्त्रीय एल्गोरिदम ज्ञात नहीं हैं। यह समस्या के इनपुट आकार में वृद्धि के साथ बहुपद के बजाय बहुपद रूप से स्केलिंग संसाधनों के साथ है, जो मूल बड़ी संख्या देने के लिए ज्ञात प्रमुख कारकों को गुणा करने के एक बहुत ही सरल रिवर्स ऑपरेशन के विपरीत है)। सार्वजनिक कुंजी क्रिप्टोग्राफी की वास्तुकला में इस विषमता का उपयोग करना (सार्वजनिक कुंजी के बीच एक कम्प्यूटेशनल रूप से असममित संबंध को परिभाषित करके, जिसे आसानी से निजी कुंजी से गणना की जा सकती है, जबकि निजी कुंजी आसानी से सार्वजनिक कुंजी से कंप्यूटर नहीं हो सकती है, कोई भी सार्वजनिक रूप से कर सकता है सार्वजनिक कुंजी की घोषणा करें और अन्य संचार पक्षों को डेटा के असममित एन्क्रिप्शन के लिए इसका उपयोग करने में सक्षम करें, जिसे केवल युग्मित निजी कुंजी के साथ डिक्रिप्ट किया जा सकता है, तीसरे पक्ष के लिए कम्प्यूटेशनल रूप से उपलब्ध नहीं है, इस प्रकार संचार को सुरक्षित बनाता है)।
कम्प्यूटेशनल जटिलता सिद्धांत मुख्य रूप से कंप्यूटर विज्ञान और एल्गोरिथम अग्रदूतों की उपलब्धियों पर विकसित किया गया था, जैसे कि एलन ट्यूरिंग, जिसका काम नाजी जर्मनी के एनिग्मा सिफर को तोड़ने के लिए महत्वपूर्ण था, जिसने द्वितीय विश्व युद्ध जीतने वाले सहयोगियों में एक गहरी भूमिका निभाई थी। गुप्त जानकारी को उजागर करने के लिए डेटा (मुख्य रूप से एन्क्रिप्टेड संचार) का विश्लेषण करने की कम्प्यूटेशनल प्रक्रियाओं को तैयार करने और स्वचालित करने के उद्देश्य से क्रिप्टोग्राफ़िक सिस्टम का उल्लंघन करने और एन्क्रिप्टेड संचार की सामग्री तक पहुंच प्राप्त करने के लिए क्रिप्टोनालिसिस का उपयोग किया गया था, आमतौर पर सामरिक सैन्य महत्व का। यह क्रिप्टोएनालिसिस भी था जिसने पहले आधुनिक कंप्यूटरों के विकास को उत्प्रेरित किया (जो शुरू में कोडब्रेकिंग के रणनीतिक लक्ष्य के लिए लागू किए गए थे)। ब्रिटिश कोलोसस (पहले आधुनिक इलेक्ट्रॉनिक और प्रोग्राम कंप्यूटर के रूप में माना जाता है) पोलिश "बम" से पहले था, जो मैरियन रेजेवस्की द्वारा डिजाइन किया गया एक इलेक्ट्रॉनिक कम्प्यूटेशनल डिवाइस था, जो एनिग्मा सिफर को तोड़ने में सहायता करता था, और पोलिश खुफिया द्वारा ग्रेट ब्रिटेन को सौंप दिया गया था। 1939 में जर्मनी द्वारा पोलैंड पर आक्रमण करने के बाद कब्जा कर ली गई जर्मन एनिग्मा एन्क्रिप्शन मशीन। इस उपकरण के आधार पर एलन ट्यूरिंग ने जर्मन एन्क्रिप्टेड संचार को सफलतापूर्वक तोड़ने के लिए अपने अधिक उन्नत समकक्ष को विकसित किया, जिसे बाद में आधुनिक कंप्यूटरों में विकसित किया गया।
चूंकि एल्गोरिदम चलाने के लिए आवश्यक संसाधनों की मात्रा इनपुट के आकार के साथ भिन्न होती है, जटिलता आमतौर पर फ़ंक्शन f (n) के रूप में व्यक्त की जाती है, जहां n इनपुट आकार होता है और f (n) या तो सबसे खराब स्थिति होती है ( आकार n के सभी इनपुट के लिए आवश्यक संसाधनों की अधिकतम मात्रा) या औसत-केस जटिलता (आकार n के सभी इनपुट पर संसाधनों की मात्रा का औसत)। आकार n के इनपुट पर आवश्यक प्राथमिक संचालन की संख्या को आमतौर पर समय जटिलता के रूप में कहा जाता है, जहां प्राथमिक संचालन के बारे में माना जाता है कि किसी विशेष कंप्यूटर पर निरंतर समय लगता है और एक अलग मशीन पर चलने पर केवल एक स्थिर कारक द्वारा बदलता है। आकार n के इनपुट पर एक एल्गोरिथ्म द्वारा आवश्यक मेमोरी की मात्रा को अंतरिक्ष जटिलता के रूप में जाना जाता है।
समय सबसे अधिक माना जाने वाला संसाधन है। जब "जटिलता" शब्द का प्रयोग योग्यता के बिना किया जाता है, तो यह आमतौर पर समय की जटिलता को संदर्भित करता है।
समय की पारंपरिक इकाइयाँ (सेकंड, मिनट, और इसी तरह) जटिलता सिद्धांत में नियोजित नहीं हैं क्योंकि वे चुने हुए कंप्यूटर और प्रौद्योगिकी की उन्नति पर बहुत अधिक निर्भर हैं। उदाहरण के लिए, एक कंप्यूटर आज 1960 के दशक के कंप्यूटर की तुलना में एक एल्गोरिथ्म को काफी तेजी से निष्पादित कर सकता है, फिर भी, यह एल्गोरिथम की अंतर्निहित गुणवत्ता के बजाय कंप्यूटर हार्डवेयर में तकनीकी सफलताओं के कारण है। जटिलता सिद्धांत का लक्ष्य एल्गोरिदम की अंतर्निहित समय की जरूरतों को मापना है, या मौलिक समय सीमाएं जो किसी भी कंप्यूटर पर एक एल्गोरिदम लागू करेगा। यह गणना करके पूरा किया जाता है कि गणना के दौरान कितने बुनियादी संचालन किए जाते हैं। इन प्रक्रियाओं को आमतौर पर चरणों के रूप में संदर्भित किया जाता है क्योंकि उन्हें एक विशेष मशीन पर निरंतर समय लेने के लिए माना जाता है (यानी, वे इनपुट की मात्रा से अप्रभावित होते हैं)।
एक अन्य महत्वपूर्ण संसाधन एल्गोरिदम को निष्पादित करने के लिए आवश्यक कंप्यूटर मेमोरी की मात्रा है।
एक और अक्सर इस्तेमाल किया जाने वाला संसाधन अंकगणितीय संचालन की मात्रा है। इस परिदृश्य में, "अंकगणितीय जटिलता" शब्द का प्रयोग किया जाता है। समय जटिलता आम तौर पर एक स्थिर कारक द्वारा अंकगणितीय जटिलता का उत्पाद है यदि गणना के दौरान होने वाली संख्याओं के द्विआधारी प्रतिनिधित्व के आकार पर ऊपरी बाधा ज्ञात है।
गणना के दौरान उपयोग किए गए पूर्णांकों का आकार कई विधियों के लिए बाध्य नहीं है, और यह मान लेना अवास्तविक है कि अंकगणितीय संचालन के लिए निश्चित समय की आवश्यकता होती है। नतीजतन, समय जटिलता, जिसे बिट जटिलता भी कहा जाता है, अंकगणितीय जटिलता से काफी अधिक हो सकती है। उदाहरण के लिए, एनएन पूर्णांक मैट्रिक्स के निर्धारक की गणना करने की अंकगणितीय कठिनाई मानक तकनीकों (गॉसियन उन्मूलन) के लिए ओ (एन ^ 3) है। क्योंकि गणना के दौरान गुणांक का आकार तेजी से बढ़ सकता है, उसी विधियों की बिट जटिलता n में घातीय है। यदि इन तकनीकों का उपयोग बहु-मॉड्यूलर अंकगणित के संयोजन में किया जाता है, तो बिट जटिलता को O(n^4) तक घटाया जा सकता है।
औपचारिक शब्दों में, बिट जटिलता, एल्गोरिथम चलाने के लिए आवश्यक बिट्स पर संचालन की संख्या को संदर्भित करती है। यह अधिकांश गणना प्रतिमानों में एक स्थिर कारक तक अस्थायी जटिलता के बराबर है। कंप्यूटर द्वारा आवश्यक मशीनी शब्दों पर संचालन की संख्या बिट जटिलता के समानुपाती होती है। गणना के यथार्थवादी मॉडल के लिए, समय जटिलता और बिट जटिलता इस प्रकार समान हैं।
जिस संसाधन को अक्सर छँटाई और खोज में माना जाता है वह प्रविष्टियों की तुलना की मात्रा है। यदि डेटा अच्छी तरह से व्यवस्थित है, तो यह समय की जटिलता का एक अच्छा संकेतक है।
सभी संभावित इनपुट पर, एल्गोरिदम में चरणों की संख्या की गणना करना असंभव है। क्योंकि इनपुट की जटिलता इसके आकार के साथ बढ़ती है, इसे आमतौर पर इनपुट के आकार n (बिट्स में) के एक फ़ंक्शन के रूप में दर्शाया जाता है, और इसलिए जटिलता n का एक फ़ंक्शन है। समान आकार के इनपुट के लिए, हालांकि, एल्गोरिदम की जटिलता काफी भिन्न हो सकती है। नतीजतन, विभिन्न जटिलता कार्यों को नियमित रूप से नियोजित किया जाता है।
सबसे खराब स्थिति जटिलता सभी आकार एन इनपुट के लिए सभी जटिलताओं का योग है, जबकि औसत-केस जटिलता सभी आकार एन इनपुट के लिए सभी जटिलताओं का योग है (यह समझ में आता है, क्योंकि किसी दिए गए आकार के संभावित इनपुट की संख्या है परिमित)। जब शब्द "जटिलता" का उपयोग आगे परिभाषित किए बिना किया जाता है, तो सबसे खराब स्थिति समय जटिलता को ध्यान में रखा जाता है।
सबसे खराब और औसत-मामले की जटिलता की सही गणना करना बेहद मुश्किल है। इसके अलावा, इन सटीक मूल्यों का व्यावहारिक अनुप्रयोग बहुत कम है क्योंकि मशीन या गणना प्रतिमान में कोई भी बदलाव जटिलता को थोड़ा बदल देगा। इसके अलावा, n के छोटे मूल्यों के लिए संसाधन उपयोग महत्वपूर्ण नहीं है, इसलिए कार्यान्वयन में आसानी अक्सर छोटे n के लिए कम जटिलता की तुलना में अधिक आकर्षक होती है।
इन कारणों से, उच्च n के लिए जटिलता के व्यवहार पर सबसे अधिक ध्यान दिया जाता है, अर्थात, इसका स्पर्शोन्मुख व्यवहार n के रूप में अनंत तक पहुंचता है। नतीजतन, जटिलता को इंगित करने के लिए आमतौर पर बड़े ओ नोटेशन का उपयोग किया जाता है।
कम्प्यूटेशनल मॉडल
एक गणना मॉडल का चुनाव, जिसमें समय की एक इकाई में किए जाने वाले आवश्यक संचालन को निर्दिष्ट करना शामिल है, जटिलता को निर्धारित करने में महत्वपूर्ण है। इसे कभी-कभी मल्टीटेप ट्यूरिंग मशीन के रूप में संदर्भित किया जाता है जब गणना प्रतिमान विशेष रूप से वर्णित नहीं होता है।
गणना का एक नियतात्मक मॉडल वह है जिसमें मशीन के बाद के राज्यों और किए जाने वाले कार्यों को पूरी तरह से पिछली स्थिति द्वारा परिभाषित किया जाता है। रिकर्सिव फ़ंक्शंस, लैम्ब्डा कैलकुलस और ट्यूरिंग मशीन पहले नियतात्मक मॉडल थे। रैंडम-एक्सेस मशीन (जिसे रैम-मशीन भी कहा जाता है) वास्तविक दुनिया के कंप्यूटरों के अनुकरण के लिए एक लोकप्रिय प्रतिमान है।
जब गणना मॉडल को परिभाषित नहीं किया जाता है, तो आमतौर पर एक मल्टीटेप ट्यूरिंग मशीन मान ली जाती है। मल्टीटेप ट्यूरिंग मशीनों पर, अधिकांश एल्गोरिदम के लिए रैम मशीनों पर समय की जटिलता समान होती है, हालांकि इस समानता को प्राप्त करने के लिए मेमोरी में डेटा को कैसे संग्रहीत किया जाता है, इस पर काफी ध्यान देने की आवश्यकता हो सकती है।
कंप्यूटिंग के गैर-नियतात्मक मॉडल में गणना के कुछ चरणों में विभिन्न विकल्प बनाए जा सकते हैं, जैसे कि गैर-नियतात्मक ट्यूरिंग मशीन। जटिलता सिद्धांत में, सभी व्यवहार्य विकल्पों पर एक ही समय में विचार किया जाता है, और गैर-नियतात्मक समय जटिलता उस समय की मात्रा होती है जब सर्वोत्तम विकल्प हमेशा बनाए जाते हैं। इसे दूसरे तरीके से रखने के लिए, संगणना आवश्यक रूप से कई (समान) प्रोसेसर पर समवर्ती रूप से की जाती है, और गैर-नियतात्मक गणना समय गणना को पूरा करने के लिए पहले प्रोसेसर द्वारा लिया गया समय है। उदाहरण के लिए शोर के छोटे पूर्णांकों के गुणन जैसे विशेष क्वांटम एल्गोरिदम को चलाते समय सुपरपोज़्ड उलझी हुई अवस्थाओं का उपयोग करके क्वांटम कंप्यूटिंग में इस समानता का उपयोग किया जा सकता है।
यहां तक कि अगर ऐसा गणना मॉडल वर्तमान में व्यावहारिक नहीं है, तो इसका सैद्धांतिक महत्व है, विशेष रूप से पी = एनपी समस्या के संबंध में, जो पूछता है कि क्या "बहुपद समय" और "गैर-नियतात्मक बहुपद समय" का उपयोग करके उत्पन्न जटिलता वर्ग कम से कम ऊपरी सीमाएँ समान हैं। नियतात्मक कंप्यूटर पर, एनपी-एल्गोरिदम का अनुकरण करने के लिए "घातीय समय" की आवश्यकता होती है। यदि कोई कार्य गैर-नियतात्मक प्रणाली पर बहुपद समय में हल किया जा सकता है, तो यह एनपी कठिनाई वर्ग के अंतर्गत आता है। यदि कोई समस्या एनपी में है और किसी अन्य एनपी समस्या से आसान नहीं है, तो इसे एनपी-पूर्ण कहा जाता है। नैकपैक समस्या, यात्रा विक्रेता समस्या, और बूलियन संतुष्टि समस्या सभी एनपी-पूर्ण संयोजन संबंधी समस्याएं हैं। इन सभी समस्याओं के लिए सबसे प्रसिद्ध एल्गोरिथम में घातीय जटिलता है। यदि इनमें से किसी भी मुद्दे को एक नियतात्मक मशीन पर बहुपद समय में हल किया जा सकता है, तो सभी एनपी समस्याओं को बहुपद समय में भी हल किया जा सकता है, और पी = एनपी स्थापित किया जाएगा। 2017 तक, यह व्यापक रूप से माना जाता है कि पी एनपी, जिसका अर्थ है कि एनपी समस्याओं की सबसे खराब परिस्थितियों को हल करना मौलिक रूप से कठिन है, यानी दिलचस्प इनपुट लंबाई को देखते हुए किसी भी व्यवहार्य समय अवधि (दशकों) से कहीं अधिक समय लगता है।
समानांतर और वितरित कंप्यूटिंग
समानांतर और वितरित कंप्यूटिंग में कई प्रोसेसर में प्रसंस्करण को विभाजित करना शामिल है जो सभी एक ही समय में संचालित होते हैं। विभिन्न मॉडलों के बीच मूलभूत अंतर प्रोसेसर के बीच डेटा भेजने की विधि है। प्रोसेसर के बीच डेटा ट्रांसमिशन आमतौर पर समानांतर कंप्यूटिंग में बहुत तेज होता है, जबकि वितरित कंप्यूटिंग में प्रोसेसर के बीच डेटा ट्रांसफर एक नेटवर्क पर किया जाता है और इस प्रकार यह काफी धीमा होता है।
एन प्रोसेसर पर एक संगणना एक प्रोसेसर पर लगने वाले समय के एन द्वारा कम से कम भागफल लेती है। वास्तव में, क्योंकि कुछ उप-कार्य समानांतर नहीं किए जा सकते हैं और कुछ प्रोसेसर को किसी अन्य प्रोसेसर से परिणाम की प्रतीक्षा करने की आवश्यकता हो सकती है, यह सैद्धांतिक रूप से आदर्श सीमा कभी प्राप्त नहीं होगी।
इस प्रकार प्रमुख जटिलता मुद्दा एल्गोरिदम विकसित करना है ताकि प्रोसेसर की संख्या से कंप्यूटिंग समय का उत्पाद एक ही प्रोसेसर पर समान गणना करने के लिए आवश्यक समय के जितना करीब हो सके।
क्वांटम गणना
एक क्वांटम कंप्यूटर एक क्वांटम यांत्रिकी-आधारित गणना मॉडल वाला कंप्यूटर है। चर्च-ट्यूरिंग थीसिस क्वांटम कंप्यूटरों के लिए सही है, जिसका अर्थ है कि कोई भी मुद्दा जिसे क्वांटम कंप्यूटर हल कर सकता है उसे ट्यूरिंग मशीन द्वारा भी हल किया जा सकता है। हालांकि, कुछ कार्यों को सैद्धांतिक रूप से काफी कम अस्थायी जटिलता वाले शास्त्रीय कंप्यूटर के बजाय क्वांटम कंप्यूटर का उपयोग करके हल किया जा सकता है। कुछ समय के लिए, यह सख्ती से सैद्धांतिक है, क्योंकि कोई नहीं जानता कि व्यावहारिक क्वांटम कंप्यूटर कैसे विकसित किया जाए।
क्वांटम जटिलता सिद्धांत विभिन्न प्रकार के मुद्दों की जांच के लिए बनाया गया था जिन्हें क्वांटम कंप्यूटर द्वारा हल किया जा सकता है। इसका उपयोग पोस्ट-क्वांटम क्रिप्टोग्राफी में किया जाता है, जो कि क्रिप्टोग्राफिक प्रोटोकॉल बनाने की प्रक्रिया है जो क्वांटम कंप्यूटर हमलों के लिए प्रतिरोधी हैं।
समस्या की जटिलता (निचली सीमा)
अनदेखे तकनीकों सहित समस्या को हल करने वाले एल्गोरिदम की जटिलताएं समस्या की जटिलता है। नतीजतन, किसी समस्या की जटिलता किसी भी एल्गोरिदम की जटिलता के बराबर होती है जो इसे हल करती है।
नतीजतन, बड़े ओ नोटेशन में दी गई कोई भी जटिलता एल्गोरिदम और साथ की समस्या दोनों की जटिलता का प्रतिनिधित्व करती है।
दूसरी ओर, मुद्दे की जटिलता पर गैर-तुच्छ निचली सीमा प्राप्त करना अक्सर मुश्किल होता है, और ऐसा करने के लिए कुछ रणनीतियाँ हैं।
अधिकांश मुद्दों को हल करने के लिए, सभी इनपुट डेटा को पढ़ा जाना चाहिए, जिसमें डेटा के परिमाण के अनुपात में समय लगता है। नतीजतन, ऐसी समस्याओं में कम से कम रैखिक जटिलता होती है, या, बड़े ओमेगा संकेतन में, (n) की जटिलता होती है।
कुछ समस्याओं, जैसे कि कंप्यूटर बीजगणित और कम्प्यूटेशनल बीजगणितीय ज्यामिति में, बहुत बड़े समाधान हैं। क्योंकि आउटपुट लिखा जाना चाहिए, जटिलता आउटपुट के अधिकतम आकार से विवश है।
छँटाई एल्गोरिथ्म के लिए आवश्यक तुलनाओं की संख्या में (nlogn) की एक गैर-रेखीय निचली सीमा होती है। नतीजतन, सबसे अच्छा छँटाई एल्गोरिदम सबसे कुशल हैं क्योंकि उनकी जटिलता O (nlogn) है। तथ्य यह है कि n हैं! n चीजों को व्यवस्थित करने के तरीके इस निचली सीमा की ओर ले जाते हैं। क्योंकि प्रत्येक तुलना n के इस संग्रह को विभाजित करती है! ऑर्डर को दो भागों में बांटते हैं, सभी ऑर्डर में अंतर करने के लिए आवश्यक N तुलनाओं की संख्या 2N > n! होनी चाहिए, जिसका अर्थ है स्टर्लिंग के सूत्र द्वारा O(nlogn)।
कम जटिलता बाधाओं को प्राप्त करने के लिए एक समस्या को दूसरी समस्या में कम करना एक सामान्य रणनीति है।
एल्गोरिथम विकास
एल्गोरिथम की जटिलता का मूल्यांकन डिजाइन प्रक्रिया का एक महत्वपूर्ण तत्व है क्योंकि यह अपेक्षित प्रदर्शन के बारे में उपयोगी जानकारी प्रदान करता है।
यह एक बार-बार की जाने वाली गलतफहमी है कि मूर के कानून के परिणामस्वरूप, जो आधुनिक कंप्यूटर शक्ति के घातीय विकास की भविष्यवाणी करता है, एल्गोरिदम की जटिलता का मूल्यांकन कम प्रासंगिक हो जाएगा। यह गलत है क्योंकि बढ़ी हुई शक्ति बड़ी मात्रा में डेटा (बड़े डेटा) के प्रसंस्करण की अनुमति देती है। उदाहरण के लिए, किसी भी एल्गोरिथम को एक सेकंड से भी कम समय में अच्छी तरह से काम करना चाहिए, जब वर्णानुक्रम में कुछ सैकड़ों प्रविष्टियों की सूची को क्रमबद्ध किया जाता है, जैसे कि किसी पुस्तक की ग्रंथ सूची। दूसरी ओर, दस लाख प्रविष्टियों (उदाहरण के लिए, एक बड़े शहर के फोन नंबर) के लिए, मूल एल्गोरिदम जिनके लिए ओ (एन 2) तुलना की आवश्यकता होती है, उन्हें एक ट्रिलियन तुलना करना होगा, जिसमें 10 की गति से तीन घंटे लगेंगे। प्रति सेकंड मिलियन तुलना। दूसरी ओर, क्विकॉर्ट और मर्ज सॉर्ट, केवल nlogn तुलना की आवश्यकता होती है (पूर्व के लिए औसत-केस जटिलता के रूप में, बाद के लिए सबसे खराब स्थिति जटिलता के रूप में)। यह n = 30,000,000 के लिए लगभग 1,000,000 तुलना उत्पन्न करता है, जो प्रति सेकंड 3 मिलियन तुलनाओं पर केवल 10 सेकंड लेता है।
नतीजतन, जटिलता का आकलन कार्यान्वयन से पहले कई अक्षम एल्गोरिदम को समाप्त करने की अनुमति दे सकता है। इसका उपयोग सभी संभावित रूपों का परीक्षण किए बिना जटिल एल्गोरिदम को ठीक करने के लिए भी किया जा सकता है। जटिलता का अध्ययन एक जटिल एल्गोरिदम के सबसे महंगे चरणों को निर्धारित करके कार्यान्वयन की दक्षता बढ़ाने के प्रयास पर ध्यान केंद्रित करने की अनुमति देता है।
प्रमाणीकरण पाठ्यक्रम के बारे में विस्तार से जानने के लिए आप नीचे दी गई तालिका का विस्तार और विश्लेषण कर सकते हैं।
EITC/IS/CCTF कम्प्यूटेशनल कॉम्प्लेक्सिटी थ्योरी फंडामेंटल सर्टिफिकेशन करिकुलम एक वीडियो फॉर्म में ओपन-एक्सेस डिडक्टिक सामग्री का संदर्भ देता है। सीखने की प्रक्रिया प्रासंगिक पाठ्यचर्या भागों को शामिल करते हुए चरण-दर-चरण संरचना (कार्यक्रम -> पाठ -> विषय) में विभाजित है। डोमेन विशेषज्ञों के साथ असीमित परामर्श भी प्रदान किया जाता है।
प्रमाणन प्रक्रिया की जांच के विवरण के लिए यह किस प्रकार काम करता है?.
प्राथमिक सहायक पाठ्यचर्या पठन सामग्री
एस. अरोड़ा, बी. बराक, कम्प्यूटेशनल जटिलता: एक आधुनिक दृष्टिकोण
https://theory.cs.princeton.edu/complexity/book.pdf
माध्यमिक सहायक पाठ्यचर्या पठन सामग्री
ओ गोल्डरेइच, जटिलता सिद्धांत का परिचय:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
असतत गणित पर सहायक पाठ्यचर्या पठन सामग्री
जे। एस्पनेस, असतत गणित पर नोट्स:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
ग्राफ सिद्धांत पर सहायक पाठ्यचर्या पठन सामग्री
आर डायस्टेल, ग्राफ थ्योरी:
https://diestel-graph-theory.com/
EITC/IS/CCTF कम्प्यूटेशनल कॉम्प्लेक्सिटी थ्योरी फंडामेंटल प्रोग्राम के लिए संपूर्ण ऑफ़लाइन स्व-शिक्षण तैयारी सामग्री को एक पीडीएफ फ़ाइल में डाउनलोड करें।
ईआईटीसी/आईएस/सीसीटीएफ प्रारंभिक सामग्री - मानक संस्करण
ईआईटीसी/आईएस/सीसीटीएफ प्रारंभिक सामग्री - समीक्षा प्रश्नों के साथ विस्तारित संस्करण