T(n) = 2T(n/2) + 0(1)
T(n) = T(sqrt(n)) + 0(1)
पहले में मैं n, logn, आदि के लिए प्रतिस्थापन विधि का उपयोग करता हूं; सभी ने मुझे गलत जवाब दिए।
पुनरावृत्ति पेड़: मुझे नहीं पता कि मैं आवेदन कर सकता हूं क्योंकि रूट स्थिर रहेगा।क्या कोई इस पुनरावृत्ति संबंध को हल करने में मदद कर सकता है?
क्या कोई मदद कर सकता है?
आइए पहले देखें। सबसे पहले, आपको टी (बेस केस) जानना होगा। आपने बताया कि यह स्थिर है, लेकिन जब आप समस्या करते हैं तो यह महत्वपूर्ण है कि आप इसे लिख दें। आम तौर पर यह टी (1) = 1 जैसा कुछ है। मैं इसका उपयोग करूंगा, लेकिन आप जो कुछ भी कर सकते हैं उसे सामान्यीकृत कर सकते हैं।
अगला, पता लगाएं कि आप कितनी बार पुनरावृत्ति करते हैं (यानी, रिकर्सन पेड़ की ऊंचाई)। n आपकी समस्या का आकार है, तो हम कितनी बार बार-बार 2 से विभाजित कर सकते हैं? गणितीय रूप से बोलते हुए, मैं क्या हूं n/(2^i) = 1? इसे चित्रित करें, बाद में इसके लिए पकड़ लें।
अगला, कुछ प्रतिस्थापन करें, जब तक कि आप एक पैटर्न को नोटिस करना शुरू न करें।
T(n) = 2(2(2T(n/2*2*2) + θ(1)) + θ(1)) + θ(1)
ठीक है, पैटर्न है कि हम समय की एक गुच्छा 2 से समय की एक गुच्छा, और विभाजित एन टी() गुणा 2 से है। कितनी बार? i बार।
T(n) = (2^i)*T(n/(2^i)) + ...
अंत में बड़े θ संदर्भ के लिए, हम एक सुंदर चाल का उपयोग करें। ऊपर देखें जहां हमारे पास कुछ प्रतिस्थापन हैं, और टी() भाग को अनदेखा करते हैं। हम θ शर्तों की राशि चाहते हैं। ध्यान दें कि वे (1 + 2 + 4 + ... + 2^i) * θ(1) तक जोड़ते हैं। क्या आप 1 + 2 + 4 + ... + 2^i के लिए एक बंद फॉर्म खोज सकते हैं?मैं तुम्हें वह दूंगा; यह (2^i - 1) है। बस याद रखने के लिए यह एक अच्छा है, लेकिन here's how you'd figure it out।
वैसे भी, सब में हम
T(n) = (2^i) * T(n/(2^i)) + (2^i - 1) * θ(1)
आप पहले i के लिए हल तो मिलता है, तो आप उस i = log_2(n) पता है। इसमें प्लग करें, कुछ बीजगणित करें, और आप
T(n) = n*T(1) + (n - 1)*θ(1) पर जाएं। T(1) = 1। तो T(n) = n + (n - 1)*θ(1)। जो लगातार एक बार है, साथ ही निरंतर, प्लस एन। हम निचले क्रम के नियम और स्थिरांक ड्रॉप करते हैं, इसलिए यह θ (n) है।
प्रसून सौरव मास्टर विधि का उपयोग करने के बारे में सही है, लेकिन यह महत्वपूर्ण है कि आप जानते हैं कि पुनरावृत्ति संबंध क्या कह रहा है। पूछने की चीजें हैं, मैं प्रत्येक चरण में कितना काम करता हूं, और n आकार के इनपुट के लिए चरणों की संख्या क्या है?
ऐसे पुनरावृत्ति संबंधों को हल करने के लिए Master Theorem का उपयोग करें।
एक एक पूर्णांक से अधिक या 1 के बराबर है और हो ख होना एक वास्तविक संख्या से अधिक 1. ग एक सकारात्मक वास्तविक संख्या और घ गैर नकारात्मक वास्तविक संख्या होने दो । प्रपत्र
तो ख की na सत्ता के लिए
टी (एन) की पुनरावृत्ति को देखते हुए = एक टी (एन/बी) + n ग .. अगर n> 1
टी (एन) = घ .. अगर एन = 1
,
- अगर लॉग ख एक < सी, टी (एन) = Θ (एन ग),
- अगर लॉग ख एक = ग, टी (एन) = Θ (एन ग लॉग एन),
- अगर लॉग ख ए> सी, टी (एन) = Θ (एन लॉग बी)।
1) T(n) = 2T(n/2) + 0(1)
इस मामले में
a = b = 2;
लॉग बी ए = 1; सी = 0 (चूंकि एन सी = 1 => सी = 0)
तो केस (3) लागू है।तो T(n) = Θ(n) :)
2) T(n) = T(sqrt(n)) + 0(1)
Let मीटर = लोग इन n;
=> टी (2 मीटर) = टी (2 एम/2) + 0(1)
अब नाम बदलने कश्मीर (एम) = टी (2 मीटर) => कश्मीर (एम) = के (एम/2) + 0(1)
केस लागू करें (2)।
क्या मैं मास्टर्स प्रमेय लागू कर सकता हूं भले ही एफ (एन) स्थिर है, जैसे इस मामले में 0 (1) दूसरी समस्या के बारे में क्या? – rda3mon
@ रिंगो: हाँ आप कर सकते हैं। संपादन देखें। –
भाग 2 गलत है। यदि '2^एम = टी', तो' 2^(एम/2) 'फिर से' sqrt (टी) 'है। या बल्कि, '2^एम = 2^लॉग एन = एन', इसलिए प्रतिस्थापन कुछ हासिल नहीं किया। – casablanca
की पहली पुनरावृत्ति पर नजर डालते हैं, टी (एन) = 2T (एन/2) + 1. n/2 हमारे सुराग यहाँ है: प्रत्येक नेस्टेड अवधि के पैरामीटर अपनी मूल का आधा है। इसलिए, यदि हम एन = 2^के साथ शुरू करते हैं तो हमारे पास हमारे विस्तार में के नियम होंगे, प्रत्येक हमारे कुल मामले, टी (0) को हिट करने से पहले कुल मिलाकर 1 जोड़ देगा। इसलिए, टी (0) = 1 मानते हुए, हम टी (2^के) = के + 1 कह सकते हैं। अब, चूंकि n = 2^k हमारे पास k = log_2 (n) होना चाहिए। इसलिए टी (एन) = लॉग_2 (एन) + 1.
हम आपके दूसरे पुनरावृत्ति, टी (एन) = टी (एन^0.5) + 1 पर एक ही चाल लागू कर सकते हैं। यदि हम n = 2^2^के हमारे पास हमारे विस्तार में के शब्द होंगे, प्रत्येक कुल में 1 जोड़ देगा। मान लें कि टी (0) = 1, हमारे पास टी (2^2^के) = के + 1 होना चाहिए। चूंकि एन = 2^2^के हमारे पास k = log_2 (log_2 (n)) होना चाहिए, इसलिए टी (एन) = log_2 (log_2 (n)) + 1.
भाग 1 के लिए, आप मास्टर प्रमेय का उपयोग @Prasoon सौरव के रूप में कर सकते हैं।
T(n) = T(n^1/2) + O(1) // sqrt(n) = n^1/2
= T(n^1/4) + O(1) + O(1) // sqrt(sqrt(n)) = n^1/4
etc.
श्रृंखला n^1/(2^k) <= 1, अर्थात 2^k = log n या k = log log n तक k शर्तों के लिए जारी रहेगा:
भाग 2 के लिए, बस पुनरावृत्ति का विस्तार करें। यह T(n) = k * O(1) = O(log log n) देता है।
2^k = log n lead to k = log log n कैसे किया? – Irwin
@ कैसाब्लांका, क्या आप कृपया समझा सकते हैं कि <= 1 कैसे आया? – TechCrunch
पुनरावृत्ति संबंध और पुनरावर्ती कार्यों को भी एफ (1) से शुरू करके हल किया जाना चाहिए। 1, टी (1) = 1 के मामले में; टी (2) = 3; टी (4) = 7; टी (8) = 15; यह स्पष्ट है कि टी (एन) = 2 * एन -1, जो ओ नोटेशन में ओ (एन) है।
दूसरे मामले में टी (1) = 1; टी (2) = 2; टी (4) = 3; टी (16) = 4; टी (256) = 5; टी (256 * 256) = 6; यह पता लगाने में थोड़ा समय लगेगा कि टी (एन) = लॉग (लॉग (एन)) + 1 जहां लॉग आधार 2 है। स्पष्ट रूप से यह ओ (लॉग (लॉग (एन)) संबंध है।
अधिकांश समय पुनरावृत्ति से निपटने के लिए सबसे अच्छा तरीका है मैं तुम्हें प्रतिस्थापन विधि का उपयोग कर हल करने के लिए मामूली संकेत दे देंगे लेकिन यहाँ पुनरावृत्ति पेड़ आकर्षित करने के लिए और ध्यान से संभाल आधार मामला है।
।
पुनरावृत्ति में पहली प्रतिस्थापन n = 2^k कोशिश पुनरावृत्ति में दूसरा प्रयास प्रतिस्थापन n = 2^2^k
मैं इस प्रश्न को ऑफ-विषय के रूप में बंद करने के लिए मतदान कर रहा हूं क्योंकि यह एक गणित प्रश्न है, प्रोग्रामिंग प्रश्न नहीं। – ProgramFOX