समय की जटिलता: Difference between revisions

चूंकि एल्गोरिदम का चलने का समय ही आकार के विभिन्न इनपुट के बीच भिन्न हो सकता है, इसलिए सामान्यतः [[सबसे खराब स्थिति जटिलता|सबसे व्यर्थ स्थिति जटिलता]] पर विचार किया जाता है, जो किसी दिए गए आकार के इनपुट के लिए आवश्यक अधिकतम समय है। कम सामान्य, और सामान्यतः स्पष्ट रूप से निर्दिष्ट, औसत-केस जटिलता है, जो किसी दिए गए आकार के इनपुट पर लिए गए समय का औसत है (यह समझ में आता है क्योंकि किसी दिए गए आकार के संभावित इनपुट की केवल सीमित संख्या होती है)। दोनों ही स्थितियों में, समय जटिलता सामान्यतः इनपुट के आकार के [[फ़ंक्शन (गणित)|फलन (गणित)]] के रूप में व्यक्त की जाती है।<ref name="Sipser" />{{RP|226}} चूंकि इस फलन की स्पष्ट गणना करना सामान्यतः कठिन होता है, और छोटे इनपुट के लिए चलने का समय सामान्यतः परिणामी नहीं होता है, सामान्यतः इनपुट आकार बढ़ने पर जटिलता के व्यवहार पर ध्यान केंद्रित किया जाता है अर्थात, जटिलता का [[स्पर्शोन्मुख विश्लेषण]] इसलिए, समय जटिलता सामान्यतः [[बड़ा ओ अंकन]] का उपयोग करके व्यक्त की जाती है {{nowrap|<math>O(n)</math>,}} {{nowrap|<math>O(n\log n)</math>,}} {{nowrap|<math>O(n^\alpha)</math>,}} {{nowrap|<math>O(2^n)</math>,}} आदि, जहाँ {{mvar|n}} इनपुट का प्रतिनिधित्व करने के लिए आवश्यक [[ अंश | अंश]] की इकाइयों में आकार है।

एल्गोरिथम जटिलताओं को बड़े ओ नोटेशन में दिखाई देने वाले फलन के प्रकार के अनुसार वर्गीकृत किया गया है। उदाहरण के लिए, समय जटिलता वाला एल्गोरिदम <math>O(n)</math> रैखिक समय एल्गोरिथ्म और समय जटिलता वाला एल्गोरिदम <math>O(n^\alpha)</math> है कुछ स्थिरांक के लिए <math>\alpha > 1</math> बहुपद समय एल्गोरिथ्म है।

की गणना {{math|(−1){{sup|''n''}}}}

चूँकि ऐसे एल्गोरिदम को पूरे इनपुट को पढ़े बिना उत्तर देना होता है, इसका विवरण अधिक सीमा तक इनपुट तक पहुंच की अनुमति पर निर्भर करता है। सामान्यतः इनपुट के लिए जिसे बाइनरी स्ट्रिंग <math>b_1, ..., b_k</math> के रूप में दर्शाया जाता है यह माना जाता है कि एल्गोरिदम समय में हो सकता है <math>O(1)</math> अनुरोध करें और इसका मूल्य प्राप्त करें <math>b_i</math> किसी {{mvar|i}} के लिए होता है .

रैखिक समय उन स्थितियों में सर्वोत्तम संभव समय जटिलता है जहां एल्गोरिदम को क्रमिक रूप से अपने संपूर्ण इनपुट को पढ़ना होता है। इसलिए, रैखिक समय या, कम से कम, लगभग रैखिक समय प्रदर्शित करने वाले एल्गोरिदम की खोज में बहुत अधिक शोध का निवेश किया गया है। इस शोध में सॉफ्टवेयर और हार्डवेयर दोनों विधि सम्मिलित हैं। ऐसी कई हार्डवेयर प्रौद्योगिकियाँ हैं जो इसे प्रदान करने के लिए [[समानांतर कंप्यूटिंग]] का उपयोग करती हैं। उदाहरण [[ सामग्री-पता योग्य स्मृति ]] है। रैखिक समय की इस अवधारणा का उपयोग बॉयर-मूर स्ट्रिंग-खोज एल्गोरिदम और उक्कोनेन के एल्गोरिदम जैसे स्ट्रिंग मिलान एल्गोरिदम में किया जाता है।

