स्पर्शोन्मुख कम्प्यूटेशनल जटिलता: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कोम्प्लेक्ससिटी | [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कोम्प्लेक्ससिटी थ्योरी]] में, एसिम्प्टोटिक कम्प्यूटेशनल कोम्प्लेक्ससिटी [[कलन विधि|ऐल्गरिदम विधि]] और [[कम्प्यूटेशनल समस्या]]ओं की कम्प्यूटेशनल कोम्प्लेक्ससिटी के आकलन के लिए एसिम्प्टोटिक विश्लेषण का उपयोग है, जो समान्यत: [[बड़ा ओ अंकन|बिग ओ नोटेसन]] के उपयोग से जुड़ा होता है। | ||
==दायरा== | ==दायरा== | ||
[[कम्प्यूटेशनल संसाधन|कम्प्यूटेशनल रिसोर्स]] के संबंध में, एसिम्प्टोटिक टाइम कोम्प्लेक्ससिटी | [[कम्प्यूटेशनल संसाधन|कम्प्यूटेशनल रिसोर्स]] के संबंध में, एसिम्प्टोटिक टाइम कोम्प्लेक्ससिटी और एसिम्प्टोटिक [[अंतरिक्ष जटिलता|स्पेस कोम्प्लेक्ससिटी]] का समान्यत: अनुमान लगाया जाता है। अन्य असिम्प्टोटीकली एसटीम्टेड से अनुमानित व्यवहार में [[सर्किट जटिलता|सर्किट कोम्प्लेक्ससिटी]] और [[समानांतर गणना|परेल्लेल कम्पूटैस्नल]] के विभिन्न उपाय सम्मिलित हैं, जैसे ([[समानांतर गणना|परेल्लेल]]) प्रोसेसर की संख्या। | ||
[[ज्यूरिस हार्टमैनिस]] और रिचर्ड ई. स्टर्न्स द्वारा 1965 के अभूतपूर्व पेपर के बाद से<ref>{{Cite journal | last1 = Hartmanis | first1 = J. | last2 = Stearns | first2 = R. E. | doi = 10.1090/S0002-9947-1965-0170805-7 | title = एल्गोरिदम की कम्प्यूटेशनल जटिलता पर| journal = Transactions of the American Mathematical Society | volume = 117 | pages = 285–306 | year = 1965 | doi-access = free }}</ref> और एनपी-पूर्णता पर [[माइकल गैरी]] और डेविड एस. जॉनसन की 1979 की बुक,<ref>[[Michael Garey]], and [[David S. Johnson]]: ''Computers and Intractability: A Guide to the Theory of NP-Completeness.'' New York: W. H. Freeman & Co., 1979.</ref> [[एल्गोरिदम का विश्लेषण]] (एल्गोरिदम का) शब्द को समान्यत: एसिम्प्टोटिक कम्प्यूटेशनल कोम्प्लेक्ससिटी | [[ज्यूरिस हार्टमैनिस]] और रिचर्ड ई. स्टर्न्स द्वारा 1965 के अभूतपूर्व पेपर के बाद से<ref>{{Cite journal | last1 = Hartmanis | first1 = J. | last2 = Stearns | first2 = R. E. | doi = 10.1090/S0002-9947-1965-0170805-7 | title = एल्गोरिदम की कम्प्यूटेशनल जटिलता पर| journal = Transactions of the American Mathematical Society | volume = 117 | pages = 285–306 | year = 1965 | doi-access = free }}</ref> और एनपी-पूर्णता पर [[माइकल गैरी]] और डेविड एस. जॉनसन की 1979 की बुक,<ref>[[Michael Garey]], and [[David S. Johnson]]: ''Computers and Intractability: A Guide to the Theory of NP-Completeness.'' New York: W. H. Freeman & Co., 1979.</ref> [[एल्गोरिदम का विश्लेषण]] (एल्गोरिदम का) शब्द को समान्यत: एसिम्प्टोटिक कम्प्यूटेशनल कोम्प्लेक्ससिटी के रूप में जाना जाता है। | ||
इसके अतिरिक्त, जब तक कि अन्यथा निर्दिष्ट न किया जाए, कम्प्यूटेशनल कोम्प्लेक्ससिटी | इसके अतिरिक्त, जब तक कि अन्यथा निर्दिष्ट न किया जाए, कम्प्यूटेशनल कोम्प्लेक्ससिटी शब्द समान्यत: एक एल्गोरिदम या समस्या की एसिम्प्टोटिक कम्प्यूटेशनल कोम्प्लेक्ससिटी के लिए [[ऊपरी सीमा|अप्पर बाउंड]] को संदर्भित करता है, जो समान्यत: बड़े ओ नोटेशन के संदर्भ में लिखा जाता है, उदाहरण के लिए। <math>O(n^3).</math> अन्य प्रकार के (एसिम्प्टोटिक) कम्प्यूटेशनल कोम्प्लेक्ससिटी अनुमान लोअर [[ऊपरी सीमा|बाउंड]] (बिग ओ नोटेशन नोटेशन; उदाहरण के लिए, Ω (''n'')) और एसिम्प्टोटिक रूप से तंग अनुमान हैं, जब एसिम्प्टोटिक [[ऊपरी सीमा|अप्पर]] और लोअर [[ऊपरी सीमा|बाउंड]] से मेल खाती है (बड़े थीटा का उपयोग करके लिखा जाता है; उदाहरण के लिए,Θ(''n'' log ''n'')). | ||
एक और [[मौन धारणा|टैसिट अस्सुम्प्सन]] | एक और [[मौन धारणा|टैसिट अस्सुम्प्सन]] यह है कि कम्प्यूटेशनल कोम्प्लेक्ससिटी का सबसे वर्स्ट केस एनालिसिस प्रश्न में है जब तक कि अन्यथा न कहा गया हो। एक अल्टरनेटिव अप्प्रौच [[एल्गोरिदम का संभाव्य विश्लेषण|एल्गोरिदम का प्रोबब्लिस्टिक एनालिसिस]] है। | ||
==एल्गोरिदम के प्रकार माने गए== | ==एल्गोरिदम के प्रकार माने गए== | ||
अधिकांश व्यावहारिक स्थितियों में दितेर्मिनिस्टिक एल्गोरिदम या [[यादृच्छिक एल्गोरिदम|रैंडेमायज्द एल्गोरिदम]] पर चर्चा की जाती है, चूँकि [[सैद्धांतिक कंप्यूटर विज्ञान|थेओरिटीकल कंप्यूटर विज्ञान]] नॉन-दितेर्मिनिस्टिक | अधिकांश व्यावहारिक स्थितियों में दितेर्मिनिस्टिक एल्गोरिदम या [[यादृच्छिक एल्गोरिदम|रैंडेमायज्द एल्गोरिदम]] पर चर्चा की जाती है, चूँकि [[सैद्धांतिक कंप्यूटर विज्ञान|थेओरिटीकल कंप्यूटर विज्ञान]] नॉन-दितेर्मिनिस्टिक एल्गोरिदम और गणना के अन्य उन्नत मॉडल पर भी विचार करता है। | ||
==यह भी देखें== | ==यह भी देखें== | ||
Revision as of 09:51, 21 July 2023
कम्प्यूटेशनल कोम्प्लेक्ससिटी थ्योरी में, एसिम्प्टोटिक कम्प्यूटेशनल कोम्प्लेक्ससिटी ऐल्गरिदम विधि और कम्प्यूटेशनल समस्याओं की कम्प्यूटेशनल कोम्प्लेक्ससिटी के आकलन के लिए एसिम्प्टोटिक विश्लेषण का उपयोग है, जो समान्यत: बिग ओ नोटेसन के उपयोग से जुड़ा होता है।
दायरा
कम्प्यूटेशनल रिसोर्स के संबंध में, एसिम्प्टोटिक टाइम कोम्प्लेक्ससिटी और एसिम्प्टोटिक स्पेस कोम्प्लेक्ससिटी का समान्यत: अनुमान लगाया जाता है। अन्य असिम्प्टोटीकली एसटीम्टेड से अनुमानित व्यवहार में सर्किट कोम्प्लेक्ससिटी और परेल्लेल कम्पूटैस्नल के विभिन्न उपाय सम्मिलित हैं, जैसे (परेल्लेल) प्रोसेसर की संख्या।
ज्यूरिस हार्टमैनिस और रिचर्ड ई. स्टर्न्स द्वारा 1965 के अभूतपूर्व पेपर के बाद से[1] और एनपी-पूर्णता पर माइकल गैरी और डेविड एस. जॉनसन की 1979 की बुक,[2] एल्गोरिदम का विश्लेषण (एल्गोरिदम का) शब्द को समान्यत: एसिम्प्टोटिक कम्प्यूटेशनल कोम्प्लेक्ससिटी के रूप में जाना जाता है।
इसके अतिरिक्त, जब तक कि अन्यथा निर्दिष्ट न किया जाए, कम्प्यूटेशनल कोम्प्लेक्ससिटी शब्द समान्यत: एक एल्गोरिदम या समस्या की एसिम्प्टोटिक कम्प्यूटेशनल कोम्प्लेक्ससिटी के लिए अप्पर बाउंड को संदर्भित करता है, जो समान्यत: बड़े ओ नोटेशन के संदर्भ में लिखा जाता है, उदाहरण के लिए। अन्य प्रकार के (एसिम्प्टोटिक) कम्प्यूटेशनल कोम्प्लेक्ससिटी अनुमान लोअर बाउंड (बिग ओ नोटेशन नोटेशन; उदाहरण के लिए, Ω (n)) और एसिम्प्टोटिक रूप से तंग अनुमान हैं, जब एसिम्प्टोटिक अप्पर और लोअर बाउंड से मेल खाती है (बड़े थीटा का उपयोग करके लिखा जाता है; उदाहरण के लिए,Θ(n log n)).
एक और टैसिट अस्सुम्प्सन यह है कि कम्प्यूटेशनल कोम्प्लेक्ससिटी का सबसे वर्स्ट केस एनालिसिस प्रश्न में है जब तक कि अन्यथा न कहा गया हो। एक अल्टरनेटिव अप्प्रौच एल्गोरिदम का प्रोबब्लिस्टिक एनालिसिस है।
एल्गोरिदम के प्रकार माने गए
अधिकांश व्यावहारिक स्थितियों में दितेर्मिनिस्टिक एल्गोरिदम या रैंडेमायज्द एल्गोरिदम पर चर्चा की जाती है, चूँकि थेओरिटीकल कंप्यूटर विज्ञान नॉन-दितेर्मिनिस्टिक एल्गोरिदम और गणना के अन्य उन्नत मॉडल पर भी विचार करता है।
यह भी देखें
- असिम्प्टोटीकली रूप से इष्टतम एल्गोरिदम
संदर्भ
- ↑ Hartmanis, J.; Stearns, R. E. (1965). "एल्गोरिदम की कम्प्यूटेशनल जटिलता पर". Transactions of the American Mathematical Society. 117: 285–306. doi:10.1090/S0002-9947-1965-0170805-7.
- ↑ Michael Garey, and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979.
