समय की जटिलता

"रनिंग समय" redirects here. For द फ़िल्म, see रनिंग टाइम (फ़िल्म).

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

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

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

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

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

Further information: गणितीय संक्रियाओं की कम्प्यूटेशनल जटिलता

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

नाम	जटिलता वर्ग	संचालन समय (टी(एन))	प्रारंभ समय के उदाहरण	उदाहरण एल्गोरिदम
निरंतर समय		$O(1)$	10	संख्याओं की क्रमबद्ध सारणी में माध्य मान ज्ञात करना। की गणना (−1)n
एकरमैन समय का उलटा		$O{\bigl (}\alpha (n){\bigr )}$		एक असंयुक्त समुच्चय का उपयोग करके प्रति ऑपरेशन परिशोधित समय
पुनरावृत्त लघुगणकीय समय		$O(\log ^{*}n)$		साइकिलों का रंग-रोगन वितरित किया
लॉग-लघुगणक		$O(\log \log n)$		एक बंधी हुई प्राथमिकता कतार का उपयोग करके प्रति ऑपरेशन परिशोधित समय
लघुगणकीय समय	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)$	n, $2n+5$	किसी अवर्गीकृत सरणी में सबसे छोटी या सबसे बड़ी वस्तु खोज। कडेन का एल्गोरिदम। रेखीय खोज
"एन लॉग-स्टार एन" समय		$O(n\log ^{*}n)$		सीडेल का बहुभुज त्रिभुज एल्गोरिथ्म।
रैखिक अंकीय समय		$O(n\log n)$	$n\log n$, $\log n!$	सबसे तेज़ संभव तुलना प्रकार फास्ट फूरियर ट्रांसफॉर्म।
चतुर्रेखीय समय		$n{\text{poly}}(\log n)$	$n\log ^{2}n$	बहुपद बहुपद मूल्यांकन
द्विघात समय		$O(n^{2})$	$n^{2}$	बबल सॉर्ट, इंसर्शन सॉर्ट, डायरेक्ट कनवल्शन
घन समय		$O(n^{3})$	$n^{3}$	दो का नादान गुणन 𝑛×𝑛 मैट्रिक्स आंशिक सहसंबंध की गणना.
बहुपद समय	P	$2^{O(\log n)}={\text{poly}}(n)$	$n^{2}+n$, $n^{10}$	रैखिक प्रोग्रामिंग के लिए करमरकर का एल्गोरिदम एकेएस प्रारंभिक परीक्षण
अर्ध-बहुपद समय	क्यूपी	$2^{{\text{poly}}(\log n)}$	$n^{\log \log n}$, $n^{\log n}$	निर्देशित स्टीनर ट्री समस्या के लिए सबसे प्रसिद्ध O(log2n)-सन्निकटन एल्गोरिथ्म, सबसे प्रसिद्ध समता गेम सॉल्वर, सबसे प्रसिद्ध ग्राफ समरूपता एल्गोरिथ्म
उप-घातांकीय समय (प्रथम परिभाषा)	सबएक्सपी	$O(2^{n^{\epsilon }})$ for all $\epsilon >0$		इसमें बीपीपी साम्मिलित है जब तक कि एक्सएक्सएक्सटीआई (नीचे देखें) एमए के सामान्य न हो जाए.
उप-घातांकीय समय (दूसरी परिभाषा)		$2^{o(n)}$	$2^{\sqrt[{3}]{n}}$	पूर्णांक गुणनखंडन के लिए सर्वोत्तम मौलिक एल्गोरिदम ग्राफ समरूपता के लिए पूर्व-सर्वश्रेष्ठ एल्गोरिदम
घातीय समय (रेखीय घातांक सहित)	E	$2^{O(n)}$	$1.1^{n}$, $10^{n}$	डायनेमिक प्रोग्रामिंग का उपयोग करके ट्रैवलिंग सेल्समैन की समस्या का समाधान
घातीय समय	एक्सटाइम	$2^{{\text{poly}}(n)}$	$2^{n}$, $2^{n^{2}}$	ब्रूट-फोर्स खोज के माध्यम से मैट्रिक्स श्रृंखला गुणन को हल करना
भाज्य समय		$O(n!)$	$n!$	ब्रूट-फोर्स सर्च के माध्यम से ट्रैवलिंग सेल्समैन की समस्या का समाधान
दोहरा घातीय समय	2-एक्सटाइम	$2^{2^{{\text{poly}}(n)}}$	$2^{2^{n}}$	प्रेस्बर्गर अंकगणित में दिए गए कथन की सत्यता का निर्णय करना