कहा जाता है कि एल्गोरिदम क्वासिलिनियर टाइम <math>T(n)=O(n\log^kn)</math> (जिसे लॉग-लीनियर टाइम भी कहा जाता है) में चलता है कुछ सकारात्मक स्थिरांक के लिए {{mvar|k}}; <ref>{{cite journal | last1 = Naik | first1 = Ashish V. | last2 = Regan | first2 = Kenneth W. | last3 = Sivakumar | first3 = D. | doi = 10.1016/0304-3975(95)00031-Q | issue = 2 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]] | mr = 1355592 | pages = 325–349 | title = क्वासिलिनियर-टाइम जटिलता सिद्धांत पर| url = http://www.cse.buffalo.edu/~regan/papers/pdf/NRS95.pdf | volume = 148 | year = 1995| doi-access = free }}</ref> रैखिक अंकीय समय <math>k=1</math> स्थिति है .<ref>{{cite book | last1 = Sedgewick | first1 = Robert | last2 = Wayne | first2 = Kevin | edition = 4th | page = 186 | publisher = Pearson Education | title = एल्गोरिदम| url = https://algs4.cs.princeton.edu/home/ | year = 2011}}</ref> [[नरम ओ अंकन|सॉफ्ट ओ अंकन]] का उपयोग करते हुए ये एल्गोरिदम हैं <math>\tilde{O}(n)</math>. क्वासिलिनियर टाइम एल्गोरिदम भी हैं <math>O(n^{1+\varepsilon })</math> प्रत्येक स्थिरांक के लिए <math>\varepsilon >0</math> और इस प्रकार किसी भी बहुपद समय एल्गोरिदम की तुलना में तेज़ चलता है जिसकी समय सीमा में पद सम्मिलित होता है <math>n^c</math> किसी के लिए <math>c>1</math>.

* [[जल्दी से सुलझाएं|त्वरित वर्गीकरण]], <math>O(n\log n)</math>, इसके यादृच्छिक संस्करण में, चलने का समय <math>O(n\log n)</math> होता है सबसे व्यर्थ स्थिति वाले इनपुट की अपेक्षा में। इसके गैर-यादृच्छिक संस्करण <math>O(n\log n)</math> में है औसत स्थिति की जटिलता पर विचार करते समय ही चलने का समय है।

* [[ढेर बनाएं और छांटें|हीपसॉर्ट]], <math>O(n\log n)</math>, सबसे व्यर्थ स्थिति में [[ मर्ज़ सॉर्ट ]], [[परिचय]], बाइनरी ट्री सॉर्ट, [[स्मूथसॉर्ट]], धैर्य सॉर्टिंग आदि

कई स्थितियों में, <math>O(n\log n)</math> रनिंग टाइम केवल प्रदर्शन का परिणाम <math>\Theta (\log n)</math> है फलन {{mvar|n}} बार (नोटेशन के लिए, देखें {{slink|बिग ओ नोटेशन|बैचमैन-लैंडौ नोटेशन का वर्ग}}). उदाहरण के लिए, [[बाइनरी ट्री सॉर्ट]] प्रत्येक तत्व को सम्मिलित करके बाइनरी ट्री बनाता है {{mvar|n}}-आकार की सरणी एक-एक करके चूँकि एक [[ स्व-संतुलन द्विआधारी खोज वृक्ष ]] पर इन्सर्ट संचालन <math>O(\log n)</math> समय होता है  संपूर्ण एल्गोरिदम <math>O(n\log n)</math> समय लेता है

तुलनात्मक प्रकारों के लिए कम से कम <math>\Omega (n\log n)</math> आवश्यकता होती है सबसे व्यर्थ स्थिति में तुलना क्योंकि <math>\log (n!)=\Theta (n\log n)</math>, स्टर्लिंग के अनुमान से वे बार-बार [[पुनरावृत्ति संबंध]] से भी उत्पन्न होते हैं <math display="inline">T(n) = 2T\left(\frac{n}{2}\right)+O(n)</math>.

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

* n पूर्णांकों पर चयन सॉर्ट सॉर्टिंग एल्गोरिदम <math>An^2</math> निष्पादित करता है कुछ स्थिरांक A के लिए संचालन इस प्रकार यह समय <math>O(n^2)</math> में चलता है और बहुपद-समय एल्गोरिथ्म है।

