समय की जटिलता

"Running time" redirects here. For the film, see Running Time (film).

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

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

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

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

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

Further information: Computational complexity of mathematical operations

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

Name	Complexity class	Running time (T(n))	Examples of running times	Example algorithms
constant time		$O(1)$	10	Finding the median value in a sorted array of numbers. Calculating (−1)n
inverse Ackermann time		$O{\bigl (}\alpha (n){\bigr )}$		Amortized time per operation using a disjoint set
iterated logarithmic time		$O(\log ^{*}n)$		Distributed coloring of cycles
log-logarithmic		$O(\log \log n)$		Amortized time per operation using a bounded priority queue
logarithmic time	DLOGTIME	$O(\log n)$	$\log n$, $\log(n^{2})$	Binary search
polylogarithmic time		${\text{poly}}(\log n)$	$(\log n)^{2}$
fractional power		$O(n^{c})$ where $0<c<1$	$n^{\frac {1}{2}}$, $n^{\frac {2}{3}}$	Searching in a kd-tree
linear time		$O(n)$	n, $2n+5$	Finding the smallest or largest item in an unsorted array. Kadane's algorithm. Linear search
"n log-star n" time		$O(n\log ^{*}n)$		Seidel's polygon triangulation algorithm.
linearithmic time		$O(n\log n)$	$n\log n$, $\log n!$	Fastest possible comparison sort Fast Fourier transform.
quasilinear time		$n{\text{poly}}(\log n)$	$n\log ^{2}n$	Multipoint polynomial evaluation
quadratic time		$O(n^{2})$	$n^{2}$	Bubble sort, Insertion sort, Direct convolution
cubic time		$O(n^{3})$	$n^{3}$	Naive multiplication of two $n\times n$ matrices Calculating partial correlation.
polynomial time	P	$2^{O(\log n)}={\text{poly}}(n)$	$n^{2}+n$, $n^{10}$	Karmarkar's algorithm for linear programming AKS primality test
quasi-polynomial time	QP	$2^{{\text{poly}}(\log n)}$	$n^{\log \log n}$, $n^{\log n}$	Best-known O(log2n)-approximation algorithm for the directed Steiner tree problem, best known parity game solver, best known graph isomorphism algorithm
sub-exponential time (first definition)	SUBEXP	$O(2^{n^{\epsilon }})$ for all $\epsilon >0$		Contains BPP unless EXPTIME (see below) equals MA.
sub-exponential time (second definition)		$2^{o(n)}$	$2^{\sqrt[{3}]{n}}$	Best classical algorithm for integer factorization formerly-best algorithm for graph isomorphism
exponential time (with linear exponent)	E	$2^{O(n)}$	$1.1^{n}$, $10^{n}$	Solving the traveling salesman problem using dynamic programming
exponential time	EXPTIME	$2^{{\text{poly}}(n)}$	$2^{n}$, $2^{n^{2}}$	Solving matrix chain multiplication via brute-force search
factorial time		$O(n!)$	$n!$	Solving the traveling salesman problem via brute-force search
double exponential time	2-EXPTIME	$2^{2^{{\text{poly}}(n)}}$	$2^{2^{n}}$	Deciding the truth of a given statement in Presburger arithmetic

लगातार समय

"Constant time" redirects here. For programming technique to avoid a timing attack, see Timing attack § Avoidance.

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

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

लघुगणकीय समय

Further information: Logarithmic growth

कहा जाता है कि एक एल्गोरिदम लघुगणकीय समय लेता है $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. उदाहरण के लिए, एक प्रक्रिया जो किसी सूची के सभी तत्वों को जोड़ती है, उसे सूची की लंबाई के अनुपात में समय की आवश्यकता होती है, यदि जोड़ने का समय स्थिर है, या, कम से कम, एक स्थिरांक से घिरा हुआ है।

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

Quasilinear time

कहा जाता है कि एक एल्गोरिदम क्वासिलिनियर टाइम (जिसे लॉग-लीनियर टाइम भी कहा जाता है) में चलता है $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 बार (नोटेशन के लिए, देखें Big O notation § Family of Bachmann–Landau notations). उदाहरण के लिए, बाइनरी ट्री सॉर्ट प्रत्येक तत्व को सम्मिलित करके एक बाइनरी ट्री बनाता है 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$ बिट्स में और न केवल इनपुट में पूर्णांकों की संख्या पर।

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

जटिलता वर्ग

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

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

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

अतिबहुपद समय

यदि 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 के लिए कोई बहुपद समय एल्गोरिथ्म नहीं है जब तक कि 3SAT (और इस प्रकार सभी NP (जटिलता)) के लिए अर्ध-बहुपद समय एल्गोरिथ्म नहीं है। इसी तरह, कुछ समस्याएं हैं जिनके लिए हम अर्ध-बहुपद समय एल्गोरिदम जानते हैं, लेकिन कोई बहुपद समय एल्गोरिदम ज्ञात नहीं है। ऐसी समस्याएँ सन्निकटन एल्गोरिदम में उत्पन्न होती हैं; एक प्रसिद्ध उदाहरण निर्देशित स्टीनर वृक्ष समस्या है, जिसके लिए एक अर्ध-बहुपद समय सन्निकटन एल्गोरिथ्म है जो एक सन्निकटन कारक प्राप्त करता है $O(\log ^{3}n)$ (n शीर्षों की संख्या है), लेकिन ऐसे बहुपद समय एल्गोरिथ्म का अस्तित्व दिखाना एक खुली समस्या है।

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

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

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

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

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

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

पहली परिभाषा

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

${\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. 'SUBEPT' सभी पैरामीटरयुक्त समस्याओं का वर्ग है जो k में समय उप-घातीय और इनपुट आकार n में बहुपद में चलता है:

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

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

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

Main article: Exponential time hypothesis

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

घातीय समय

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

${\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! से ऊपरी सीमा पर होता है। तथ्यात्मक समय घातीय समय (EXP) का एक उपसमुच्चय है क्योंकि $n!=O\left(2^{n^{1+\epsilon }}\right)$ सभी के लिए $\epsilon >0$. हालाँकि, यह E का उपसमुच्चय नहीं है।

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

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

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

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

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

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

यह भी देखें

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