निरंतर समय

"निरंतर समय" redirects here. For टाइमिंग आक्रमण से बचने के लिए प्रोग्रामिंग तकनीक, see आक्रमण का समय § बचाव.

एक एल्गोरिदम को स्थिर समय कहा जाता है (इसे इस रूप में भी लिखा जाता है)। ${\textstyle O(1)}$ समय) यदि का मान ${\textstyle T(n)}$ (एल्गोरिदम की जटिलता) मान से बंधी है जो इनपुट के आकार पर निर्भर नहीं करती है। उदाहरण के लिए, किसी सरणी डेटा संरचना में किसी तत्व तक पहुँचने में निरंतर समय लगता है क्योंकि इसे खोजने के लिए केवल निर्देश (कंप्यूटर विज्ञान) का पालन करना पड़ता है। इसी प्रकार, आरोही क्रम में क्रमबद्ध सरणी में न्यूनतम मान ज्ञात करना; यह पहला तत्व है. चूँकि, अव्यवस्थित सरणी में न्यूनतम मान खोज निरंतर समय का संचालन नहीं है क्योंकि न्यूनतम मान निर्धारित करने के लिए सरणी में प्रत्येक तत्व (गणित) पर स्कैनिंग की आवश्यकता होती है। इसलिए यह रैखिक समय संक्रिया है ${\textstyle O(n)}$ समय चूँकि, यदि तत्वों की संख्या पहले से ज्ञात है और बदलती नहीं है, तो ऐसे एल्गोरिदम को अभी भी निरंतर समय में चलने के लिए कहा जा सकता है।

स्थिर समय नाम के अतिरिक्त, चलने का समय समस्या के आकार से स्वतंत्र नहीं होना चाहिए, किन्तु चलने के समय की ऊपरी सीमा समस्या के आकार से स्वतंत्र होनी चाहिए। उदाहरण के लिए, कार्य के मूल्यों का आदान-प्रदान होता है a और b यदि आवश्यक हो तो कि ${\textstyle a\leq b}$ इसे स्थिर समय कहा जाता है, तथापि समय इस पर निर्भर हो सकता है कि यह पहले से ही सत्य है या नहीं ${\textstyle a\leq b}$. चूँकि, कुछ स्थिरांक है t ऐसा कि आवश्यक समय सदैव अधिकतम t होता है .

लघुगणकीय समय

Further information: लघुगणकीय वृद्धि

कहा जाता है कि एल्गोरिदम लघुगणकीय समय $T(n)=O(\log n)$ लेता है .चूँकि $\log _{a}n$ और $\log _{b}n$ लॉगरिदमिक पहचानों से संबंधित हैं आधार बदलना, और ऐसे बिग ओ नोटेशन बड़े ओ वर्गीकरण के लिए स्थिरांक द्वारा गुणा, लॉगरिदमिक-समय एल्गोरिदम के लिए मानक उपयोग है $O(\log n)$ की अभिव्यक्ति में प्रदर्शित होने वाले लघुगणक के आधार की परवाह किए बिना T उपयोग किया जाता है.

लॉगरिदमिक समय लेने वाले एल्गोरिदम सामान्यतः बाइनरी पेड़ों पर संचालन में या बाइनरी खोज का उपयोग करते समय पाए जाते हैं।

एक $O(\log n)$ एल्गोरिदम को अत्यधिक कुशल माना जाता है, क्योंकि संचालन की संख्या और इनपुट के आकार का अनुपात घट जाता है और शून्य हो जाता है n बढ़ती है। एल्गोरिदम जिसे अपने इनपुट के सभी तत्वों तक पहुंच चाहिए, वह लॉगरिदमिक समय नहीं ले सकता है, क्योंकि आकार के इनपुट को पढ़ने में लगने वाला समय n के क्रम n का है .