इन दो गुणों वाले किसी भी एल्गोरिदम को [[ट्यूरिंग मशीन]] पर अंकगणितीय संचालन करने के लिए उपयुक्त एल्गोरिदम द्वारा अंकगणितीय संचालन को प्रतिस्थापित करके बहुपद समय एल्गोरिदम में परिवर्तित किया जा सकता है। दूसरा नियम अत्यंत आवश्यक है: पूर्णांक <math>2^n</math> दिया गया है (जो ट्यूरिंग मशीन मॉडल में n के समानुपाती स्थान लेता है), इसकी <math>2^{2^n}</math> गणना करना संभव है दोहराए गए वर्ग का उपयोग करके n गुणन के साथ। चूँकि, <math>2^{2^n}</math> स्थान प्रतिनिधित्व करता था के लिए आनुपातिक <math>2^n</math> है , और इस प्रकार इनपुट का प्रतिनिधित्व करने के लिए उपयोग किए जाने वाले स्थान में बहुपद के अतिरिक्त घातांकीय होता है। इसलिए, ट्यूरिंग मशीन पर बहुपद समय में यह गणना करना संभव नहीं है, किन्तु बहुपद रूप से कई अंकगणितीय परिचालनों द्वारा इसकी गणना करना संभव है।

अर्ध-बहुपद समय एल्गोरिदम सामान्यतः एक [[ एनपी कठिन ]] समस्या से दूसरी समस्या में [[कमी (जटिलता)]] में उत्पन्न होते हैं। उदाहरण के लिए, कोई एनपी हार्ड समस्या का उदाहरण ले सकता है, जैसे [[बूलियन संतुष्टि समस्या]], और इसे किसी अन्य समस्या बी के उदाहरण में परिवर्तित कर सकता है, किन्तु उदाहरण <math>2^{O(\log^c n)}</math> का आकार बन जाता है . उस स्थिति में, यह कमी यह सिद्ध नहीं करती है कि समस्या बी एनपी-हार्ड है; यह कमी केवल यह दर्शाती है कि B के लिए कोई बहुपद समय एल्गोरिथ्म नहीं है जब तक कि 3एसएटी (और इस प्रकार सभी एनपी (जटिलता)) के लिए अर्ध-बहुपद समय एल्गोरिथ्म नहीं है। इसी तरह, कुछ समस्याएं हैं जिनके लिए हम अर्ध-बहुपद समय एल्गोरिदम जानते हैं, किन्तु कोई बहुपद समय एल्गोरिदम ज्ञात नहीं है। ऐसी समस्याएँ सन्निकटन एल्गोरिदम में उत्पन्न होती हैं; प्रसिद्ध उदाहरण निर्देशित स्टीनर वृक्ष समस्या है, जिसके लिए अर्ध-बहुपद समय सन्निकटन एल्गोरिथ्म है जो सन्निकटन कारक प्राप्त करता है <math>O(\log^3 n)</math> (n शीर्षों की संख्या है), किन्तु ऐसे बहुपद समय एल्गोरिथ्म का अस्तित्व दिखाना खुली समस्या है।

अर्ध-बहुपद समय समाधानों के साथ अन्य कम्प्यूटेशनल समस्याओं, किन्तु कोई ज्ञात बहुपद समय समाधान में [[ लगाया हुआ गुट ]] समस्या सम्मिलित नहीं है, जिसमें लक्ष्य क्लिक और [[यादृच्छिक ग्राफ]] के मिलन में क्लिक समस्या को हल करना है। यद्यपि अर्ध-बहुपद रूप से हल करने योग्य, यह अनुमान लगाया गया है कि प्लांटेड क्लिक समस्या का कोई बहुपद समय समाधान नहीं है; इस लगाए गए क्लिक अनुमान का उपयोग कम्प्यूटेशनल गेम सिद्धांत, प्रोपर्टी परीक्षण और [[ यंत्र अधिगम ]] में कई अन्य समस्याओं की कठिनाई को सिद्ध करने के लिए [[कम्प्यूटेशनल कठोरता धारणा]] के रूप में किया गया है।<ref>{{cite conference | last1 = Braverman | first1 = Mark | author1-link = Mark Braverman (mathematician) | last2 = Kun-Ko | first2 = Young | last3 = Rubinstein | first3 = Aviad | last4 = Weinstein | first4 = Omri | editor-last = Klein | editor-first = Philip N. | arxiv = 1504.08352 | contribution = ETH hardness for densest-{{mvar|k}}-subgraph with perfect completeness | doi = 10.1137/1.9781611974782.86 | mr = 3627815 | pages = 1326–1341 | publisher = Society for Industrial and Applied Mathematics | title = Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19 | year = 2017}}</ref>

