समय की जटिलता: Difference between revisions
From Vigyanwiki
(Created page with "{{Short description|Estimate of time taken for running an algorithm}} {{Redirect|Running time|the film|Running Time (film)}} File:comparison computational complexity.svg|thu...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Estimate of time taken for running an algorithm}} | {{Short description|Estimate of time taken for running an algorithm}} | ||
{{Redirect|Running time|the film|Running Time (film)}} | {{Redirect|Running time|the film|Running Time (film)}} | ||
[[File:comparison computational complexity.svg|thumb|आमतौर पर एल्गोरिदम के विश्लेषण में उपयोग किए जाने वाले फ़ंक्शन के ग्राफ़, प्रत्येक फ़ंक्शन के लिए इनपुट आकार n के परिणाम के रूप में ऑपरेशन N की संख्या दिखाते हैं]][[कंप्यूटर विज्ञान]] में, समय जटिलता कम्प्यूटेशनल जटिलता है जो | [[File:comparison computational complexity.svg|thumb|आमतौर पर एल्गोरिदम के विश्लेषण में उपयोग किए जाने वाले फ़ंक्शन के ग्राफ़, प्रत्येक फ़ंक्शन के लिए इनपुट आकार n के परिणाम के रूप में ऑपरेशन N की संख्या दिखाते हैं]][[कंप्यूटर विज्ञान]] में, समय जटिलता कम्प्यूटेशनल जटिलता है जो [[कलन विधि]] को चलाने में लगने वाले कंप्यूटर समय की मात्रा का वर्णन करती है। समय की जटिलता का अनुमान आमतौर पर एल्गोरिदम द्वारा किए गए प्राथमिक संचालन की संख्या की गणना करके लगाया जाता है, यह मानते हुए कि प्रत्येक प्रारंभिक ऑपरेशन को निष्पादित करने में निश्चित समय लगता है। इस प्रकार, एल्गोरिदम द्वारा किए गए समय की मात्रा और किए गए प्राथमिक संचालन की संख्या को [[स्थिर कारक]] से संबंधित माना जाता है। | ||
चूंकि | चूंकि एल्गोरिदम का चलने का समय ही आकार के विभिन्न इनपुट के बीच भिन्न हो सकता है, इसलिए आमतौर पर [[सबसे खराब स्थिति जटिलता]] | सबसे खराब स्थिति समय जटिलता पर विचार किया जाता है, जो किसी दिए गए आकार के इनपुट के लिए आवश्यक अधिकतम समय है। कम सामान्य, और आमतौर पर स्पष्ट रूप से निर्दिष्ट, औसत-केस जटिलता है, जो किसी दिए गए आकार के इनपुट पर लिए गए समय का औसत है (यह समझ में आता है क्योंकि किसी दिए गए आकार के संभावित इनपुट की केवल सीमित संख्या होती है)। दोनों ही मामलों में, समय जटिलता आम तौर पर इनपुट के आकार के [[फ़ंक्शन (गणित)]] के रूप में व्यक्त की जाती है।<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> बहुपद समय एल्गोरिथ्म है। | ||
== सामान्य समय जटिलताओं की तालिका == | == सामान्य समय जटिलताओं की तालिका == | ||
| Line 70: | Line 70: | ||
{{redirect|Constant time|programming technique to avoid a timing attack|Timing attack#Avoidance}} | {{redirect|Constant time|programming technique to avoid a timing attack|Timing attack#Avoidance}} | ||
एक एल्गोरिदम को स्थिर समय कहा जाता है (इसे इस रूप में भी लिखा जाता है)। <math display="inline">O(1)</math> समय) यदि का मान <math display="inline">T(n)</math> (एल्गोरिदम की जटिलता) | एक एल्गोरिदम को स्थिर समय कहा जाता है (इसे इस रूप में भी लिखा जाता है)। <math display="inline">O(1)</math> समय) यदि का मान <math display="inline">T(n)</math> (एल्गोरिदम की जटिलता) मान से बंधी है जो इनपुट के आकार पर निर्भर नहीं करती है। उदाहरण के लिए, किसी [[सरणी डेटा संरचना]] में किसी तत्व तक पहुँचने में निरंतर समय लगता है क्योंकि इसे खोजने के लिए केवल [[निर्देश (कंप्यूटर विज्ञान)]] का पालन करना पड़ता है। इसी प्रकार, आरोही क्रम में क्रमबद्ध सरणी में न्यूनतम मान ज्ञात करना; यह पहला तत्व है. हालाँकि, अव्यवस्थित सरणी में न्यूनतम मान ढूँढना निरंतर समय का ऑपरेशन नहीं है क्योंकि न्यूनतम मान निर्धारित करने के लिए सरणी में प्रत्येक [[तत्व (गणित)]] पर स्कैनिंग की आवश्यकता होती है। इसलिए यह रैखिक समय संक्रिया है <math display="inline">O(n)</math> समय। हालाँकि, यदि तत्वों की संख्या पहले से ज्ञात है और बदलती नहीं है, तो ऐसे एल्गोरिदम को अभी भी निरंतर समय में चलने के लिए कहा जा सकता है। | ||
स्थिर समय नाम के बावजूद, चलने का समय समस्या के आकार से स्वतंत्र नहीं होना चाहिए, लेकिन चलने के समय की ऊपरी सीमा समस्या के आकार से स्वतंत्र होनी चाहिए। उदाहरण के लिए, कार्य के मूल्यों का आदान-प्रदान होता है {{mvar|a}} और {{mvar|b}}यदि आवश्यक हो तो कि <math display="inline">a \le b</math>इसे स्थिर समय कहा जाता है, भले ही समय इस पर निर्भर हो सकता है कि यह पहले से ही सत्य है या नहीं <math display="inline">a \le b</math>. हालाँकि, कुछ स्थिरांक है {{mvar|t}} ऐसा कि आवश्यक समय हमेशा अधिकतम होता है {{mvar|t}}. | स्थिर समय नाम के बावजूद, चलने का समय समस्या के आकार से स्वतंत्र नहीं होना चाहिए, लेकिन चलने के समय की ऊपरी सीमा समस्या के आकार से स्वतंत्र होनी चाहिए। उदाहरण के लिए, कार्य के मूल्यों का आदान-प्रदान होता है {{mvar|a}} और {{mvar|b}}यदि आवश्यक हो तो कि <math display="inline">a \le b</math>इसे स्थिर समय कहा जाता है, भले ही समय इस पर निर्भर हो सकता है कि यह पहले से ही सत्य है या नहीं <math display="inline">a \le b</math>. हालाँकि, कुछ स्थिरांक है {{mvar|t}} ऐसा कि आवश्यक समय हमेशा अधिकतम होता है {{mvar|t}}. | ||
| Line 76: | Line 76: | ||
== लघुगणकीय समय == | == लघुगणकीय समय == | ||
{{Further|Logarithmic growth}} | {{Further|Logarithmic growth}} | ||
कहा जाता है कि | कहा जाता है कि एल्गोरिदम लघुगणकीय समय लेता है <math>T(n) = O(\log n)</math>. तब से <math>\log_a n</math> और <math>\log_b n</math> लॉगरिदमिक पहचानों से संबंधित हैं#आधार बदलना, और ऐसे बिग ओ नोटेशन#बड़े ओ वर्गीकरण के लिए स्थिरांक द्वारा गुणा, लॉगरिदमिक-समय एल्गोरिदम के लिए मानक उपयोग है <math>O(\log n)</math> की अभिव्यक्ति में प्रदर्शित होने वाले लघुगणक के आधार की परवाह किए बिना {{mvar|T}}. | ||
लॉगरिदमिक समय लेने वाले एल्गोरिदम आमतौर पर बाइनरी पेड़ों पर संचालन में या बाइनरी खोज का उपयोग करते समय पाए जाते हैं। | लॉगरिदमिक समय लेने वाले एल्गोरिदम आमतौर पर बाइनरी पेड़ों पर संचालन में या बाइनरी खोज का उपयोग करते समय पाए जाते हैं। | ||
एक <math>O(\log n)</math> एल्गोरिदम को अत्यधिक कुशल माना जाता है, क्योंकि ऑपरेशन की संख्या और इनपुट के आकार का अनुपात घट जाता है और शून्य हो जाता है {{mvar|n}} बढ़ती है। | एक <math>O(\log n)</math> एल्गोरिदम को अत्यधिक कुशल माना जाता है, क्योंकि ऑपरेशन की संख्या और इनपुट के आकार का अनुपात घट जाता है और शून्य हो जाता है {{mvar|n}} बढ़ती है। एल्गोरिदम जिसे अपने इनपुट के सभी तत्वों तक पहुंच चाहिए, वह लॉगरिदमिक समय नहीं ले सकता है, क्योंकि आकार के इनपुट को पढ़ने में लगने वाला समय {{mvar|n}} के क्रम का है {{mvar|n}}. | ||
शब्दकोश खोज द्वारा लघुगणकीय समय का | शब्दकोश खोज द्वारा लघुगणकीय समय का उदाहरण दिया गया है। शब्दकोश पर विचार करें (डेटा संरचना) {{math|''D''}} जिसमें है {{mvar|n}} प्रविष्टियाँ, वर्णानुक्रम के अनुसार क्रमबद्ध। हम ऐसा मानते हैं, के लिए <math>1 \le k \le n</math>, कोई भी पहुंच सकता है {{mvar|k}}निरंतर समय में शब्दकोश कीवीं प्रविष्टि। होने देना <math>D(k)</math> इसे निरूपित करें {{mvar|k}}फिर कोशिश करो। इन परिकल्पनाओं के तहत, यह देखने के लिए परीक्षण करें कि क्या कोई शब्द {{mvar|w}} शब्दकोश में लघुगणकीय समय में किया जा सकता है: विचार करें <math>D\left(\left\lfloor \frac{n}{2} \right\rfloor\right)</math>, कहाँ <math>\lfloor\;\rfloor</math> [[फर्श समारोह]] को दर्शाता है। अगर <math>w = D\left(\left\lfloor \frac{n}{2} \right\rfloor\right)</math>, तो हमारा काम हो गया। अन्यथा, यदि <math>w < D\left(\left\lfloor \frac{n}{2} \right\rfloor\right)</math>, शब्दकोश के बाएँ आधे भाग में इसी प्रकार खोज जारी रखें, अन्यथा शब्दकोश के दाएँ आधे भाग के साथ भी इसी प्रकार जारी रखें। यह एल्गोरिदम उस विधि के समान है जिसका उपयोग अक्सर पेपर डिक्शनरी में प्रविष्टि खोजने के लिए किया जाता है। | ||
== बहुगणितीय समय == | == बहुगणितीय समय == | ||
कहा जाता है कि | कहा जाता है कि एल्गोरिदम [[बहुगणितीय फलन]] समय में चलता है यदि उसका समय है <math>T(n)</math> है <math>O\bigl((\log n)^k\bigr)</math> कुछ स्थिरांक के लिए {{mvar|k}}. इसे लिखने का दूसरा तरीका है <math>O(\log^kn)</math>. | ||
उदाहरण के लिए, [[मैट्रिक्स श्रृंखला गुणन]] को [[समानांतर रैंडम-एक्सेस मशीन]] पर पॉलीलॉगरिदमिक समय में हल किया जा सकता है,<ref>{{cite journal | last1 = Bradford | first1 = Phillip G. | last2 = Rawlins | first2 = Gregory J. E. | last3 = Shannon | first3 = Gregory E. | doi = 10.1137/S0097539794270698 | issue = 2 | journal = [[SIAM Journal on Computing]] | mr = 1616556 | pages = 466–490 | title = पॉलीलॉग समय में कुशल मैट्रिक्स श्रृंखला क्रम| volume = 27 | year = 1998}}</ref> और ग्राफ़ (असतत गणित) | उदाहरण के लिए, [[मैट्रिक्स श्रृंखला गुणन]] को [[समानांतर रैंडम-एक्सेस मशीन]] पर पॉलीलॉगरिदमिक समय में हल किया जा सकता है,<ref>{{cite journal | last1 = Bradford | first1 = Phillip G. | last2 = Rawlins | first2 = Gregory J. E. | last3 = Shannon | first3 = Gregory E. | doi = 10.1137/S0097539794270698 | issue = 2 | journal = [[SIAM Journal on Computing]] | mr = 1616556 | pages = 466–490 | title = पॉलीलॉग समय में कुशल मैट्रिक्स श्रृंखला क्रम| volume = 27 | year = 1998}}</ref> और ग्राफ़ (असतत गणित) [[गतिशील कनेक्टिविटी]] तरीके से प्लानरिटी परीक्षण हो सकता है <math>O(\log^3n)</math> प्रति डालने/हटाने की कार्रवाई में लगने वाला समय।<ref>{{cite conference | last1 = Holm | first1 = Jacob | last2 = Rotenberg | first2 = Eva | editor1-last = Makarychev | editor1-first = Konstantin | editor2-last = Makarychev | editor2-first = Yury | editor3-last = Tulsiani | editor3-first = Madhur | editor4-last = Kamath | editor4-first = Gautam | editor5-last = Chuzhoy | editor5-first = Julia | editor5-link = Julia Chuzhoy | arxiv = 1911.03449 | contribution = Fully-dynamic planarity testing in polylogarithmic time | doi = 10.1145/3357713.3384249 | pages = 167–180 | publisher = Association for Computing Machinery | title = Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020 | year = 2020}}</ref> | ||
== उप-रैखिक समय == | == उप-रैखिक समय == | ||
कहा जाता है कि | कहा जाता है कि एल्गोरिदम सब-लीनियर टाइम (अक्सर सब-लीनियर टाइम लिखा जाता है) में चलता है <math>T(n)=o(n)</math>. विशेष रूप से इसमें ऊपर परिभाषित समय जटिलताओं वाले एल्गोरिदम शामिल हैं। | ||
विशिष्ट एल्गोरिदम जो सटीक होते हैं और फिर भी उप-रेखीय समय में चलते हैं, [[समानांतर एल्गोरिदम]] का उपयोग करते हैं ([[एनसी (जटिलता)]] के रूप में)<sup>1</sup>मैट्रिक्स निर्धारक गणना करता है), या वैकल्पिक रूप से इनपुट संरचना पर गारंटीकृत धारणाएं रखता है (जैसा कि लॉगरिदमिक समय [[बाइनरी खोज एल्गोरिदम]] और कई पेड़ रखरखाव एल्गोरिदम करते हैं)। हालाँकि, [[औपचारिक भाषा]]एँ जैसे कि सभी स्ट्रिंग्स का सेट जिसमें पहले द्वारा इंगित स्थिति में 1-बिट होता है <math>\log n</math> स्ट्रिंग के बिट्स इनपुट के प्रत्येक बिट पर निर्भर हो सकते हैं और फिर भी उप-रेखीय समय में गणना योग्य हो सकते हैं। | विशिष्ट एल्गोरिदम जो सटीक होते हैं और फिर भी उप-रेखीय समय में चलते हैं, [[समानांतर एल्गोरिदम]] का उपयोग करते हैं ([[एनसी (जटिलता)]] के रूप में)<sup>1</sup>मैट्रिक्स निर्धारक गणना करता है), या वैकल्पिक रूप से इनपुट संरचना पर गारंटीकृत धारणाएं रखता है (जैसा कि लॉगरिदमिक समय [[बाइनरी खोज एल्गोरिदम]] और कई पेड़ रखरखाव एल्गोरिदम करते हैं)। हालाँकि, [[औपचारिक भाषा]]एँ जैसे कि सभी स्ट्रिंग्स का सेट जिसमें पहले द्वारा इंगित स्थिति में 1-बिट होता है <math>\log n</math> स्ट्रिंग के बिट्स इनपुट के प्रत्येक बिट पर निर्भर हो सकते हैं और फिर भी उप-रेखीय समय में गणना योग्य हो सकते हैं। | ||
| Line 97: | Line 97: | ||
विशिष्ट शब्द सबलाइनियर टाइम एल्गोरिदम आमतौर पर उन एल्गोरिदम के लिए आरक्षित होता है जो उपरोक्त के विपरीत होते हैं क्योंकि वे शास्त्रीय सीरियल मशीन मॉडल पर चलते हैं और इनपुट पर पूर्व धारणाओं की अनुमति नहीं होती है।<ref>{{cite journal | last1 = Kumar | first1 = Ravi | last2 = Rubinfeld | first2 = Ronitt | author2-link = Ronitt Rubinfeld | title = सबलाइनियर टाइम एल्गोरिदम| journal = [[SIGACT News]] | volume = 34 | issue = 4 | pages = 57–67 | url = http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/kumarR-survey.pdf | year = 2003 | doi = 10.1145/954092.954103| s2cid = 65359 }}</ref> हालाँकि, उन्हें [[यादृच्छिक एल्गोरिदम]] होने की अनुमति है, और वास्तव में सबसे तुच्छ कार्यों को छोड़कर सभी के लिए यादृच्छिक किया जाना चाहिए। | विशिष्ट शब्द सबलाइनियर टाइम एल्गोरिदम आमतौर पर उन एल्गोरिदम के लिए आरक्षित होता है जो उपरोक्त के विपरीत होते हैं क्योंकि वे शास्त्रीय सीरियल मशीन मॉडल पर चलते हैं और इनपुट पर पूर्व धारणाओं की अनुमति नहीं होती है।<ref>{{cite journal | last1 = Kumar | first1 = Ravi | last2 = Rubinfeld | first2 = Ronitt | author2-link = Ronitt Rubinfeld | title = सबलाइनियर टाइम एल्गोरिदम| journal = [[SIGACT News]] | volume = 34 | issue = 4 | pages = 57–67 | url = http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/kumarR-survey.pdf | year = 2003 | doi = 10.1145/954092.954103| s2cid = 65359 }}</ref> हालाँकि, उन्हें [[यादृच्छिक एल्गोरिदम]] होने की अनुमति है, और वास्तव में सबसे तुच्छ कार्यों को छोड़कर सभी के लिए यादृच्छिक किया जाना चाहिए। | ||
चूँकि ऐसे एल्गोरिदम को पूरे इनपुट को पढ़े बिना उत्तर देना होगा, इसका विवरण काफी हद तक इनपुट तक पहुंच की अनुमति पर निर्भर करता है। आमतौर पर | चूँकि ऐसे एल्गोरिदम को पूरे इनपुट को पढ़े बिना उत्तर देना होगा, इसका विवरण काफी हद तक इनपुट तक पहुंच की अनुमति पर निर्भर करता है। आमतौर पर इनपुट के लिए जिसे बाइनरी स्ट्रिंग के रूप में दर्शाया जाता है <math>b_1, ..., b_k</math> यह माना जाता है कि एल्गोरिदम समय में हो सकता है <math>O(1)</math> अनुरोध करें और इसका मूल्य प्राप्त करें <math>b_i</math> किसी के लिए {{mvar|i}}. | ||
उप-रेखीय समय एल्गोरिदम आमतौर पर यादृच्छिक होते हैं, और केवल सन्निकटन एल्गोरिदम समाधान प्रदान करते हैं। वास्तव में, | उप-रेखीय समय एल्गोरिदम आमतौर पर यादृच्छिक होते हैं, और केवल सन्निकटन एल्गोरिदम समाधान प्रदान करते हैं। वास्तव में, बाइनरी स्ट्रिंग की संपत्ति जिसमें केवल शून्य होते हैं (और कोई नहीं) आसानी से (गैर-अनुमानित) उप-रेखीय समय एल्गोरिदम द्वारा निर्णय योग्य नहीं साबित किया जा सकता है। [[संपत्ति परीक्षण]] की जांच में उप-रेखीय समय एल्गोरिदम स्वाभाविक रूप से उत्पन्न होते हैं। | ||
==रेखीय समय == | ==रेखीय समय == | ||
कहा जाता है कि | कहा जाता है कि एल्गोरिदम रैखिक समय लेता है, या <math>O(n)</math> समय, यदि इसकी समय जटिलता है <math>O(n)</math>. अनौपचारिक रूप से, इसका मतलब यह है कि इनपुट के आकार के साथ चलने का समय अधिकतम रैखिक रूप से बढ़ता है। अधिक सटीक रूप से, इसका मतलब यह है कि स्थिरांक है {{mvar|c}} ऐसा कि चलने का समय अधिकतम हो <math>cn</math> आकार के प्रत्येक इनपुट के लिए {{mvar|n}}. उदाहरण के लिए, प्रक्रिया जो किसी सूची के सभी तत्वों को जोड़ती है, उसे सूची की लंबाई के अनुपात में समय की आवश्यकता होती है, यदि जोड़ने का समय स्थिर है, या, कम से कम, स्थिरांक से घिरा हुआ है। | ||
रैखिक समय उन स्थितियों में सर्वोत्तम संभव समय जटिलता है जहां एल्गोरिदम को क्रमिक रूप से अपने संपूर्ण इनपुट को पढ़ना होता है। इसलिए, रैखिक समय या, कम से कम, लगभग रैखिक समय प्रदर्शित करने वाले एल्गोरिदम की खोज में बहुत अधिक शोध का निवेश किया गया है। इस शोध में सॉफ्टवेयर और हार्डवेयर दोनों तरीके शामिल हैं। ऐसी कई हार्डवेयर प्रौद्योगिकियाँ हैं जो इसे प्रदान करने के लिए [[समानांतर कंप्यूटिंग]] का उपयोग करती हैं। | रैखिक समय उन स्थितियों में सर्वोत्तम संभव समय जटिलता है जहां एल्गोरिदम को क्रमिक रूप से अपने संपूर्ण इनपुट को पढ़ना होता है। इसलिए, रैखिक समय या, कम से कम, लगभग रैखिक समय प्रदर्शित करने वाले एल्गोरिदम की खोज में बहुत अधिक शोध का निवेश किया गया है। इस शोध में सॉफ्टवेयर और हार्डवेयर दोनों तरीके शामिल हैं। ऐसी कई हार्डवेयर प्रौद्योगिकियाँ हैं जो इसे प्रदान करने के लिए [[समानांतर कंप्यूटिंग]] का उपयोग करती हैं। उदाहरण [[ सामग्री-पता योग्य स्मृति ]] है। रैखिक समय की इस अवधारणा का उपयोग बॉयर-मूर स्ट्रिंग-खोज एल्गोरिदम और उक्कोनेन के एल्गोरिदम जैसे स्ट्रिंग मिलान एल्गोरिदम में किया जाता है। | ||
== <span id= Linearithmic time ></span> Quasilinear time == | == <span id= Linearithmic time ></span> Quasilinear time == | ||
कहा जाता है कि | कहा जाता है कि एल्गोरिदम क्वासिलिनियर टाइम (जिसे लॉग-लीनियर टाइम भी कहा जाता है) में चलता है <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^2n)</math> | * [[इन-प्लेस मर्ज सॉर्ट]], <math>O(n\log^2n)</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>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>O(n\log n)</math> रनिंग टाइम केवल प्रदर्शन का परिणाम है <math>\Theta (\log n)</math> कार्यवाही {{mvar|n}} बार (नोटेशन के लिए, देखें {{slink|Big O notation|Family of Bachmann–Landau notations}}). उदाहरण के लिए, [[बाइनरी ट्री सॉर्ट]] प्रत्येक तत्व को सम्मिलित करके | कई मामलों में, <math>O(n\log n)</math> रनिंग टाइम केवल प्रदर्शन का परिणाम है <math>\Theta (\log n)</math> कार्यवाही {{mvar|n}} बार (नोटेशन के लिए, देखें {{slink|Big O notation|Family of Bachmann–Landau notations}}). उदाहरण के लिए, [[बाइनरी ट्री सॉर्ट]] प्रत्येक तत्व को सम्मिलित करके बाइनरी ट्री बनाता है {{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>. | तुलनात्मक प्रकारों के लिए कम से कम आवश्यकता होती है <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>. | ||
| Line 125: | Line 125: | ||
== [[बहुपद]] समय == | == [[बहुपद]] समय == | ||
एक एल्गोरिदम को बहुपद समय का कहा जाता है यदि इसका चलने का समय एल्गोरिदम के लिए इनपुट के आकार में | एक एल्गोरिदम को बहुपद समय का कहा जाता है यदि इसका चलने का समय एल्गोरिदम के लिए इनपुट के आकार में बहुपद अभिव्यक्ति द्वारा [[ऊपरी सीमा]] पर होता है, अर्थात, {{nowrap|1=''T''(''n'') = ''O''(''n''<sup>''k''</sup>)}} कुछ सकारात्मक स्थिरांक k के लिए।<ref name=Sipser>{{Cite book| last=Sipser | first=Michael | author-link=Michael Sipser | title=संगणना के सिद्धांत का परिचय| year=2006 | publisher=Course Technology Inc | isbn=0-619-21764-2 }}</ref><ref>{{Cite book| last=Papadimitriou | first=Christos H. | author-link=Christos H. Papadimitriou | title=अभिकलनात्मक जटिलता| year=1994 | publisher=Addison-Wesley | location=Reading, Mass. | isbn=0-201-53082-1 }}</ref> निर्णय समस्या जिसके लिए नियतात्मक बहुपद-समय एल्गोरिथ्म मौजूद है, [[जटिलता वर्ग]] [[पी (जटिलता)]] से संबंधित है, जो [[कम्प्यूटेशनल जटिलता सिद्धांत]] के क्षेत्र में केंद्रीय है। कोबम की थीसिस में कहा गया है कि बहुपद समय सुव्यवस्थित, व्यवहार्य, कुशल या तेज़ का पर्याय है।<ref>{{Cite book| last=Cobham | first=Alan | author-link=Alan Cobham (mathematician) | year = 1965 | chapter = The intrinsic computational difficulty of functions | title = प्रोक. तर्क, पद्धति और विज्ञान का दर्शन II| publisher = North Holland}}</ref> | ||
बहुपद-समय एल्गोरिदम के कुछ उदाहरण: | बहुपद-समय एल्गोरिदम के कुछ उदाहरण: | ||
* n पूर्णांकों पर चयन सॉर्ट सॉर्टिंग एल्गोरिदम निष्पादित करता है <math>An^2</math> कुछ स्थिरांक A के लिए संचालन। इस प्रकार यह समय में चलता है <math>O(n^2)</math> और | * n पूर्णांकों पर चयन सॉर्ट सॉर्टिंग एल्गोरिदम निष्पादित करता है <math>An^2</math> कुछ स्थिरांक A के लिए संचालन। इस प्रकार यह समय में चलता है <math>O(n^2)</math> और बहुपद-समय एल्गोरिथ्म है। | ||
* सभी बुनियादी अंकगणितीय संक्रियाएं (जोड़, घटाव, गुणा, भाग और तुलना) बहुपद समय में की जा सकती हैं। | * सभी बुनियादी अंकगणितीय संक्रियाएं (जोड़, घटाव, गुणा, भाग और तुलना) बहुपद समय में की जा सकती हैं। | ||
* ग्राफ़ (अलग गणित) में [[अधिकतम मिलान]] बहुपद समय में पाया जा सकता है। | * ग्राफ़ (अलग गणित) में [[अधिकतम मिलान]] बहुपद समय में पाया जा सकता है। | ||
=== प्रबल और दुर्बल बहुपद समय === | === प्रबल और दुर्बल बहुपद समय === | ||
कुछ संदर्भों में, विशेष रूप से [[अनुकूलन (गणित)]] में, व्यक्ति प्रबल बहुपद समय और कमजोर बहुपद समय एल्गोरिदम के बीच अंतर करता है। ये दो अवधारणाएँ केवल तभी प्रासंगिक हैं जब एल्गोरिदम के इनपुट में पूर्णांक शामिल हों। | कुछ संदर्भों में, विशेष रूप से [[अनुकूलन (गणित)]] में, व्यक्ति प्रबल बहुपद समय और कमजोर बहुपद समय एल्गोरिदम के बीच अंतर करता है। ये दो अवधारणाएँ केवल तभी प्रासंगिक हैं जब एल्गोरिदम के इनपुट में पूर्णांक शामिल हों। | ||
गणना के अंकगणितीय मॉडल में दृढ़तापूर्वक बहुपद समय को परिभाषित किया गया है। गणना के इस मॉडल में बुनियादी अंकगणितीय परिचालन (जोड़, घटाव, गुणा, भाग और तुलना) को ऑपरेंड के आकार की परवाह किए बिना निष्पादित करने के लिए | गणना के अंकगणितीय मॉडल में दृढ़तापूर्वक बहुपद समय को परिभाषित किया गया है। गणना के इस मॉडल में बुनियादी अंकगणितीय परिचालन (जोड़, घटाव, गुणा, भाग और तुलना) को ऑपरेंड के आकार की परवाह किए बिना निष्पादित करने के लिए इकाई समय कदम उठाना पड़ता है। एल्गोरिथ्म दृढ़ता से बहुपद समय में चलता है यदि:<ref>{{Cite book| last=Grötschel | first=Martin | author1-link= Martin Grötschel |author2=László Lovász | author3-link=Alexander Schrijver |author3=Alexander Schrijver | year = 1988 | chapter = Complexity, Oracles, and Numerical Computation| title = ज्यामितीय एल्गोरिदम और संयोजन अनुकूलन| publisher = Springer | isbn=0-387-13624-X| author2-link=László Lovász }}</ref> | ||
# गणना के अंकगणितीय मॉडल में संचालन की संख्या इनपुट उदाहरण में पूर्णांकों की संख्या में | # गणना के अंकगणितीय मॉडल में संचालन की संख्या इनपुट उदाहरण में पूर्णांकों की संख्या में बहुपद से घिरी होती है; और | ||
# एल्गोरिदम द्वारा उपयोग किया गया स्थान इनपुट के आकार में | # एल्गोरिदम द्वारा उपयोग किया गया स्थान इनपुट के आकार में बहुपद से घिरा हुआ है। | ||
इन दो गुणों वाले किसी भी एल्गोरिदम को [[ट्यूरिंग मशीन]] पर अंकगणितीय संचालन करने के लिए उपयुक्त एल्गोरिदम द्वारा अंकगणितीय संचालन को प्रतिस्थापित करके बहुपद समय एल्गोरिदम में परिवर्तित किया जा सकता है। दूसरी शर्त अत्यंत आवश्यक है: पूर्णांक दिया गया है <math>2^n</math> (जो ट्यूरिंग मशीन मॉडल में n के समानुपाती स्थान लेता है), इसकी गणना करना संभव है <math>2^{2^n}</math> दोहराए गए वर्ग का उपयोग करके n गुणन के साथ। हालाँकि, स्थान प्रतिनिधित्व करता था <math>2^{2^n}</math> के लिए आनुपातिक है <math>2^n</math>, और इस प्रकार इनपुट का प्रतिनिधित्व करने के लिए उपयोग किए जाने वाले स्थान में बहुपद के बजाय घातांकीय होता है। इसलिए, ट्यूरिंग मशीन पर बहुपद समय में यह गणना करना संभव नहीं है, लेकिन बहुपद रूप से कई अंकगणितीय परिचालनों द्वारा इसकी गणना करना संभव है। | इन दो गुणों वाले किसी भी एल्गोरिदम को [[ट्यूरिंग मशीन]] पर अंकगणितीय संचालन करने के लिए उपयुक्त एल्गोरिदम द्वारा अंकगणितीय संचालन को प्रतिस्थापित करके बहुपद समय एल्गोरिदम में परिवर्तित किया जा सकता है। दूसरी शर्त अत्यंत आवश्यक है: पूर्णांक दिया गया है <math>2^n</math> (जो ट्यूरिंग मशीन मॉडल में n के समानुपाती स्थान लेता है), इसकी गणना करना संभव है <math>2^{2^n}</math> दोहराए गए वर्ग का उपयोग करके n गुणन के साथ। हालाँकि, स्थान प्रतिनिधित्व करता था <math>2^{2^n}</math> के लिए आनुपातिक है <math>2^n</math>, और इस प्रकार इनपुट का प्रतिनिधित्व करने के लिए उपयोग किए जाने वाले स्थान में बहुपद के बजाय घातांकीय होता है। इसलिए, ट्यूरिंग मशीन पर बहुपद समय में यह गणना करना संभव नहीं है, लेकिन बहुपद रूप से कई अंकगणितीय परिचालनों द्वारा इसकी गणना करना संभव है। | ||
हालाँकि, पहली शर्त के लिए, ऐसे एल्गोरिदम हैं जो बाइनरी-एन्कोडेड इनपुट की लंबाई में | हालाँकि, पहली शर्त के लिए, ऐसे एल्गोरिदम हैं जो बाइनरी-एन्कोडेड इनपुट की लंबाई में बहुपद से बंधे कई ट्यूरिंग मशीन चरणों में चलते हैं, लेकिन इनपुट की संख्या में बहुपद से बंधे कई अंकगणितीय संचालन नहीं लेते हैं नंबर. दो पूर्णांकों के सबसे बड़े सामान्य भाजक की गणना के लिए [[यूक्लिडियन एल्गोरिथ्म]] उदाहरण है। दो पूर्णांक दिए गए हैं <math>a</math> और <math>b</math>, एल्गोरिथम निष्पादित करता है <math>O(\log a + \log b)</math> संख्याओं पर अंकगणितीय संक्रियाएँ | ||
अधिक से अधिक <math>O(\log a + \log b)</math> बिट्स साथ ही, अंकगणितीय संक्रियाओं की संख्या को इनपुट में पूर्णांकों की संख्या से सीमित नहीं किया जा सकता है (जो इस मामले में स्थिर है, इनपुट में हमेशा केवल दो पूर्णांक होते हैं)। बाद के अवलोकन के कारण, एल्गोरिदम दृढ़ता से बहुपद समय में नहीं चलता है। इसका वास्तविक चलने का समय लंबाई पर निर्भर करता है <math>a</math> और <math>b</math> बिट्स में और न केवल इनपुट में पूर्णांकों की संख्या पर। | अधिक से अधिक <math>O(\log a + \log b)</math> बिट्स साथ ही, अंकगणितीय संक्रियाओं की संख्या को इनपुट में पूर्णांकों की संख्या से सीमित नहीं किया जा सकता है (जो इस मामले में स्थिर है, इनपुट में हमेशा केवल दो पूर्णांक होते हैं)। बाद के अवलोकन के कारण, एल्गोरिदम दृढ़ता से बहुपद समय में नहीं चलता है। इसका वास्तविक चलने का समय लंबाई पर निर्भर करता है <math>a</math> और <math>b</math> बिट्स में और न केवल इनपुट में पूर्णांकों की संख्या पर। | ||
एक एल्गोरिथ्म जो बहुपद समय में चलता है लेकिन जो दृढ़ता से बहुपद नहीं है, उसे कमजोर बहुपद समय में चलने वाला कहा जाता है।<ref>{{Cite book| last=Schrijver | first=Alexander | author-link = Alexander Schrijver| year = 2003 | chapter = Preliminaries on algorithms and Complexity | title = Combinatorial Optimization: Polyhedra and Efficiency | volume = 1 | publisher = Springer | isbn=3-540-44389-4}}</ref> | एक एल्गोरिथ्म जो बहुपद समय में चलता है लेकिन जो दृढ़ता से बहुपद नहीं है, उसे कमजोर बहुपद समय में चलने वाला कहा जाता है।<ref>{{Cite book| last=Schrijver | first=Alexander | author-link = Alexander Schrijver| | ||