शब्दकोश खोज द्वारा लघुगणकीय समय का उदाहरण दिया गया है। शब्दकोश पर विचार करें (डेटा संरचना) D जिसमें है n प्रविष्टियाँ, वर्णानुक्रम के अनुसार क्रमबद्ध। हम ऐसा मानते हैं, के लिए $1\leq k\leq n$, कोई भी पहुंच सकता है k निरंतर समय में शब्दकोश कीवीं प्रविष्टि माना $D(k)$ इसे निरूपित करें kफिर कोशिश करो। इन परिकल्पनाओं के अनुसार, यह देखने के लिए परीक्षण करें कि क्या कोई शब्द w शब्दकोश में लघुगणकीय समय में किया जा सकता है: विचार करें $D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$, जहाँ $\lfloor \;\rfloor$ फ्लोर फलन को दर्शाता है। यदि $w=D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$, तो हमारा काम हो गया अन्यथा, यदि $w<D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$, शब्दकोश के बाएँ आधे भाग में इसी प्रकार खोज जारी रखें, अन्यथा शब्दकोश के दाएँ आधे भाग के साथ भी इसी प्रकार जारी रखें। यह एल्गोरिदम उस विधि के समान है जिसका उपयोग अधिकांशतः पेपर डिक्शनरी में प्रविष्टि खोजने के लिए किया जाता है।

बहुगणितीय समय

कहा जाता है कि एल्गोरिदम बहुगणितीय फलन समय में चलता है यदि उसका समय $T(n)$ है $O{\bigl (}(\log n)^{k}{\bigr )}$ कुछ स्थिरांक के लिए k. इसे लिखने का दूसरी $O(\log ^{k}n)$ विधि है .

उदाहरण के लिए, मैट्रिक्स श्रृंखला गुणन को समानांतर रैंडम-एक्सेस मशीन पर पॉलीलॉगरिदमिक समय में हल किया जा सकता है, और ग्राफ़ (असतत गणित) गतिशील कनेक्टिविटी विधि से प्लानरिटी परीक्षण हो सकता है $O(\log ^{3}n)$ प्रति डालने/हटाने की कार्रवाई में लगने वाला समय है।

उप-रैखिक समय

कहा जाता है कि एल्गोरिदम सब-लीनियर टाइम $T(n)=o(n)$ (अधिकांशतः सब-लीनियर टाइम लिखा जाता है) में चलता है . विशेष रूप से इसमें ऊपर परिभाषित समय जटिलताओं वाले एल्गोरिदम सम्मिलित हैं।

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

विशिष्ट शब्द सबलाइनियर टाइम एल्गोरिदम सामान्यतः उन एल्गोरिदम के लिए आरक्षित होता है जो उपरोक्त के विपरीत होते हैं क्योंकि वे मौलिक सीरियल मशीन मॉडल पर चलते हैं और इनपुट पर पूर्व धारणाओं की अनुमति नहीं होती है। चूँकि, उन्हें यादृच्छिक एल्गोरिदम होने की अनुमति है, और वास्तव में सबसे तुच्छ कार्यों को छोड़कर सभी के लिए यादृच्छिक किया जाना चाहिए।

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

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

रेखीय समय

कहा जाता है कि एल्गोरिदम रैखिक समय लेता है, या $O(n)$ समय, यदि इसकी समय जटिलता है $O(n)$. अनौपचारिक रूप से, इसका कारण यह है कि इनपुट के आकार के साथ चलने का समय अधिकतम रैखिक रूप से बढ़ता है। अधिक स्पष्ट रूप से, इसका कारण यह है कि स्थिरांक है c ऐसा कि चलने का समय अधिकतम हो $cn$ आकार के प्रत्येक इनपुट के लिए n. उदाहरण के लिए, प्रक्रिया जो किसी सूची के सभी तत्वों को जोड़ती है, उसे सूची की लंबाई के अनुपात में समय की आवश्यकता होती है, यदि जोड़ने का समय स्थिर है, या, कम से कम, स्थिरांक से घिरा हुआ है।

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

चतुर्रेखीय समय