जटिलता सिद्धांत में, अनसुलझी [[पी बनाम एनपी]] समस्या पूछती है कि क्या एनपी में सभी समस्याओं में बहुपद-समय एल्गोरिदम हैं। एनपी-पूर्ण समस्याओं जैसे 3एसएटी आदि के लिए सभी सबसे प्रसिद्ध एल्गोरिदम तेजी से समय लेते हैं। कई प्राकृतिक एनपी-पूर्ण समस्याओं के लिए यह अनुमान लगाया गया है कि उनके पास उप-घातांकीय समय एल्गोरिदम नहीं है। यहां उप-घातांकीय समय का अर्थ नीचे प्रस्तुत दूसरी परिभाषा से लिया गया है। (दूसरी ओर, आसन्न मैट्रिक्स द्वारा प्राकृतिक विधि से दर्शाई गई कई ग्राफ़ समस्याएं उप-घातांकीय समय में हल करने योग्य हैं, क्योंकि इनपुट का आकार शीर्षों की संख्या का वर्ग है।) यह अनुमान (k-एसएटी समस्या के लिए) है घातीय समय परिकल्पना के रूप में जाना जाता है।<ref name="ETH">{{cite journal | last1 = Impagliazzo | first1 = Russell | author1-link = Russell Impagliazzo | last2 = Paturi | first2 = Ramamohan | doi = 10.1006/jcss.2000.1727 | issue = 2 | journal = [[Journal of Computer and System Sciences]] | mr = 1820597 | pages = 367–375 | title = On the complexity of {{mvar|k}}-SAT | url = https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoPaturi_2001_jcss.pdf | volume = 62 | year = 2001| doi-access = free }}</ref> चूँकि यह अनुमान लगाया गया है कि एनपी-पूर्ण समस्याओं में अर्ध-बहुपद समय एल्गोरिदम नहीं होते हैं, [[सन्निकटन एल्गोरिदम]] के क्षेत्र में कुछ अनुपयुक्तता परिणाम यह धारणा बनाते हैं कि एनपी-पूर्ण समस्याओं में अर्ध-बहुपद समय एल्गोरिदम नहीं होते हैं। उदाहरण के लिए, [[ कवर सेट करें | कवर समुच्चय करें]] समस्या के लिए ज्ञात अप्राप्यता परिणाम देखें।

कुछ लेखक उप-घातीय समय को चलने वाले समय <math>2^{o(n)}</math> के रूप में परिभाषित करते हैं .<ref name="ETH" /><ref>{{Cite journal| last1=Kuperberg | first1=Greg | title=डायहेड्रल हिडन सबग्रुप समस्या के लिए एक सबएक्सपोनेंशियल-टाइम क्वांटम एल्गोरिदम| location=Philadelphia | year=2005 | journal=SIAM Journal on Computing | issn=1095-7111 | volume=35 | issue=1 | page=188 | doi=10.1137/s0097539703436345| arxiv=quant-ph/0302112 | s2cid=15965140 }}</ref><ref>{{cite arXiv|eprint=quant-ph/0406151v1|author1=Oded Regev|title=बहुपद स्थान के साथ डायहेड्रल हिडन सबग्रुप समस्या के लिए एक सबएक्सपोनेंशियल टाइम एल्गोरिदम|year=2004}}</ref> यह परिभाषा उप-घातीय समय की पहली परिभाषा की तुलना में बड़े चलने वाले समय की अनुमति देती है। ऐसे उप-घातीय समय एल्गोरिदम का उदाहरण पूर्णांक गुणनखंडन के लिए सबसे प्रसिद्ध मौलिक एल्गोरिदम है, [[सामान्य संख्या फ़ील्ड चलनी]], जो {{nowrap|<math>2^{\tilde{O}(n^{1/3})}</math>,}} समय के बारे में चलता है जहां इनपुट की लंबाई है {{mvar|n}}. अन्य उदाहरण [[ग्राफ समरूपता समस्या]] थी, जिसे 1982 से 2016 तक के सबसे प्रसिद्ध एल्गोरिदम {{nowrap|<math>2^{O\left(\sqrt{n \log n}\right)}</math>.}} में हल किया गया था चूँकि, [[कंप्यूटिंग के सिद्धांत पर संगोष्ठी]] 2016 में अर्ध-बहुपद समय एल्गोरिथ्म प्रस्तुत किया गया था।<ref>{{cite journal|first1=Martin |last1=Grohe|first2=Daniel|last2=Neuen|title=ग्राफ़ समरूपता समस्या पर हालिया प्रगति|arxiv=2011.01366|year=2021}}</ref>