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

{{Redirect|Running time|the film|Running Time (film)}}

[[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> बहुपद समय एल्गोरिथ्म है।

{{Further|Computational complexity of mathematical operations}}

निम्नलिखित तालिका आम तौर पर सामना की जाने वाली समय जटिलताओं के कुछ वर्गों का सारांश प्रस्तुत करती है। मेज पर, {{nowrap|1=poly(''x'') = ''x''^''O''(1)}}, यानी, x में बहुपद।

! Name !! [[Complexity class]] !! Running time {{nowrap|({{math|''T''(''n'')}})}} !! Examples of running times !! Example algorithms

| constant time || || <math>O(1)</math> || 10 || Finding the median value in a sorted [[array data structure|array]] of numbers.

Calculating  {{math|(−1){{sup|''n''}}}}  

| [[inverse Ackermann function|inverse Ackermann]] time || || <math>O\bigl(\alpha(n)\bigr)</math> || || [[Amortized time]] per operation using a [[disjoint set data structure|disjoint set]]

| [[iterated logarithm]]ic time || || <math>O(\log^*n)</math> || || [[Cole-Vishkin algorithm|Distributed coloring of cycles]]

| log-logarithmic || || <math>O(\log\log n)</math> || || Amortized time per operation using a bounded [[priority queue]]<ref>{{Cite journal|first1=Kurt |last1=Mehlhorn |author1-link=Kurt Mehlhorn|first2=Stefan |last2=Naher|year=1990|title=Bounded ordered dictionaries in {{math|''O''(log log ''N'')}} time and {{math|''O''(''n'')}} space|journal=[[Information Processing Letters]]|doi=10.1016/0020-0190(90)90022-P|volume=35|issue=4|pages=183–189}}</ref>

| logarithmic time || [[DLOGTIME]] || <math>O(\log n)</math> || <math>\log n</math>, <math>\log (n^2)</math> || [[Binary search]]

| polylogarithmic time || || <math>\text{poly}(\log n)</math> || <math>(\log n)^2</math> ||

|fractional power || || <math>O(n^c)</math> where <math>0<c<1</math> || <math>n^{\frac{1}{2}}</math>, <math>n^{\frac{2}{3}}</math> || Searching in a [[kd-tree]]

| linear time || || <math>O(n)</math> || {{mvar|n}}, <math>2n+5</math> || Finding the smallest or largest item in an unsorted [[Array data structure|array]].

| "n log-star n" time || || <math>O(n\log^*n)</math> || || [[Raimund Seidel|Seidel]]'s [[polygon triangulation]] algorithm.

| linearithmic time || || <math>O(n\log n)</math> || <math>n\log n</math>, <math>\log n!</math> || Fastest possible [[comparison sort]]

| quasilinear time || || <math>n\text{poly}(\log n)</math> || <math>n\log^2 n</math> || [[Polynomial evaluation#Multipoint evaluation|Multipoint polynomial evaluation]]

| quadratic time || || <math>O(n^2)</math> || <math>n^2</math> || [[Bubble sort]], [[Insertion sort]], [[Convolution theorem|Direct convolution]]

| cubic time || || <math>O(n^3)</math> || <math>n^3</math> || Naive multiplication of two <math>n\times n</math> matrices

Calculating [[partial correlation]].

| polynomial time || [[P (complexity)|P]] || <math>2^{O(\log n)}=\text{poly}(n)</math> || <math>n^2+n</math>, <math>n^{10}</math> || [[Karmarkar's algorithm]] for [[linear programming]]

[[AKS primality test]]<ref name="tao-aks">{{cite book|title=An epsilon of room, II: Pages from year three of a mathematical blog|last=Tao|first=Terence|publisher=American Mathematical Society|year=2010|isbn=978-0-8218-5280-4|series=Graduate Studies in Mathematics|volume=117|location=Providence, RI|pages=82–86|contribution=1.11 The AKS primality test|doi=10.1090/gsm/117|mr=2780010|author-link=Terence Tao|contribution-url=https://terrytao.wordpress.com/2009/08/11/the-aks-primality-test/}}</ref><ref>{{cite journal | last1 = Lenstra | first1 = H. W. Jr. | author1-link = Hendrik Lenstra | last2 = Pomerance | first2 = Carl | author2-link = Carl Pomerance | doi = 10.4171/JEMS/861 | issue = 4 | journal = [[Journal of the European Mathematical Society]] | mr = 3941463 | pages = 1229–1269 | title = Primality testing with Gaussian periods | url = https://math.dartmouth.edu/~carlp/aks111216.pdf | volume = 21 | year = 2019| s2cid = 127807021 }}</ref>

| quasi-polynomial time || QP || <math>2^{\text{poly}(\log n)}</math> || <math>n^{\log \log n}</math>, <math>n^{\log n}</math> || Best-known {{math|''O''(log{{sup|2}}''n'')}}-[[approximation algorithm]] for the directed [[Steiner tree problem]], best known [[parity game]] solver,<ref>{{cite journal |author = Calude, Cristian S. and Jain, Sanjay and Khoussainov, Bakhadyr and Li, Wei and Stephan, Frank| title = Deciding Parity Games in Quasipolynomial Time| year = 2017| isbn = 9781450345286| publisher = Association for Computing Machinery| url = https://doi.org/10.1145/3055399.3055409| doi = 10.1145/3055399.3055409 | journal = Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing| pages = 252–263}}</ref> best known [[graph isomorphism]] algorithm

| sub-exponential time<br />(first definition) || SUBEXP || <math>O(2^{n^\epsilon})</math> for all <math>\epsilon >0</math> ||  || Contains [[Bounded-error probabilistic polynomial|BPP]] unless EXPTIME (see below) equals [[Arthur–Merlin protocol#MA|MA]].<ref name="bpp" />

| sub-exponential time<br />(second definition) || || <math>2^{o(n)}</math> || <math>2^{\sqrt[3]{n}}</math> ||[[General number field sieve|Best classical algorithm]] for [[integer factorization]]

formerly-best algorithm for [[graph isomorphism problem|graph isomorphism]]

| exponential time<br />(with linear exponent) || [[E (complexity)|E]] || <math>2^{O(n)}</math> || <math>1.1^n</math>, <math>10^n</math> || Solving the [[traveling salesman problem]] using [[dynamic programming]]

| exponential time || [[EXPTIME]] || <math>2^{\text{poly}(n)}</math> || <math>2^n</math>, <math>2^{n^2}</math> || Solving [[matrix chain multiplication]] via [[brute-force search]]

| factorial time || || <math>O(n!)</math> || <math>n!</math> || Solving the [[Travelling salesman problem|traveling salesman problem]] via [[brute-force search]]

| double exponential time || [[2-EXPTIME]] || <math>2^{2^{\text{poly}(n)}}</math> || <math>2^{2^n}</math> || Deciding the truth of a given statement in [[Presburger arithmetic]]

== लगातार समय ==

{{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(n)</math> समय। हालाँकि, यदि तत्वों की संख्या पहले से ज्ञात है और बदलती नहीं है, तो ऐसे एल्गोरिदम को अभी भी निरंतर समय में चलने के लिए कहा जा सकता है।

स्थिर समय नाम के बावजूद, चलने का समय समस्या के आकार से स्वतंत्र नहीं होना चाहिए, लेकिन चलने के समय की ऊपरी सीमा समस्या के आकार से स्वतंत्र होनी चाहिए। उदाहरण के लिए, कार्य के मूल्यों का आदान-प्रदान होता है {{mvar|a}} और {{mvar|b}}यदि आवश्यक हो तो कि <math display="inline">a \le b</math>इसे स्थिर समय कहा जाता है, भले ही समय इस पर निर्भर हो सकता है कि यह पहले से ही सत्य है या नहीं <math display="inline">a \le b</math>. हालाँकि, कुछ स्थिरांक है {{mvar|t}} ऐसा कि आवश्यक समय हमेशा अधिकतम होता है {{mvar|t}}.

कहा जाता है कि एल्गोरिदम लघुगणकीय समय लेता है <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|''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> और ग्राफ़ (असतत गणित) [[गतिशील कनेक्टिविटी]] तरीके से प्लानरिटी परीक्षण हो सकता है <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>. विशेष रूप से इसमें ऊपर परिभाषित समय जटिलताओं वाले एल्गोरिदम शामिल हैं।

विशिष्ट एल्गोरिदम जो सटीक होते हैं और फिर भी उप-रेखीय समय में चलते हैं, [[समानांतर एल्गोरिदम]] का उपयोग करते हैं ([[एनसी (जटिलता)]] के रूप में)¹मैट्रिक्स निर्धारक गणना करता है), या वैकल्पिक रूप से इनपुट संरचना पर गारंटीकृत धारणाएं रखता है (जैसा कि लॉगरिदमिक समय [[बाइनरी खोज एल्गोरिदम]] और कई पेड़ रखरखाव एल्गोरिदम करते हैं)। हालाँकि, [[औपचारिक भाषा]]एँ जैसे कि सभी स्ट्रिंग्स का सेट जिसमें पहले द्वारा इंगित स्थिति में 1-बिट होता है <math>\log n</math> स्ट्रिंग के बिट्स इनपुट के प्रत्येक बिट पर निर्भर हो सकते हैं और फिर भी उप-रेखीय समय में गणना योग्य हो सकते हैं।

विशिष्ट शब्द सबलाइनियर टाइम एल्गोरिदम आमतौर पर उन एल्गोरिदम के लिए आरक्षित होता है जो उपरोक्त के विपरीत होते हैं क्योंकि वे शास्त्रीय सीरियल मशीन मॉडल पर चलते हैं और इनपुट पर पूर्व धारणाओं की अनुमति नहीं होती है।<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}}.

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