कहा जाता है कि एल्गोरिदम क्वासिलिनियर टाइम $T(n)=O(n\log ^{k}n)$ (जिसे लॉग-लीनियर टाइम भी कहा जाता है) में चलता है कुछ सकारात्मक स्थिरांक के लिए k; रैखिक अंकीय समय $k=1$ स्थिति है . सॉफ्ट ओ अंकन का उपयोग करते हुए ये एल्गोरिदम हैं ${\tilde {O}}(n)$. क्वासिलिनियर टाइम एल्गोरिदम भी हैं $O(n^{1+\varepsilon })$ प्रत्येक स्थिरांक के लिए $\varepsilon >0$ और इस प्रकार किसी भी बहुपद समय एल्गोरिदम की तुलना में तेज़ चलता है जिसकी समय सीमा में पद सम्मिलित होता है $n^{c}$ किसी के लिए $c>1$.

क्वासिलिनियर समय में चलने वाले एल्गोरिदम में सम्मिलित हैं:

• इन-प्लेस मर्ज सॉर्ट, $O(n\log ^{2}n)$
• त्वरित वर्गीकरण, $O(n\log n)$, इसके यादृच्छिक संस्करण में, चलने का समय $O(n\log n)$ होता है सबसे व्यर्थ स्थिति वाले इनपुट की अपेक्षा में। इसके गैर-यादृच्छिक संस्करण $O(n\log n)$ में है औसत स्थिति की जटिलता पर विचार करते समय ही चलने का समय है।
• हीपसॉर्ट, $O(n\log n)$, सबसे व्यर्थ स्थिति में मर्ज़ सॉर्ट , परिचय, बाइनरी ट्री सॉर्ट, स्मूथसॉर्ट, धैर्य सॉर्टिंग आदि
• फास्ट फूरियर रूपांतरण, $O(n\log n)$
• स्पंज सरणी गणना, $O(n\log n)$

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

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

उप-द्विघात समय

एक एल्गोरिथ्म को उपवर्गिक समय कहा जाता है यदि $T(n)=o(n^{2})$.

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

बहुपद समय

एक एल्गोरिदम को बहुपद समय का कहा जाता है यदि इसका चलने का समय एल्गोरिदम के लिए इनपुट के आकार में बहुपद अभिव्यक्ति द्वारा ऊपरी सीमा पर होता है, अर्थात, T(n) = O(n^k) कुछ सकारात्मक स्थिरांक k के लिए। निर्णय समस्या जिसके लिए नियतात्मक बहुपद-समय एल्गोरिथ्म उपस्थित है, जटिलता वर्ग पी (जटिलता) से संबंधित है, जो कम्प्यूटेशनल जटिलता सिद्धांत के क्षेत्र में केंद्रीय है। कोबम की थीसिस में कहा गया है कि बहुपद समय सुव्यवस्थित, व्यवहार्य, कुशल या तेज़ का पर्याय है।

बहुपद-समय एल्गोरिदम के कुछ उदाहरण:

• n पूर्णांकों पर चयन सॉर्ट सॉर्टिंग एल्गोरिदम $An^{2}$ निष्पादित करता है कुछ स्थिरांक A के लिए संचालन इस प्रकार यह समय $O(n^{2})$ में चलता है और बहुपद-समय एल्गोरिथ्म है।
• सभी मूलभूत अंकगणितीय संक्रियाएं (जोड़, घटाव, गुणा, भाग और तुलना) बहुपद समय में की जा सकती हैं।
• ग्राफ़ (अलग गणित) में अधिकतम मिलान बहुपद समय में पाया जा सकता है।

प्रबल और दुर्बल बहुपद समय

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

गणना के अंकगणितीय मॉडल में दृढ़तापूर्वक बहुपद समय को परिभाषित किया गया है। गणना के इस मॉडल में मूलभूत अंकगणितीय परिचालन (जोड़, घटाव, गुणा, भाग और तुलना) को ऑपरेंड के आकार की परवाह किए बिना निष्पादित करने के लिए इकाई समय कदम उठाना पड़ता है। एल्गोरिथ्म दृढ़ता से बहुपद समय में चलता है यदि:

1. गणना के अंकगणितीय मॉडल में संचालन की संख्या इनपुट उदाहरण में पूर्णांकों की संख्या में बहुपद से घिरी होती है; और
2. एल्गोरिदम द्वारा उपयोग किया गया स्थान इनपुट के आकार में बहुपद से घिरा हुआ है।

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

