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

Revision as of 12:01, 4 July 2023

सामान्यतः एल्गोरिदम के विश्लेषण में उपयोग किए जाने वाले फलन के ग्राफ़, प्रत्येक फलन के लिए इनपुट आकार n के परिणाम के रूप में संचालन N की संख्या दिखाते हैं

कंप्यूटर विज्ञान में, समय जटिलता कम्प्यूटेशनल जटिलता है जो कलन विधि को चलाने में लगने वाले कंप्यूटर समय की मात्रा का वर्णन करती है। समय की जटिलता का अनुमान सामान्यतः एल्गोरिदम द्वारा किए गए प्राथमिक संचालन की संख्या की गणना करके लगाया जाता है, यह मानते हुए कि प्रत्येक प्रारंभिक संचालन को निष्पादित करने में निश्चित समय लगता है। इस प्रकार, एल्गोरिदम द्वारा किए गए समय की मात्रा और किए गए प्राथमिक संचालन की संख्या को स्थिर कारक से संबंधित माना जाता है।

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

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

सामान्य समय जटिलताओं की तालिका

निम्नलिखित तालिका सामान्यतः सामना की जाने वाली समय जटिलताओं के कुछ वर्गों का सारांश प्रस्तुत करती है। तालिका में पॉली (x) = xO(1) अर्थात x में बहुपद है।

नाम	जटिलता वर्ग	संचालन समय (टी(एन))	प्रारंभ समय के उदाहरण	उदाहरण एल्गोरिदम
निरंतर समय		$O(1)$	10	संख्याओं की क्रमबद्ध सारणी में माध्य मान ज्ञात करना। की गणना $(-1) n$
एकरमैन समय का उलटा		$O{\bigl (}\alpha (n){\bigr )}$		एक असंयुक्त समुच्चय का उपयोग करके प्रति ऑपरेशन परिशोधित समय
पुनरावृत्त लघुगणकीय समय		$O(\log ^{*}n)$		साइकिलों का रंग-रोगन वितरित किया
लॉग-लघुगणक		$O(\log \log n)$		एक बंधी हुई प्राथमिकता कतार का उपयोग करके प्रति ऑपरेशन परिशोधित समय^[2]
लघुगणकीय समय	DLOGTIME	$O(\log n)$	$\log n$ , $\log(n^{2})$	बाइनरी खोज
बहुगणितीय समय		${\text{poly}}(\log n)$	$(\log n)^{2}$
भिन्नात्मक शक्ति		$O(n^{c})$ where $0<c<1$	$n^{\frac {1}{2}}$ , $n^{\frac {2}{3}}$	केडी-ट्री में खोज रहे हैं
रैखिक समय		$O(n)$

[1]

[2]

@@ Line 214: / Line 214: @@
 {{Main|घातांकीय समय परिकल्पना}}
-घातीय समय परिकल्पना (ईटीएच) यह है कि [[3SAT|3एसएटी]], प्रति खंड अधिकतम तीन अक्षर और ''एन'' चर के साथ [[संयोजक सामान्य रूप]] में बूलियन सूत्रों की संतुष्टि की समस्या को समय 2 में हल नहीं किया जा सकता है।<sup>ओ(एन)</sup>. अधिक स्पष्ट रूप से, परिकल्पना यह है कि कुछ पूर्ण स्थिरांक है {{math|''c'' > 0}} ऐसा कि 3एसएटी का निर्णय समय 2 में नहीं किया जा सकता<sup>किसी नियतात्मक ट्यूरिंग मशीन द्वारा cn</sup>। एम के साथ खंडों की संख्या को दर्शाते हुए, ईटीएच उस परिकल्पना के बराबर है कि केएसएटी को समय 2 में हल नहीं किया जा सकता है<sup>किसी भी पूर्णांक के लिए o(m)</sup> {{math|''k'' ≥ 3}}.<ref>{{Cite journal|first1=R.|last1=Impagliazzo|author1-link=Russell Impagliazzo|first2=R.|last2=Paturi|first3=F.|last3=Zane|title=Which problems have strongly exponential complexity?|journal=[[Journal of Computer and System Sciences]]|volume=63|issue=4|year=2001|pages=512–530|doi=10.1006/jcss.2001.1774|doi-access=free}}</ref> घातीय समय परिकल्पना का तात्पर्य P ≠ एनपी से है।
+घातीय समय परिकल्पना (ईटीएच) यह है कि [[3SAT|3एसएटी]], प्रति खंड अधिकतम तीन अक्षर और ''एन'' चर के साथ [[संयोजक सामान्य रूप]] में बूलियन सूत्रों की संतुष्टि की समस्या को समय 2 में हल नहीं किया जा सकता है।ओ(एन). अधिक स्पष्ट रूप से, परिकल्पना यह है कि कुछ पूर्ण स्थिरांक है {{math|''c'' > 0}} ऐसा कि 3एसएटी का निर्णय समय 2 में नहीं किया जा सकता किसी नियतात्मक ट्यूरिंग मशीन द्वारा cn एम के साथ खंडों की संख्या को दर्शाते हुए, ईटीएच उस परिकल्पना के बराबर है कि केएसएटी को समय 2 में हल नहीं किया जा सकता है किसी भी पूर्णांक के लिए o(m) {{math|''k'' ≥ 3}}.<ref>{{Cite journal|first1=R.|last1=Impagliazzo|author1-link=Russell Impagliazzo|first2=R.|last2=Paturi|first3=F.|last3=Zane|title=Which problems have strongly exponential complexity?|journal=[[Journal of Computer and System Sciences]]|volume=63|issue=4|year=2001|pages=512–530|doi=10.1006/jcss.2001.1774|doi-access=free}}</ref> घातीय समय परिकल्पना का तात्पर्य P ≠ एनपी से है।
 == घातीय समय ==
