EITC/IS/CCTF कम्प्युटेशनल जटिलता सिद्धान्त आधारभूत

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

समय सबैभन्दा सामान्य रूपमा मानिने स्रोत हो। जब "जटिलता" शब्द क्वालिफायर बिना प्रयोग गरिन्छ, यसले सामान्यतया समयको जटिलतालाई जनाउँछ।

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

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

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

गणनाको क्रममा प्रयोग गरिएका पूर्णाङ्कहरूको आकार धेरै विधिहरूमा सीमित छैन, र अंकगणितीय सञ्चालनहरूलाई निश्चित समय चाहिन्छ भन्ने मान्न अवास्तविक छ। नतिजाको रूपमा, समय जटिलता, जसलाई बिट जटिलता पनि भनिन्छ, अंकगणितीय जटिलता भन्दा उल्लेखनीय रूपमा उच्च हुन सक्छ। nn पूर्णांक म्याट्रिक्सको निर्धारक गणना गर्ने अंकगणितीय कठिनाई, उदाहरणका लागि, मानक प्रविधिहरू (गौसियन उन्मूलन) को लागि O(n^3) हो। किनभने गुणांकको साइज गणनाको क्रममा घातीय रूपमा विस्तार हुन सक्छ, उही विधिहरूको बिट जटिलता n मा घातीय छ। यदि यी प्रविधिहरू बहु-मोड्युलर अंकगणितसँग संयोजनमा प्रयोग गरिन्छ भने, बिट जटिलतालाई O(n^4) मा घटाउन सकिन्छ।

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

स्रोत जुन प्राय: क्रमबद्ध र खोजीमा विचार गरिन्छ प्रविष्टिहरूको तुलनाको मात्रा हो। यदि डेटा राम्रोसँग व्यवस्थित गरिएको छ भने, यो समय जटिलताको राम्रो सूचक हो।

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

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

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

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

कम्प्यूटेशनल मोडेलहरू

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

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

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

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

यदि यस्तो गणना मोडेल हाल व्यावहारिक छैन भने पनि, यसको सैद्धान्तिक महत्त्व छ, विशेष गरी P = NP समस्याको सम्बन्धमा, जसले "बहुपद समय" र "गैर-निर्धारित बहुपद समय" को प्रयोग गरेर उत्पन्न जटिलता वर्गहरू कम्तिमा माथिल्लो रूपमा सोध्छ। सीमाहरू समान छन्। एक नियतात्मक कम्प्यूटरमा, NP-algorithm को अनुकरण गर्न "घातीय समय" चाहिन्छ। यदि कुनै कार्य गैर-निर्धारित प्रणालीमा बहुपद समयमा समाधान गर्न सकिन्छ भने, यो NP कठिनाई वर्गसँग सम्बन्धित छ। यदि कुनै मुद्दा NP मा छ र कुनै अन्य NP समस्या भन्दा सजिलो छैन भने, यसलाई NP-पूर्ण भनिन्छ। Knapsack समस्या, यात्रा विक्रेता समस्या, र बुलियन सन्तुष्टि समस्या सबै NP-पूर्ण संयोजन समस्याहरू हुन्। सबैभन्दा प्रसिद्ध एल्गोरिथ्ममा यी सबै समस्याहरूको लागि घातीय जटिलता छ। यदि यी मध्ये कुनै पनि समस्यालाई निर्धारक मेसिनमा बहुपदीय समयमा समाधान गर्न सकिन्छ भने, सबै NP समस्याहरू बहुपद समयमा पनि समाधान गर्न सकिन्छ, र P = NP स्थापना हुनेछ। 2017 को रूपमा, यो व्यापक रूपमा अनुमान गरिएको छ कि P NP, NP समस्याहरूको सबैभन्दा खराब अवस्थाहरू मौलिक रूपमा समाधान गर्न गाह्रो हुन्छ, अर्थात्, रोचक इनपुट लम्बाइ दिएका कुनै पनि सम्भाव्य समय अवधि (दशकहरू) भन्दा धेरै समय लाग्छ।

समानान्तर र वितरित कम्प्युटिङ

