समय जटिलता

thumb|कलनविधियों के विश्लेषण में काम आने वाले सामान्य फलनों का आरेख, प्रत्येक फलन के लिए n आकार के निवेश के लिए N संक्रियाओं वाला परिणाम दिखाया गया है। सैद्धान्तिक कंप्यूटर विज्ञान में समय जटिलता (time complexity) उस गणनीय जटिलता को कहते हैं जो किसी अल्गोरिद्म को चलने में लगने वाले कंप्यूटर समय की मात्रा को वर्णित करता है। यदि प्रत्येक मूलभूत संक्रिया को पूर्ण करने में निश्चित समय लगता हो तो समय जटिलता को सामान्यतः अल्गोरिद्म द्वारा किये गये मूलभूत संक्रियाओं की संख्या की गणना से प्राक्कलित किया जाता है। अतः अल्गोरिद्म द्वारा लगने वाले समय की मात्रा और मूलभूत संक्रियाओं की संख्या नियत गुणक से सम्बंधित होते हैं। भिन्न-भिन्न निवेश के आकार के अनुसार अल्गोरिद्म के चलने का समय बदलता रहता है। अतः किसी दिये गये आकार के निवेश के लिए आवश्यक समय की मात्रा की सबसे खराब स्थिति में लगने वाले समय को उपरोक्त समय से से सन्दर्भित किया जाता है। प्रत्येक स्थिति में समय जटिलता को निवेश के आकार के फलन के रूप में परिभाषित किया जा सकता है। बहुपद समय किसी एलगोरिद्म को बहुपद समय कहा जाता है यदि किसी एलगोरिद्म के लिए निवेशी बहुपद व्यंजक द्वारा इसके चलने में लगने वाला समय उपरी परिबद्ध है। अर्थात् किसी धनात्मक संख्या k के लिए T(n) = O(nk) है।सिप्सर माइकल :en:Michael Sipser Introduction to the Theory of Computation https://archive.org/details/introductiontoth0000mich 2006 Course Technology Inc 0-619-21764-2 Papadimitriou Christos H. Christos H. Papadimitriou Computational complexity https://archive.org/details/computationalcom0000papa 1994 Addison-Wesley Reading, Mass. 0-201-53082-1 निश्चयात्मक बहुपद समय एल्गोरिद्म के लिए समस्या जटिलता वर्ग P से आती है जो गणनीय समिश्र सिद्धान्त के क्षेत्र में प्रमुख है। कोबम की थीसिस के अनुसार बहुपद समय के अन्य प्रयायवाची शब्द "सुव्यवस्थित", "व्यवहार्य", "कुशल", या "तेज" हैं।Cobham Alan Alan Cobham (mathematician) 1965 The intrinsic computational difficulty of functions Proc. Logic, Methodology, and Philosophy of Science II North Holland सन्दर्भ श्रेणी:अभिकलन का सिद्धांत श्रेणी:समय