मेरा प्रश्न "Plain English Explanation of Big O" पोस्ट से उत्पन्न होता है। मुझे लॉगरिदमिक जटिलता के लिए सही अर्थ नहीं पता है। मुझे पता है कि मैं समय और संचालन की संख्या के बीच एक रिग्रेशन कर सकता हूं और एक्स-स्क्वायर वैल्यू की गणना कर सकता हूं, और जटिलता निर्धारित कर सकता हूं। हालांकि, मैं कागज पर इसे जल्दी से निर्धारित करने के लिए एक विधि जानना चाहता हूं।बिग ओ लॉगरिदमिक कब पता चलेगा?
आप लॉगरिदमिक जटिलता को कैसे निर्धारित करते हैं? क्या कुछ अच्छे मानक हैं?
सुनिश्चित नहीं है कि यह आपका क्या मतलब है, लेकिन ... जब आप एक संतुलित बाइनरी पेड़ की तरह फैलाने वाली डेटा संरचना के साथ काम कर रहे हैं तो लॉगरिदमिक जटिलता उत्पन्न होती है, जिसमें रूट पर 1 नोड, 2 बच्चे, 4 पोते, 8 महान पोते, आदि। मूल रूप से प्रत्येक स्तर पर नोड्स की संख्या कुछ कारक (2) से गुणा हो जाती है लेकिन फिर भी उनमें से केवल एक ही पुनरावृत्ति में शामिल है। या फिर एक और उदाहरण के रूप में, एक पाश जिसमें सूचकांक प्रत्येक चरण में दोगुना हो जाता है:
for (int i = 1; i < N; i *= 2) { ... }
हालात ऐसे ही लघुगणक जटिलता के हस्ताक्षर हैं।
Master theorem आमतौर पर काम करता है।
कुछ हद तक सोचना मुश्किल है, लेकिन एक बार जब आप इसे मास्टर करते हैं तो बहुत अच्छा होता है। – samoz
कठोर नहीं है, लेकिन आपके पास एक एल्गोरिदम है जो अनिवार्य रूप से प्रत्येक पुनरावृत्ति पर आधे से किए जाने वाले कार्यों को विभाजित कर रहा है, तो आपके पास लॉगरिदमिक जटिलता है। क्लासिक उदाहरण बाइनरी खोज है।
जरूरी नहीं है। मैं समझता हूं कि आप क्या करने की कोशिश कर रहे हैं, लेकिन सिर्फ इसलिए कि आप काम को आधा में विभाजित करते हैं, इसका मतलब यह नहीं है कि आपको लॉगरिदमिक जटिलता मिलती है, आप उस मामले के लिए घातीय समय भी प्राप्त कर सकते हैं। आपको यह ध्यान रखना होगा कि समाधान कैसे पुन: संयोजित किए जा रहे हैं और विभाजित समस्याओं को कैसे हल किया जाए। ऐसे कई मामले हैं जहां पुनर्संरचना चरण पर हावी है। मास्टर प्रमेय देखें या प्रमेय के बिना पुनरावृत्ति को बेहतर ढंग से हल करें। एक सरल पुनरावृत्ति के नीचे बहुत सारी आश्चर्य है। – unj2
@unjaan: मुझे लगता है कि आप मुझे गलत समझ रहे हैं। मैंने सिर्फ काम को आधे में विभाजित नहीं किया, मैंने कहा "काम प्रत्येक पुनरावृत्ति पर आधे से किया जाना चाहिए"। मेरा मतलब यह है कि, यदि प्रत्येक चरण में पिछले चरण की तुलना में आधा काम किया जाना बाकी है, तो आपके पास लॉगरिदमिक जटिलता है (काम के लिए, कम्प्यूटेशन पढ़ें)। –
यदि आप सिर्फ लॉगरिदमिक बिग ओह के बारे में जानना चाहते हैं, तो पुनरावृत्ति के प्रत्येक चरण में आपका डेटा कब कट किया जाए, इस पर ध्यान दें।
ऐसा इसलिए है क्योंकि यदि आप डेटा को संसाधित कर रहे हैं जो 1/2 जितना बड़ा है, तो यह एक अनंत श्रृंखला है।
जरूरी नहीं 1/2।1/सी काम करता है, जब तक 'सी' स्थिर है। –
लेकिन 1/2 अधिक 'अंतर्ज्ञानी' –
आमतौर पर बिग ओ के बारे में बात करते समय, लॉग का मतलब लॉग बेस 2. – samoz
यह कहने का एक और तरीका है।
मान लीजिए कि आपका एल्गोरिदम समस्या के आकार में अंकों की संख्या में रैखिक है। तो, शायद आपके पास एक बड़ी संख्या के कारक के लिए एक नया एल्गोरिदम है, जो आप अंकों की संख्या में रैखिक होने के लिए दिखा सकते हैं। आपके एल्गोरिदम का उपयोग करके 10 अंकों की संख्या के रूप में एक 20 अंकों की संख्या कारक के लिए दो गुना अधिक समय लेती है। इसमें लॉग जटिलता होगी। (और यह आविष्कारक के लिए कुछ लायक होगा।)
बिसेक्शन का एक ही व्यवहार है। इसमें 1024 = 2^10 के कारक द्वारा अंतराल की लंबाई को कम करने के लिए लगभग 10 बिसेक्शन कदम होते हैं, लेकिन केवल 20 कदम 2^20 के कारक द्वारा अंतराल को काट देंगे।
लॉग जटिलता हमेशा यह नहीं मानती है कि सभी समस्याओं पर एल्गोरिदम तेजी से होता है। ओ (लॉग (एन)) के सामने रैखिक कारक बड़ा हो सकता है। तो आपकी एल्गोरिदम छोटी समस्याओं पर भयानक हो सकती है, जब तक समस्या का आकार काफी बड़ा नहीं होता है तब तक उपयोगी नहीं होता है कि अन्य एल्गोरिदम एक घातीय (या बहुपद) मौत मर जाते हैं।
अच्छी समस्या के साथ अच्छी तरह से समझाया गया। –
+1 बहुत दिलचस्प है। मैं आपके उदाहरणों की तरह कुछ ढूंढ रहा हूं। क्या एल्गोरिदम logartihmic है: के लिए (int i = BIG_number; i> N; i * = 1/2) {...} –
1/2 पूर्णांक विभाजन में शून्य है, लेकिन यदि आप इसके बजाय "i/= 2" का उपयोग करते हैं , हाँ यही है। (यदि वह विशेष एल्गोरिदम है जिसके बारे में आप सोच रहे हैं, तो यह आपके प्रश्न में शामिल करना एक अच्छा विचार हो सकता है।) –