चूँकि, पहली नियम के लिए, ऐसे एल्गोरिदम हैं जो बाइनरी-एन्कोडेड इनपुट की लंबाई में बहुपद से बंधे कई ट्यूरिंग मशीन चरणों में चलते हैं, किन्तु इनपुट की संख्या में बहुपद से बंधे कई अंकगणितीय संचालन नहीं लेते हैं नंबर. दो पूर्णांकों के सबसे बड़े सामान्य भाजक की गणना के लिए यूक्लिडियन एल्गोरिथ्म उदाहरण है। दो पूर्णांक दिए गए हैं $a$ और $b$, एल्गोरिथम निष्पादित करता है $O(\log a+\log b)$ संख्याओं पर अंकगणितीय संक्रियाएँ अधिक से अधिक $O(\log a+\log b)$ बिट्स साथ ही, अंकगणितीय संक्रियाओं की संख्या को इनपुट में पूर्णांकों की संख्या से सीमित नहीं किया जा सकता है (जो इस स्थिति में स्थिर है, इनपुट में सदैव केवल दो पूर्णांक होते हैं)। बाद के अवलोकन के कारण, एल्गोरिदम दृढ़ता से बहुपद समय में नहीं चलता है। इसका वास्तविक चलने का समय लंबाई पर निर्भर करता है $a$ और $b$ बिट्स में और न केवल इनपुट में पूर्णांकों की संख्या पर निर्भर करता है।

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

जटिलता वर्ग

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

• पी (जटिलता): निर्णय समस्याओं की जटिलता वर्ग जिसे बहुपद समय में नियतात्मक ट्यूरिंग मशीन पर हल किया जा सकता है
• एनपी (जटिलता): निर्णय समस्याओं की जटिलता वर्ग जिसे बहुपद समय में गैर-नियतात्मक ट्यूरिंग मशीन पर हल किया जा सकता है
• ज़ेडपीपी (जटिलता): निर्णय समस्याओं की जटिलता वर्ग जिसे बहुपद समय में संभाव्य ट्यूरिंग मशीन पर शून्य त्रुटि के साथ हल किया जा सकता है
• आरपी (जटिलता): निर्णय समस्याओं की जटिलता वर्ग जिसे बहुपद समय में संभाव्य ट्यूरिंग मशीन पर पक्ष त्रुटि के साथ हल किया जा सकता है।
• बीपीपी (जटिलता): निर्णय समस्याओं की जटिलता वर्ग जिसे बहुपद समय में संभाव्य ट्यूरिंग मशीन पर दो-पक्ष त्रुटि के साथ हल किया जा सकता है
• बीक्यूपी: निर्णय समस्याओं की जटिलता वर्ग जिसे बहुपद समय में क्वांटम ट्यूरिंग मशीन पर दो-पक्ष त्रुटि से हल किया जा सकता है

पी नियतात्मक मशीन पर सबसे छोटा समय-जटिलता वर्ग है जो मशीन मॉडल परिवर्तनों के संदर्भ में सशक्त (कंप्यूटर विज्ञान) है। (उदाहरण के लिए, एकल-टेप ट्यूरिंग मशीन से मल्टी-टेप मशीन में परिवर्तन से द्विघात गति हो सकती है, किन्तु कोई भी एल्गोरिदम जो मॉडल के अनुसार बहुपद समय में चलता है, वह दूसरे मॉडल पर भी ऐसा करता है।) कोई भी दी गई अमूर्त मशीन ऐसा करेगी समस्याओं के अनुरूप जटिलता वर्ग है जिसे उस मशीन पर बहुपद समय में हल किया जा सकता है।

अतिबहुपद समय

यदि T(n) ऊपर किसी बहुपद से घिरा नहीं है तो एल्गोरिदम को सुपरपोलिनोमियल समय लेने के लिए परिभाषित किया गया है। बड़े O अंकन फ़ैमिली ऑफ़ बाचमैन-लैंडौ अंकन का उपयोग करते हुए, यह ω(n^c) सभी स्थिरांकों के लिए समय c, जहां n इनपुट पैरामीटर है, सामान्यतः इनपुट में बिट्स की संख्या है।

