स्पर्शोन्मुख कम्प्यूटेशनल जटिलता

कम्प्यूटेशनल कोम्प्लेक्ससिटी थ्योरी में, एसिम्प्टोटिक कम्प्यूटेशनल कोम्प्लेक्ससिटी ऐल्गरिदम और कम्प्यूटेशनल समस्याओं की कम्प्यूटेशनल कोम्प्लेक्ससिटी के आकलन के लिए एसिम्प्टोटिक विश्लेषण का उपयोग है, जो समान्यत: बिग ओ नोटेसन के उपयोग से जुड़ा होता है।

विस्तार

कम्प्यूटेशनल रिसोर्स के संबंध में, एसिम्प्टोटिक टाइम कोम्प्लेक्ससिटी और एसिम्प्टोटिक स्पेस कोम्प्लेक्ससिटी का समान्यत: अनुमान लगाया जाता है। अन्य असिम्प्टोटीकली एसटीम्टेड से अनुमानित व्यवहार में सर्किट कोम्प्लेक्ससिटी और परेल्लेल कम्पूटैस्नल के विभिन्न उपाय सम्मिलित हैं, जैसे (परेल्लेल) प्रोसेसर की संख्या।

ज्यूरिस हार्टमैनिस और रिचर्ड ई. स्टर्न्स द्वारा 1965 के अभूतपूर्व पेपर के बाद से और एनपी-पूर्णता पर माइकल गैरी और डेविड एस. जॉनसन की 1979 की बुक, एल्गोरिदम का विश्लेषण (एल्गोरिदम का) शब्द को समान्यत: एसिम्प्टोटिक कम्प्यूटेशनल कोम्प्लेक्ससिटी के रूप में जाना जाता है।

इसके अतिरिक्त, जब तक कि अन्यथा निर्दिष्ट न किया जाए, कम्प्यूटेशनल कोम्प्लेक्ससिटी शब्द समान्यत: एक एल्गोरिदम या समस्या की एसिम्प्टोटिक कम्प्यूटेशनल कोम्प्लेक्ससिटी के लिए अप्पर बाउंड को संदर्भित करता है, जो समान्यत: बड़े ओ नोटेशन के संदर्भ में लिखा जाता है, उदाहरण के लिए। $O(n^{3}).$ अन्य प्रकार के (एसिम्प्टोटिक) कम्प्यूटेशनल कोम्प्लेक्ससिटी अनुमान लोअर बाउंड (बिग ओ नोटेशन नोटेशन; उदाहरण के लिए, Ω (n)) और एसिम्प्टोटिक रूप से तंग अनुमान हैं, जब एसिम्प्टोटिक अप्पर और लोअर बाउंड से मेल खाती है (बड़े थीटा का उपयोग करके लिखा जाता है; उदाहरण के लिए,Θ(n log n)).

एक और टैसिट अस्सुम्प्सन यह है कि कम्प्यूटेशनल कोम्प्लेक्ससिटी का सबसे वर्स्ट केस एनालिसिस प्रश्न में है जब तक कि अन्यथा न कहा गया हो। एक अल्टरनेटिव अप्प्रौच एल्गोरिदम का प्रोबब्लिस्टिक एनालिसिस है।

एल्गोरिदम के प्रकारों पर विचार

अधिकांश व्यावहारिक स्थितियों में दितेर्मिनिस्टिक एल्गोरिदम या रैंडेमायज्द एल्गोरिदम पर विचार किया जाता है, चूँकि थेओरिटीकल कंप्यूटर विज्ञान नॉन-दितेर्मिनिस्टिक एल्गोरिदम और गणना के अन्य उन्नत मॉडल पर भी विचार करता है।

यह भी देखें

• असिम्प्टोटीकली ओप्टीमल एल्गोरिदम