समय की जटिलता

"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)}=$