एल्गोरिदम की कंप्यूटिंग समय जटिलता पर संसाधन

Question

क्या कोई अच्छा संसाधन (पुस्तक, संदर्भ, वेब साइट, एप्लिकेशन ...) है जो बताता है कि एल्गोरिदम की समय जटिलता की गणना कैसे करें?

क्योंकि, मेरे दिमाग में चीजों को ठोस बनाना मुश्किल है। कभी-कभी यह पुनरावृत्ति के बारे में बात कर रहा है जिसमें एलजी एन की समय जटिलता है; और फिर एक और पाश के अनुसार यह n.lg एन बन जाता है; और कभी-कभी वे इसे व्यक्त करने के लिए बड़े ओमेगा नोटेशन का उपयोग करते हैं, कभी-कभी बड़े-ओ और आदि ...

ये चीजें मेरे लिए काफी सार हैं। इसलिए, मुझे एक ऐसे संसाधन की आवश्यकता है जिसमें अच्छी व्याख्या हो और मुझे यह देखने के लिए कई उदाहरण मिलें कि क्या हो रहा है।

उम्मीद है कि मैंने अपनी समस्या को स्पष्ट रूप से समझाया है। मुझे पूरा यकीन है कि जो लोग अभी एल्गोरिदम का अध्ययन करना शुरू कर चुके हैं, उनके साथ भी यही समस्या है। तो, शायद वे अनुभवी लोग भी हमारे साथ अपना अनुभव साझा कर सकते हैं। धन्यवाद ...

Answer 1

इस विषय पर पुस्तकों का क्लासिक सेट Knuth की Art of Computer Programming श्रृंखला है। वे सिद्धांत और औपचारिक सबूत पर भारी हैं, इसलिए उनसे निपटने से पहले अपने कैलकुस पर ब्रश करें।

Answer 2

मुझे लगता है कि सबसे अच्छी किताब Introduction to Algorithms कॉर्मन, लीज़रसन, रिवेस्ट और स्टीन द्वारा है।

यहां यह on Amazon है।

Answer 3

मैं विश्वविद्यालय में क्रिस्टोस पापादिमित्रिउ के कम्प्यूटेशनल जटिलता पढ़ सकते हैं और वास्तव में इसे का आनंद लिया। यह एक आसान कार्य नहीं है, पुस्तक में लंबे समय है, लेकिन यह अच्छी तरह से लिखा है (यानी, समझ में आता है और स्वयं शिक्षण के लिए उपयुक्त) और यह उपयोगी ज्ञान के बहुत सारे, बस की तुलना में अधिक "कैसे मैं बाहर की एल्गोरिथ्म एक्स समय जटिलता आंकड़ा है" शामिल हैं ।

Answer 4

Computational complexity theory विकिपीडिया में आलेख में पुस्तक ड्राफ्ट Computational Complexity: A Modern Approach, संजीव अरोड़ा और बम बराक, कैम्ब्रिज यूनिवर्सिटी प्रेस की एक पाठ्यपुस्तक के लिंक सहित संदर्भों की एक सूची है।

Answer 5

दोस्तों, आप कर रहे हैं सभी की सिफारिश सच जटिलता सिद्धांत किताबें - चीजें हैं जो सबसे प्रोग्रामर/सॉफ्टवेयर डेवलपर्स कभी नहीं सुना - अरोड़ा और बराक पीसीपी, इंटरएक्टिव सबूत, क्वांटम कम्प्यूटिंग और Expander रेखांकन पर विषयों जैसी चीजों के सभी प्रकार के होते हैं या कभी भी उपयोग करेंगे। Papdimitriou एक ही श्रेणी में है। Knuth पढ़ने के लिए असंभव है (और मैं एक सीएस/गणित प्रमुख था) और चीजों को कैसे काम करता है पर शून्य अंतर्ज्ञान देता है।

यदि आप रनटाइम की गणना करने के लिए एक आसान तरीका चाहते हैं, और विश्लेषण का स्वाद प्राप्त करने के लिए, क्लेनबर्ग और टैर्डोस के पहले अध्याय या तो "एल्गोरिदम के डिजाइन और विश्लेषण" का प्रयास करें, जो मूलभूत सिद्धांतों के माध्यम से आपका हाथ रखता है, और तो आप बहुत कठिन समस्याओं पर काम कर सकते हैं।

Answer 6

Discrete Mathematics में एक कोर्स कभी-कभी Introduction to Algorithms से पहले दिया जाता है।

Answer 7

मैं मानता हूं कि Introduction to Algorithms एक अच्छी किताब है। उदाहरण के लिए अधिक विस्तृत निर्देशों के लिए पुनरावृत्ति संबंधों को कैसे हल करें Knuth's Concrete Mathematics देखें। कम्प्यूटेशनल कॉम्प्लेक्सिटी पर एक अच्छी किताब खुद ही Papadimitriou है। लेकिन अगर आप केवल एल्गोरिदम की जटिलता की गणना करना चाहते हैं तो वह अंतिम पुस्तक थोड़ा सा हो सकती है।

बड़े ओ/-Omega अंकन के बारे में एक संक्षिप्त अवलोकन: (एन सी * (एन लॉग इन करें))

• आप एक एल्गोरिथ्म है कि समय टी में एक समस्या का हल दे सकते हैं (ग एक स्थिर होने के नाते), उस समस्या की जटिलता की तुलना में ओ (एन लॉग एन) है। बड़े-ओ ग से छुटकारा मिलता है, कि इनपुट आकार n के आधार पर नहीं किसी भी निरंतर कारकों है। बिग-ओ चलने वाले समय पर ऊपरी बाउंड देता है, क्योंकि आपने दिखाया है (एक एल्गोरिदम देकर) कि आप उस समय में समस्या का समाधान कर सकते हैं।
• आप एक सबूत है कि किसी भी एल्गोरिथ्म समस्या को हल करने में कम से कम समय टी लेता दे सकते हैं (ग * (एन एन लॉग इन करें)) समस्या से (एन लॉग इन करें n)ओमेगा में है। बिग-ओमेगा समस्या पर निचला बाउंड देता है। ज्यादातर मामलों में निचली सीमाएं ऊपरी सीमाओं से सबूत के लिए बहुत कठिन होती हैं, क्योंकि आपको यह दिखाना होगा कि समस्या के लिए कोई भी संभावित एल्गोरिदम कम से कम टी (सी * (एन लॉग एन) लेता है। निचले बाउंड को जानने से मतलब नहीं है एक एल्गोरिथ्म है कि लोअर बाउंड तक पहुँच जाता है जानते हुए भी।
• आप एक कम बाध्य है, तो जैसे ओमेगा (एन लॉग इन करें n), और एक एल्गोरिथ्म है कि उस समय (एक ऊपरी बाध्य) में समस्या हल समस्या से थीटा (एन लॉग इन करें n) में है। इस समस्या के लिए एक "इष्टतम" एल्गोरिथ्म जाना जाता है। बेशक इस अंकन निरंतर कारक ग जो काफी बड़ा हो सकता है (था छुपाता है इसका मतलब यह है टी क्यों मैंने उद्धरणों में इष्टतम लिखा है)।

ध्यान दें कि इन नोटेशन का उपयोग करते समय आप आमतौर पर एल्गोरिदम के सबसे खराब मामले चलने वाले समय के बारे में बात कर रहे हैं।