समानान्तर र वितरित कम्प्युटिङले धेरै प्रोसेसरहरूमा विभाजन गर्ने प्रक्रिया समावेश गर्दछ जुन सबै एकै समयमा सञ्चालन हुन्छन्। विभिन्न मोडेलहरू बीचको आधारभूत भिन्नता प्रोसेसरहरू बीच डाटा पठाउने विधि हो। प्रोसेसरहरू बीच डाटा प्रसारण सामान्यतया समानान्तर कम्प्युटिङमा धेरै छिटो हुन्छ, जबकि वितरित कम्प्युटिङमा प्रोसेसरहरू बीच डाटा स्थानान्तरण नेटवर्कमा गरिन्छ र यसरी पर्याप्त ढिलो हुन्छ।

N प्रोसेसरहरूमा गणना गर्दा यसले एकल प्रोसेसरमा लिने समयको N द्वारा भागफल लिन्छ। वास्तविकतामा, किनकि केही सबटास्कहरू समानान्तर हुन सक्दैनन् र केही प्रोसेसरहरूले अर्को प्रोसेसरबाट परिणामको लागि पर्खनु पर्ने हुन सक्छ, यो सैद्धान्तिक रूपमा आदर्श बाउन्ड कहिल्यै प्राप्त हुनेछैन।

मुख्य जटिलता मुद्दा भनेको एल्गोरिदमहरू विकास गर्नु हो ताकि प्रोसेसरहरूको संख्याद्वारा कम्प्युटिङ समयको उत्पादन एकल प्रोसेसरमा समान गणना गर्न आवश्यक समयको नजिक होस्।

क्वान्टम गणना

क्वान्टम कम्प्युटर भनेको क्वान्टम मेकानिक्समा आधारित गणना मोडेल भएको कम्प्युटर हो। चर्च–ट्युरिङ थेसिस क्वान्टम कम्प्युटरका लागि सत्य हो, जसको अर्थ क्वान्टम कम्प्युटरले समाधान गर्न सक्ने कुनै पनि समस्या ट्युरिङ मेसिनद्वारा पनि समाधान गर्न सकिन्छ। जे होस्, केही कार्यहरू सैद्धान्तिक रूपमा कम टेम्पोरल जटिलता भएको क्लासिकल कम्प्युटरको सट्टा क्वान्टम कम्प्युटर प्रयोग गरेर समाधान गर्न सकिन्छ। अहिलेको लागि, यो कडा सैद्धान्तिक छ, किनकि कसैलाई थाहा छैन कि कसरी व्यावहारिक क्वान्टम कम्प्युटर विकास गर्ने।

क्वान्टम कम्प्लेक्सिटी थ्योरी क्वान्टम कम्प्युटरहरूद्वारा समाधान गर्न सकिने बिभिन्न प्रकारका समस्याहरूको अनुसन्धान गर्नको लागि सिर्जना गरिएको थियो। यो पोस्ट-क्वान्टम क्रिप्टोग्राफीमा प्रयोग गरिन्छ, जुन क्वान्टम कम्प्युटर आक्रमणहरूको प्रतिरोधी क्रिप्टोग्राफिक प्रोटोकलहरू सिर्जना गर्ने प्रक्रिया हो।

समस्याको जटिलता (तल्लो सीमा)

समस्या समाधान गर्न सक्ने एल्गोरिदमका जटिलताहरू, पत्ता नलागेका प्रविधिहरू सहित, समस्याको जटिलता हो। नतिजाको रूपमा, समस्याको जटिलता कुनै पनि एल्गोरिदमको जटिलता बराबर हुन्छ जसले यसलाई समाधान गर्छ।

नतिजाको रूपमा, ठूलो ओ नोटेशनमा दिइएको कुनै पनि जटिलताले एल्गोरिदम र साथमा समस्या दुवैको जटिलतालाई प्रतिनिधित्व गर्दछ।

अर्कोतर्फ, मुद्दाको जटिलतामा अतुलनीय तल्लो सीमाहरू प्राप्त गर्न प्रायः गाह्रो हुन्छ, र त्यसो गर्नका लागि केही रणनीतिहरू छन्।

धेरैजसो समस्याहरू समाधान गर्नको लागि, सबै इनपुट डेटाहरू पढ्नु पर्छ, जसले डेटाको परिमाणको अनुपातमा समय लिन्छ। नतिजाको रूपमा, त्यस्ता समस्याहरूमा कम्तिमा रेखीय जटिलता हुन्छ, वा ठूलो ओमेगा नोटेशनमा, Ω(n) को जटिलता हुन्छ।

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

