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

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

दायरा

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

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

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

एक और मौन धारणा यह है कि कम्प्यूटेशनल जटिलता का सबसे खराब मामला विश्लेषण प्रश्न में है जब तक कि अन्यथा न कहा गया हो। एक वैकल्पिक दृष्टिकोण एल्गोरिदम का संभाव्य विश्लेषण है।

एल्गोरिदम के प्रकार माने गए

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

यह भी देखें

• स्पर्शोन्मुख रूप से इष्टतम एल्गोरिदम