क्यों अध्ययन जटिलता सिद्धांत?
मैं एल्गोरिदम के अध्ययन में एक शौकिया हूँ। थोड़ी देर के लिए मेरे पास एक ज्वलंत प्रश्न है, हम कंप्यूटर विज्ञान में जटिलता सिद्धांत का अध्ययन क्यों करते हैं? मेरे द्वारा पूछे जाने का कारण यह है क्योंकि बेहतर स्पर्शोन्मुख जटिलता वाले एल्गोरिदम व्यावहारिक उद्देश्यों के लिए हमेशा तेज नहीं होते हैं, वास्तव में वे बेतुके धीमे हो सकते हैं। इसके बजाय एक ऐसा सिद्धांत क्यों नहीं विकसित किया गया जो वैज्ञानिक अनुसंधान और उद्योग की व्यावहारिक जरूरतों के लिए बेहतर हो?
एक उदाहरण के रूप में, यह ज्ञात है कि एक परिपूर्ण शतरंज खेल का निर्धारण करने के लिए एक एल्गोरिथ्म का विकास किया जा सकता है $O(1)$, क्योंकि 8 × 8 ग्रिड पर कानूनी शतरंज के खेल की संख्या ऊपर से बंधी हुई है। हालाँकि, मैंने सुना है कि यह एल्गोरिथ्म ब्रह्मांड की उम्र से अधिक समय लगेगा। यह सवाल है, क्यों जटिलता सिद्धांत? ऐसा लगता है कि यह क्षेत्र मौलिक रूप से दोषपूर्ण है, और कंप्यूटर वैज्ञानिकों को एल्गोरिदम के अध्ययन के लिए एक बेहतर दृष्टिकोण का उपयोग करना चाहिए।
(नोट: क्षेत्र में शोधकर्ताओं के लिए मेरी ईमानदार क्षमायाचना। inc)
जवाब
यह एक सरल प्रश्न नहीं है, और आपको एक सरल उत्तर की उम्मीद नहीं करनी चाहिए। इस अंतरिक्ष में समान प्रश्नों की एक श्रृंखला है: हम असममित रनिंग टाइम का अध्ययन क्यों करते हैं? हम एल्गोरिदम का विश्लेषण करने के लिए असममित रनिंग टाइम विश्लेषण का उपयोग क्यों करते हैं? हम जटिलता सिद्धांत का अध्ययन क्यों करते हैं? उनमें से प्रत्येक के कई उत्तर हैं; केवल एक ही कारण नहीं है कि हम ऐसा क्यों करते हैं, और विभिन्न लोगों के अलग-अलग कारण हो सकते हैं।
असममित रनिंग टाइम विश्लेषण के फायदे और नुकसान हैं। आपने एक नुकसान की सही पहचान की है: एक अच्छा स्पर्शोन्मुख चलने का समय अभ्यास में अच्छे चलने के समय की गारंटी नहीं देता है। लेकिन अगर आप केवल एक लाभ या नुकसान पर ध्यान केंद्रित करते हैं तो आप विश्लेषण की उस शैली की ताकत और कमजोरियों की पूरी तस्वीर नहीं लेंगे। कुछ फायदे यह हैं कि विश्लेषण अपेक्षाकृत सुपाच्य है, यह किसी विशेष वास्तुकला के लिए विशिष्ट नहीं है, यह स्केलेबिलिटी के बारे में उपयोगी जानकारी प्रदान करता है, और कम से कम कुछ समय में एल्गोरिदमिक अड़चनों की पहचान करने में उपयोगी भविष्य कहनेवाला शक्ति है। उदाहरण के लिए, एक के बीच का अंतर$O(n^2)$ समय एल्गोरिथ्म और ए $O(n \log n)$समय एल्गोरिथ्म अक्सर महत्वपूर्ण हो सकता है, भले ही हम निरंतर कारकों की अनदेखी कर रहे हों। कुछ नुकसान यह है कि निरंतर कारक महत्वपूर्ण हो सकते हैं, कैश और मेमोरी पदानुक्रम प्रभाव बहुत महत्वपूर्ण हो सकते हैं फिर भी एसिम्प्टोटिक रनिंग टाइम विश्लेषण द्वारा नजरअंदाज किया जाता है, और (किसी भी मीट्रिक की तरह) एसिमेपोटिक रनिंग टाइम के लिए पूरी तरह से अनुकूलन करने से थोड़ा व्यावहारिक के बेतुके परिणाम हो सकते हैं। उपयोगिता ( गैलेक्टिक एल्गोरिदम और गुडहार्ट का नियम देखें )।
मुझे लगता है कि विकल्प की जांच करना भी उपयोगी है। मैं आपको असममित रूप से चल रहे समय विश्लेषण के विकल्प का पता लगाने के लिए प्रोत्साहित करता हूं और इसके माध्यम से जो आप प्रस्तावित करेंगे, उसके माध्यम से काम करना होगा। यदि आप एक ठोस प्रस्ताव के साथ आने की कोशिश नहीं करते हैं, तो यह मान लेना आसान है कि यह कुछ बेहतर खोजने के लिए कठिन नहीं हो सकता ... लेकिन जब आप कुछ विशिष्ट करने के लिए मजबूर होते हैं, तो आपको पता चल सकता है कि यह है आप की अपेक्षा अधिक चुनौतीपूर्ण है। उदाहरण के लिए, मैं आपको अपने TAOCP श्रृंखला में MIX पर चल रहे एल्गोरिथ्म के विश्लेषण के साथ परिचित होने के लिए प्रोत्साहित करता हूं । वहां वह ठोस रनिंग टाइम एनालिसिस करता है, जिसमें बिना एसिमप्टिक्स के लगातार कारकों को ध्यान में रखा जाता है। यदि आप अपने आप को उस के विवरण के माध्यम से काम करने के लिए मजबूर करते हैं, तो आप जल्दी से उस के नुकसान का पता लगा लेंगे: यह सुपर-थकाऊ है, जो एक विशेष कंप्यूटर आर्किटेक्चर के लिए बहुत विशिष्ट है, और अक्सर बहुत अधिक ज्ञानवर्धक नहीं है।
हम इसी तरह से प्रत्येक अन्य विषयों पर चर्चा कर सकते हैं - जैसे, क्यों या क्यों जटिलता सिद्धांत का अध्ययन नहीं करना चाहिए - और आप पाएंगे कि उनकी भी बारीकियां हैं।
मैं आपके लिए यह भी उजागर करना चाहता हूं कि सिद्धांत और एल्गोरिदम समुदाय एक व्यापक है, जिसमें विभिन्न शैलियों की एक श्रृंखला है। आपको लगता है कि यह सब एक ही ढेर में एक साथ हो रहा है, लेकिन इसमें काम का एक स्पेक्ट्रम है: इसमें से कुछ सुपर-सैद्धांतिक और अभ्यास से दूर हैं, इनमें से कुछ अत्यधिक व्यावहारिक हैं और ठोस समस्याओं से प्रेरित हैं और इसका तत्काल प्रभाव हो सकता है, और उन चरम सीमाओं के बीच विभिन्न बिंदुओं पर काम की एक सीमा होती है। मुझे लगता है कि यह समझना महत्वपूर्ण है कि सिद्धांत समुदाय में कुछ काम है जो महान व्यावहारिक प्रासंगिकता का है या इसका बड़ा प्रभाव पड़ा है, जैसे कि ऐसा काम है जो बहुत अधिक सैद्धांतिक है और निकटवर्ती प्रभाव से प्रेरित नहीं है।
चूंकि आपने सैद्धांतिक ढांचे के लिए कहा है जो उद्योग की जरूरतों को पूरा करने पर केंद्रित हैं, इसलिए आप वर्ड रैम मॉडल, कैश-गुमनामी एल्गोरिदम और समानांतर बाहरी मेमोरी मॉडल में भी रुचि रख सकते हैं ।
मैं आपको निम्नलिखित संसाधनों को पढ़ने के लिए दृढ़ता से प्रोत्साहित करता हूं, क्योंकि वे आपके प्रश्न से निकटता से संबंधित हैं: क्यों बहुपद समय को "कुशल" कहा जाता है? , एल्गोरिदम को डिजाइन करने के एल्गोरिदम के अभ्यास के लिए असममित जटिलता की प्रासंगिकता की व्याख्या करना , बिग ओ में लगातार कारकों की उपेक्षा करने का औचित्य ।