क्रमबद्ध गर्ने एल्गोरिदमको लागि आवश्यक तुलनाहरूको संख्यामा Ω(nlogn) को ननलाइनर तल्लो सीमा हुन्छ। नतिजाको रूपमा, उत्तम क्रमबद्ध एल्गोरिदमहरू सबैभन्दा कुशल छन् किनभने तिनीहरूको जटिलता O(nlogn) हो। त्यहाँ एन छन् भन्ने तथ्य! चीजहरू व्यवस्थित गर्ने तरिकाहरूले यो तल्लो सीमामा जान्छ। किनभने प्रत्येक तुलनाले n को यो सङ्ग्रहलाई विभाजन गर्छ! अर्डरलाई दुई टुक्रामा पार्नुहोस्, सबै अर्डरहरू छुट्याउन आवश्यक पर्ने N तुलनाहरूको संख्या 2N > n! हुनु पर्छ, स्टर्लिङको सूत्रद्वारा O(nlogn) लाई बुझाउँछ।

एउटा समस्यालाई अर्को समस्यामा घटाउनु कम जटिलता बाधाहरू प्राप्त गर्नको लागि साझा रणनीति हो।

एल्गोरिथ्म विकास

एल्गोरिदमको जटिलताको मूल्याङ्कन गर्नु डिजाइन प्रक्रियाको महत्त्वपूर्ण तत्व हो किनभने यसले अपेक्षित कार्यसम्पादनको बारेमा उपयोगी जानकारी प्रदान गर्दछ।

यो एक बारम्बार गलतफहमी हो कि, मूर को कानून को परिणाम को रूप मा, जो आधुनिक कम्प्यूटर शक्ति को घातीय वृद्धि को भविष्यवाणी गर्दछ, एल्गोरिदम को जटिलता को मूल्यांकन कम सान्दर्भिक हुनेछ। यो गलत छ किनभने बढेको पावरले ठूलो मात्रामा डाटा (ठूलो डाटा) प्रशोधन गर्न अनुमति दिन्छ। उदाहरणका लागि, कुनै पनि एल्गोरिदमले एक सेकेन्डभन्दा कम समयमा राम्रोसँग काम गर्नुपर्छ जब वर्णमाला क्रमबद्ध रूपमा केही सयौं प्रविष्टिहरूको सूची, जस्तै पुस्तकको ग्रन्थसूची। अर्कोतर्फ, एक मिलियन प्रविष्टिहरूको लागि (उदाहरणका लागि, ठूला सहरका फोन नम्बरहरू), आधारभूत एल्गोरिदमहरू जसलाई O(n2) तुलनाहरू आवश्यक पर्दछ, एक ट्रिलियन तुलनाहरू प्रदर्शन गर्नुपर्नेछ, जुन 10 को गतिमा तीन घण्टा लाग्नेछ। प्रति सेकेन्ड मिलियन तुलना। Quicksort र मर्ज क्रम, अर्कोतर्फ, केवल nlogn तुलनाहरू चाहिन्छ (पूर्वको लागि औसत-केस जटिलताको रूपमा, पछिल्लोको लागि सबैभन्दा खराब-केस जटिलताको रूपमा)। यसले n = 30,000,000 को लागि लगभग 1,000,000 तुलनाहरू उत्पादन गर्दछ, जसले प्रति सेकेन्ड 3 मिलियन तुलनामा 10 सेकेन्ड मात्र लिनेछ।

नतिजाको रूपमा, जटिलता मूल्याङ्कनले कार्यान्वयन गर्नु अघि धेरै असक्षम एल्गोरिदमहरू हटाउन अनुमति दिन सक्छ। यो पनि सबै सम्भावित भेरियन्टहरू परीक्षण नगरीकन जटिल एल्गोरिदमहरू ठीक-ट्यून गर्न प्रयोग गर्न सकिन्छ। जटिलताको अध्ययनले जटिल एल्गोरिदमको सबैभन्दा महँगो चरणहरू निर्धारण गरेर कार्यान्वयनको दक्षता बढाउनको लागि प्रयासलाई केन्द्रित गर्न अनुमति दिन्छ।