उदाहरण के लिए, एल्गोरिदम जो 2ⁿ के लिए चलता है आकार n के इनपुट पर चरणों के लिए सुपरपोलिनोमियल समय (अधिक विशेष रूप से, घातीय समय) की आवश्यकता होती है।

एक एल्गोरिथ्म जो घातीय संसाधनों का उपयोग करता है वह स्पष्ट रूप से सुपरपोलिनोमियल है, किन्तु कुछ एल्गोरिदम केवल बहुत ही अशक्त रूप से सुपरपोलिनोमियल हैं। उदाहरण के लिए, एडलमैन-पोमेरेन्स-रुमली प्राइमैलिटी टेस्ट चलता है n^{O(log log n)} एन-बिट इनपुट पर समय; यह अधिक बड़े n के लिए किसी भी बहुपद की तुलना में तेजी से बढ़ता है, किन्तु इनपुट आकार को अव्यवहारिक रूप से बड़ा होना चाहिए, इससे पहले कि यह छोटी डिग्री वाले बहुपद पर हावी नही हो सकता है।

एक एल्गोरिथ्म जिसके लिए सुपरपोलिनोमियल समय की आवश्यकता होती है वह जटिलता वर्ग 'पी (जटिलता)' से बाहर होता है। कोबम की थीसिस बताती है कि ये एल्गोरिदम अव्यावहारिक हैं, और कई स्थितियों में हैं भी। चूंकि पी बनाम एनपी समस्या अनसुलझी है, इसलिए यह अज्ञात है कि एनपी-पूर्ण समस्याओं के लिए सुपरपोलिनोमियल समय की आवश्यकता है या नहीं है।

अर्ध-बहुपद समय

अर्ध-बहुपद समय एल्गोरिदम ऐसे एल्गोरिदम हैं जो बहुपद समय से अधिक समय तक चलते हैं, फिर भी घातीय समय तक इतने लंबे नहीं होते हैं। अर्ध-बहुपद समय एल्गोरिदम का सबसे व्यर्थ स्थिति चलने का समय है $2^{O(\log ^{c}n)}$ कुछ के लिए तय किया गया $c>0$. के लिए $c=1$ हमें बहुपद समय एल्गोरिथ्म मिलता है $c<1$ हमें सब-लीनियर टाइम एल्गोरिदम मिलता है।

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

अर्ध-बहुपद समय समाधानों के साथ अन्य कम्प्यूटेशनल समस्याओं, किन्तु कोई ज्ञात बहुपद समय समाधान में लगाया हुआ गुट समस्या सम्मिलित नहीं है, जिसमें लक्ष्य क्लिक और यादृच्छिक ग्राफ के मिलन में क्लिक समस्या को हल करना है। यद्यपि अर्ध-बहुपद रूप से हल करने योग्य, यह अनुमान लगाया गया है कि प्लांटेड क्लिक समस्या का कोई बहुपद समय समाधान नहीं है; इस लगाए गए क्लिक अनुमान का उपयोग कम्प्यूटेशनल गेम सिद्धांत, प्रोपर्टी परीक्षण और यंत्र अधिगम में कई अन्य समस्याओं की कठिनाई को सिद्ध करने के लिए कम्प्यूटेशनल कठोरता धारणा के रूप में किया गया है।

जटिलता वर्ग क्यूपी में अर्ध-बहुपद समय एल्गोरिदम वाली सभी समस्याएं सम्मिलित हैं। इसे डीटाइम के ​​संदर्भ में निम्नानुसार परिभाषित किया जा सकता है।

${\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{\log ^{c}n}\right)$

एनपी-पूर्ण समस्याओं से संबंध

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

उप-घातांकीय समय

इन्फ्रा-एक्सपोनेंशियल या सब-एक्सपोनेंशियल टाइम शब्द का उपयोग यह व्यक्त करने के लिए किया जाता है कि कुछ एल्गोरिदम का चलने का समय किसी भी बहुपद की तुलना में तेजी से बढ़ सकता है किन्तु अभी भी एक्सपोनेंशियल से अधिक छोटा है। इस अर्थ में, जिन समस्याओं में उप-घातीय समय एल्गोरिदम होते हैं, वे उन समस्याओं की तुलना में कुछ सीमा तक अधिक सुव्यवस्थित होती हैं जिनमें केवल घातीय एल्गोरिदम होते हैं। उप-घातांक की स्पष्ट परिभाषा पर सामान्यतः सहमति नहीं है, और हम नीचे दो सबसे व्यापक रूप से उपयोग किए जाने वाले को सूचीबद्ध करते हैं।