-एक एल्गोरिदम को घातांकीय समय कहा जाता है, यदि ''T''(''n'') ऊपरी सीमा पर 2 से घिरा हो<sup>पॉली(n)</sup>, जहां पॉली(n) n में कुछ बहुपद है। अधिक औपचारिक रूप से, एल्गोरिथ्म घातीय समय है यदि T(n) O(2) से घिरा है<sup>n<sup>k</sup></sup>) कुछ स्थिरांक k के लिए। समस्याएँ जो नियतात्मक ट्यूरिंग मशीन पर घातीय समय एल्गोरिदम को स्वीकार करती हैं, जटिलता वर्ग बनाती हैं जिसे '[[EXP]]' के रूप में जाना जाता है।
+एक एल्गोरिदम को घातांकीय समय कहा जाता है, यदि ''T''(''n'') ऊपरी सीमा पर 2 से घिरा हो पॉली(n) है, जहां पॉली(n) n में कुछ बहुपद है। अधिक औपचारिक रूप से, एल्गोरिथ्म घातीय समय है यदि T(n) O(2)<sup>n<sup>k</sup></sup> से घिरा है) कुछ स्थिरांक k के लिए समस्याएँ जो नियतात्मक ट्यूरिंग मशीन पर घातीय समय एल्गोरिदम को स्वीकार करती हैं, जटिलता वर्ग बनाती हैं जिसे '[[EXP|ऍक्स्प]]' के रूप में जाना जाता है।
 :<math>\text{EXP} = \bigcup_{c \in \mathbb{R_+}} \text{DTIME}\left(2^{n^c}\right)</math>
-कभी-कभी, घातीय समय का उपयोग उन एल्गोरिदम को संदर्भित करने के लिए किया जाता है जिनमें T(n) = 2 होता है<sup>O(n)</sup>, जहां घातांक अधिकतम n का रैखिक फलन है। यह जटिलता वर्ग '[[ई (जटिलता)]]' को जन्म देता है।
+कभी-कभी, घातीय समय का उपयोग उन एल्गोरिदम को संदर्भित करने के लिए किया जाता है जिनमें T(n) = 2<sup>O(n)</sup> होता है, जहां घातांक अधिकतम n का रैखिक फलन है। यह जटिलता वर्ग '[[ई (जटिलता)]]' को जन्म देता है।
 :<math>\text{E} = \bigcup_{c \in \mathbb{N}} \text{DTIME}\left(2^{cn}\right)</math>
@@ Line 225: / Line 225: @@
 == भाज्य समय ==
-एक एल्गोरिथ्म को फैक्टोरियल समय कहा जाता है यदि ''T(n)'' [[भाज्य समारोह|भाज्य फलन]] ''n!'' से ऊपरी सीमा पर होता है। तथ्यात्मक समय घातीय समय (EXP) का उपसमुच्चय है क्योंकि <math> n! = O \left(2^{n^{1 + \epsilon}} \right)</math> सभी के लिए <math>\epsilon > 0</math>. चूँकि, यह E का उपसमुच्चय नहीं है।
+एक एल्गोरिथ्म को फैक्टोरियल समय कहा जाता है यदि ''T(n)'' [[भाज्य समारोह|भाज्य फलन]] ''n!'' से ऊपरी सीमा पर होता है। तथ्यात्मक समय घातीय समय (ऍक्स्प) का उपसमुच्चय है क्योंकि <math> n! = O \left(2^{n^{1 + \epsilon}} \right)</math> सभी के लिए <math>\epsilon > 0</math>. चूँकि, यह E का उपसमुच्चय नहीं है।
-फैक्टोरियल समय में चलने वाले एल्गोरिदम का उदाहरण [[बोगोसॉर्ट]] है, जो परीक्षण और त्रुटि पर आधारित कुख्यात सॉर्टिंग एल्गोरिदम है। बोगोसॉर्ट सूची में बार-बार फेरबदल करके n आइटमों की सूची को क्रमबद्ध करता है जब तक कि यह क्रमबद्ध न हो जाए। औसत स्थिति में, बोगोसॉर्ट एल्गोरिदम से गुजरने वाला प्रत्येक एन में से की जांच करेगा! n वस्तुओं का क्रम। यदि आइटम अलग-अलग हैं, तो केवल ही ऑर्डर को क्रमबद्ध किया जाता है। बोगोसॉर्ट [[अनंत बंदर प्रमेय]] के साथ विरासत साझा करता है।
+फैक्टोरियल समय में चलने वाले एल्गोरिदम का उदाहरण [[बोगोसॉर्ट]] है, जो परीक्षण और त्रुटि पर आधारित कुख्यात सॉर्टिंग एल्गोरिदम है। बोगोसॉर्ट सूची में बार-बार फेरबदल करके n आइटमों की सूची को क्रमबद्ध करता है जब तक कि यह क्रमबद्ध न हो जाए। औसत स्थिति में, बोगोसॉर्ट एल्गोरिदम से निकलने वाला प्रत्येक एन में से की जांच करेगा! n वस्तुओं का क्रम यदि आइटम अलग-अलग हैं, जिससे केवल ही ऑर्डर को क्रमबद्ध किया जाता है। बोगोसॉर्ट [[अनंत बंदर प्रमेय]] के साथ विरासत साझा करता है।
 == दोगुना घातीय समय ==
