समय की जटिलता

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

File:Comparison computational complexity.svg

सामान्यतः एल्गोरिदम के विश्लेषण में उपयोग किए जाने वाले फलन के ग्राफ़, प्रत्येक फलन के लिए इनपुट आकार 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}$