पहली परिभाषा

एक समस्या को उप-घातीय समय में हल करने योग्य कहा जाता है यदि इसे प्रारंभ समय में हल किया जा सकता है जिसका लघुगणक किसी दिए गए बहुपद से छोटा हो जाता है। अधिक स्पष्ट रूप से, समस्या प्रत्येक के लिए उप-घातीय समय में है ε > 0 एल्गोरिदम उपस्थित है जो समस्या को समय O(2)^nε में हल करता है). ऐसी सभी समस्याओं का समूह जटिलता वर्ग 'सबएक्सपी' है जिसे डीटाइम के ​​​​संदर्भ में निम्नानुसार परिभाषित किया जा सकता है।

${\text{SUBEXP}}=\bigcap _{\varepsilon >0}{\text{DTIME}}\left(2^{n^{\varepsilon }}\right)$

उप-घातांक की यह धारणा ε के संदर्भ में इस अर्थ में गैर-समान है कि ε इनपुट का हिस्सा नहीं है और प्रत्येक ε के पास समस्या के लिए अपना स्वयं का एल्गोरिदम हो सकता है।

दूसरी परिभाषा

कुछ लेखक उप-घातीय समय को चलने वाले समय $2^{o(n)}$ के रूप में परिभाषित करते हैं . यह परिभाषा उप-घातीय समय की पहली परिभाषा की तुलना में बड़े चलने वाले समय की अनुमति देती है। ऐसे उप-घातीय समय एल्गोरिदम का उदाहरण पूर्णांक गुणनखंडन के लिए सबसे प्रसिद्ध मौलिक एल्गोरिदम है, सामान्य संख्या फ़ील्ड चलनी, जो $2^{{\tilde {O}}(n^{1/3})}$, समय के बारे में चलता है जहां इनपुट की लंबाई है n. अन्य उदाहरण ग्राफ समरूपता समस्या थी, जिसे 1982 से 2016 तक के सबसे प्रसिद्ध एल्गोरिदम $2^{O\left({\sqrt {n\log n}}\right)}$. में हल किया गया था चूँकि, कंप्यूटिंग के सिद्धांत पर संगोष्ठी 2016 में अर्ध-बहुपद समय एल्गोरिथ्म प्रस्तुत किया गया था।

इससे फर्क पड़ता है कि क्या एल्गोरिदम को उदाहरण के आकार, शीर्षों की संख्या या किनारों की संख्या में उप-घातीय होने की अनुमति है। पैरामीटरयुक्त जटिलता में, जोड़ियों पर विचार करके इस अंतर को स्पष्ट किया जाता है $(L,k)$ निर्णय समस्याओं और मापदंडों का k. 'सबेप्ट' सभी पैरामीटरयुक्त समस्याओं का वर्ग है जो k में समय उप-घातीय और इनपुट आकार n में बहुपद में चलता है:

${\text{SUBEPT}}={\text{DTIME}}\left(2^{o(k)}\cdot {\text{poly}}(n)\right).$

अधिक स्पष्ट रूप से, सबेप्ट $(L,k)$ सभी पैरामीटरयुक्त समस्याओं का वर्ग है जिसके लिए गणना योग्य फलन है $f:\mathbb {N} \to \mathbb {N}$ साथ $f\in o(k)$ और एल्गोरिदम जो $2^{f(k)}\cdot {\text{poly}}(n)$ समय में एल तय करता है .

घातीय समय परिकल्पना

Main article: घातांकीय समय परिकल्पना