-यदि T(n) 2 से ऊपरी सीमा पर है तो एल्गोरिदम को [[दोहरा घातीय कार्य]] टाइम कहा जाता है<sup>2<sup>पॉली(n)</sup></sup>, जहां पॉली(n) n में कुछ बहुपद है। ऐसे एल्गोरिदम जटिलता वर्ग [[2-EXPTIME|2-एक्सटाइम]] से संबंधित हैं।
+यदि T(n) 2 से ऊपरी सीमा पर है तो एल्गोरिदम को [[दोहरा घातीय कार्य]] टाइम कहा जाता है  जहां पॉली(n) n में कुछ बहुपद है। ऐसे एल्गोरिदम जटिलता वर्ग [[2-EXPTIME|2-एक्सटाइम]] से संबंधित हैं।
 :<math>\mbox{2-EXPTIME} = \bigcup_{c \in \N} \mbox{DTIME}\left( 2^{2^{n^c}}\right)</math>
 प्रसिद्ध दोहरे घातीय समय एल्गोरिदम में सम्मिलित हैं:
 * [[प्रेस्बर्गर अंकगणित]] के लिए निर्णय प्रक्रियाएं
-* ग्रोबनेर आधार की गणना (सबसे व्यर्थ स्थिति में<ref>{{cite journal | last1 = Mayr | first1 = Ernst W. | author1-link = Ernst Mayr (computer scientist) | last2 = Meyer | first2 = Albert R. | author2-link = Albert R. Meyer | doi = 10.1016/0001-8708(82)90048-2 | issue = 3 | journal = [[Advances in Mathematics]] | mr = 683204 | pages = 305–329 | title = क्रमविनिमेय अर्धसमूहों और बहुपद आदर्शों के लिए शब्द समस्याओं की जटिलता| volume = 46 | year = 1982| doi-access = free }}</ref>)
+* ग्रोबनेर आधार की गणना (सबसे व्यर्थ स्थिति में <ref>{{cite journal | last1 = Mayr | first1 = Ernst W. | author1-link = Ernst Mayr (computer scientist) | last2 = Meyer | first2 = Albert R. | author2-link = Albert R. Meyer | doi = 10.1016/0001-8708(82)90048-2 | issue = 3 | journal = [[Advances in Mathematics]] | mr = 683204 | pages = 305–329 | title = क्रमविनिमेय अर्धसमूहों और बहुपद आदर्शों के लिए शब्द समस्याओं की जटिलता| volume = 46 | year = 1982| doi-access = free }}</ref>)
 * वास्तविक बंद फ़ील्ड पर क्वांटिफ़ायर उन्मूलन में कम से कम दोगुना घातीय समय लगता है,<ref>{{cite journal | last1 = Davenport | first1 = James H. | author1-link = James H. Davenport | last2 = Heintz | first2 = Joos | doi = 10.1016/S0747-7171(88)80004-X | issue = 1–2 | journal = [[Journal of Symbolic Computation]] | mr = 949111 | pages = 29–35 | title = वास्तविक परिमाणक उन्मूलन दोगुना घातीय है| volume = 5 | year = 1988| doi-access = free }}</ref> और इस समय में किया जा सकता है.<ref>{{cite conference | last = Collins | first = George E. | author-link = George E. Collins| editor-last = Brakhage | editor-first = H. | contribution = Quantifier elimination for real closed fields by cylindrical algebraic decomposition | doi = 10.1007/3-540-07407-4_17 | mr = 0403962 | pages = 134–183 | publisher = Springer | series = Lecture Notes in Computer Science | title = Automata Theory and Formal Languages: 2nd GI Conference, Kaiserslautern, May 20–23, 1975 | volume = 33 | year = 1975| doi-access = free }}</ref>
-== यह भी देखें ==
+== यह भी देखें                                                                                                                                                                                              ==
 * [[एल-नोटेशन]]
 * [[अंतरिक्ष जटिलता]]
-== संदर्भ ==
+== संदर्भ                                                                                                                                                                     ==
 {{Reflist|colwidth=33em}}

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 12:01, 4 July 2023

Contents

सामान्य समय जटिलताओं की तालिका