घातीय समय परिकल्पना (ईटीएच) यह है कि 3एसएटी, प्रति खंड अधिकतम तीन अक्षर और एन चर के साथ संयोजक सामान्य रूप में बूलियन सूत्रों की संतुष्टि की समस्या को समय 2 में हल नहीं किया जा सकता है।ओ(एन). अधिक स्पष्ट रूप से, परिकल्पना यह है कि कुछ पूर्ण स्थिरांक है c > 0 ऐसा कि 3एसएटी का निर्णय समय 2 में नहीं किया जा सकता किसी नियतात्मक ट्यूरिंग मशीन द्वारा cn एम के साथ खंडों की संख्या को दर्शाते हुए, ईटीएच उस परिकल्पना के बराबर है कि केएसएटी को समय 2 में हल नहीं किया जा सकता है किसी भी पूर्णांक के लिए o(m) k ≥ 3. घातीय समय परिकल्पना का तात्पर्य P ≠ एनपी से है।

घातीय समय

एक एल्गोरिदम को घातांकीय समय कहा जाता है, यदि T(n) ऊपरी सीमा पर 2 से घिरा हो पॉली(n) है, जहां पॉली(n) n में कुछ बहुपद है। अधिक औपचारिक रूप से, एल्गोरिथ्म घातीय समय है यदि T(n) O(2)^nk से घिरा है) कुछ स्थिरांक k के लिए समस्याएँ जो नियतात्मक ट्यूरिंग मशीन पर घातीय समय एल्गोरिदम को स्वीकार करती हैं, जटिलता वर्ग बनाती हैं जिसे 'ऍक्स्प' के रूप में जाना जाता है।

${\text{EXP}}=\bigcup _{c\in \mathbb {R_{+}} }{\text{DTIME}}\left(2^{n^{c}}\right)$

कभी-कभी, घातीय समय का उपयोग उन एल्गोरिदम को संदर्भित करने के लिए किया जाता है जिनमें T(n) = 2^O(n) होता है, जहां घातांक अधिकतम n का रैखिक फलन है। यह जटिलता वर्ग 'ई (जटिलता)' को जन्म देता है।

${\text{E}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{cn}\right)$

भाज्य समय

एक एल्गोरिथ्म को फैक्टोरियल समय कहा जाता है यदि T(n) भाज्य फलन n! से ऊपरी सीमा पर होता है। तथ्यात्मक समय घातीय समय (ऍक्स्प) का उपसमुच्चय है क्योंकि $n!=O\left(2^{n^{1+\epsilon }}\right)$ सभी के लिए $\epsilon >0$. चूँकि, यह E का उपसमुच्चय नहीं है।

फैक्टोरियल समय में चलने वाले एल्गोरिदम का उदाहरण बोगोसॉर्ट है, जो परीक्षण और त्रुटि पर आधारित कुख्यात सॉर्टिंग एल्गोरिदम है। बोगोसॉर्ट सूची में बार-बार फेरबदल करके n आइटमों की सूची को क्रमबद्ध करता है जब तक कि यह क्रमबद्ध न हो जाए। औसत स्थिति में, बोगोसॉर्ट एल्गोरिदम से निकलने वाला प्रत्येक एन में से की जांच करेगा! n वस्तुओं का क्रम यदि आइटम अलग-अलग हैं, जिससे केवल ही ऑर्डर को क्रमबद्ध किया जाता है। बोगोसॉर्ट अनंत बंदर प्रमेय के साथ विरासत साझा करता है।

दोगुना घातीय समय

यदि T(n) 2 से ऊपरी सीमा पर है तो एल्गोरिदम को दोहरा घातीय कार्य टाइम कहा जाता है जहां पॉली(n) n में कुछ बहुपद है। ऐसे एल्गोरिदम जटिलता वर्ग 2-एक्सटाइम से संबंधित हैं।

${\mbox{2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{2^{n^{c}}}\right)$

प्रसिद्ध दोहरे घातीय समय एल्गोरिदम में सम्मिलित हैं:

• प्रेस्बर्गर अंकगणित के लिए निर्णय प्रक्रियाएं
• ग्रोबनेर आधार की गणना (सबसे व्यर्थ स्थिति में )
• वास्तविक बंद फ़ील्ड पर क्वांटिफ़ायर उन्मूलन में कम से कम दोगुना घातीय समय लगता है, और इस समय में किया जा सकता है.

यह भी देखें

• एल-नोटेशन
• अंतरिक्ष जटिलता