मैं निम्नलिखित बाहर काम किया है:हल करने के लिए कैसे: टी (एन) = टी (n - 1) + n
T(n) = T(n - 1) + n = O(n^2)
अब जब मैं इस बाहर काम मुझे लगता है कि बाध्य बहुत ढीला है। क्या मैंने कुछ गलत किया है या क्या यह वही तरीका है?
इस बारे में सोचें:
रिकर्सन के प्रत्येक "पुनरावृत्ति" में आप ओ (एन) काम करते हैं।
प्रत्येक पुनरावृत्ति में n = 1 कार्य करने के लिए एन-1 कार्य होता है। (मुझे लगता है कि आधार मामला ओ (एन) काम है)
इसलिए, मानते हुए कि बेस केस निरंतर स्वतंत्र है, तो रिकर्सन के ओ (एन) पुनरावृत्तियों हैं।
यदि आपके पास ओ (एन) प्रत्येक के एन पुनरावृत्तियों हैं, तो ओ (एन) * ओ (एन) = ओ (एन^2)।
आपका विश्लेषण सही है। यदि आप रिकर्सन को हल करने के इस तरीके पर अधिक जानकारी चाहते हैं, तो रिकर्सन पेड़ देखें। वे अन्य तरीकों की तुलना में बहुत सहज हैं।
आपको अपने पुनरावृत्ति संबंध के लिए आधारभूत स्थिति की भी आवश्यकता है।
T(1) = c
T(n) = T(n-1) + n
इसे हल करने के लिए, आप पहले समाधान का अनुमान लगा सकते हैं और फिर साबित कर सकते हैं कि यह प्रेरण का उपयोग करके काम करता है।
T(n) = (n + 1) * n/2 + c - 1
पहले बेस केस। जब n = 1 यह आवश्यकतानुसार सी देता है।
अन्य n के लिए:
T(n)
= (n + 1) * n/2 + c - 1
= ((n - 1) + 2) * n/2 + c - 1
= ((n - 1) * n/2) + (2 * n/2) + c - 1
= (n * (n - 1)/2) + c - 1) + (2 * n/2)
= T(n - 1) + n
तो समाधान काम करता है।
पहली जगह में अनुमान पाने के लिए, देखते हैं कि आपकी पुनरावृत्ति संबंध उत्पन्न triangular numbers जब ग = 1:
T(1) = 1:
*
T(2) = 3:
*
**
T(3) = 6:
*
**
***
T(4) = 10:
*
**
***
****
etc..
Intuitively एक त्रिकोण है मोटे तौर पर एक वर्ग के आधे, और बिग-ओ अंकन में स्थिरांक को अनदेखा किया जा सकता है इसलिए ओ (एन^2) अपेक्षित परिणाम है।
क्या आप मुझे बता सकते हैं कि आपके उत्तर में आपके पास तीसरे समीकरण को कैसे मिला है? आप किस गणितीय तकनीक पर लागू होते थे? –
@ टोनी: यह एक "अनुमान" है। हकीकत में ऐसा इसलिए है क्योंकि मैं त्रिभुज संख्याओं के सूत्र को जानता हूं - मुझे वास्तव में इसका अनुमान नहीं था, मुझे पहले से ही यह पता था। सही जवाब "अनुमान" करना अक्सर आसान होता है और साबित करता है कि यह इसे पहले सिद्धांतों से प्राप्त करने के बजाय सही है। पुनरावृत्ति संबंधों को हल करने के लिए यह एक मानक तकनीक है। –
@ टोनी: एक शिक्षित अनुमान के लिए तकनीकी शब्द "ansatz" है। देखें: http://en.wikipedia.org/wiki/Ansatz। Http://en.wikipedia.org/wiki/Recurrence_relation में पुनरावृत्ति संबंध को हल करने के अनुमान के उपयोग के बारे में कुछ जानकारी है।पुनरावृत्ति संबंधों को हल करने के अन्य संभावित तरीकों को भी सूचीबद्ध किया गया है। –
सही के बारे में लगता है, लेकिन आधार मामले टी (1) पर निर्भर करेगा। मान लीजिए कि आप टी (एन) से टी (0) प्राप्त करने के लिए एन कदम उठाएंगे और प्रत्येक बार एन टर्म औसत एन/2 के औसत के लिए 0 और n के बीच कहीं भी होगा, इसलिए n * n/2 = (n^2)/2 = ओ (एन^2)।
समाधान इस के लिए बहुत आसान है। आप प्रत्यावर्तन उतारना करने के लिए है:
T(n) = T(n-1) + n = T(n-2) + (n - 1) + n =
= T(n-3) + (n-2) + (n-1) + n = ... =
= T(0) + 1 + 2 + ... + (n-1) + n
आप अंकगणितीय प्रगति यहाँ है और योग 1/2*n*(n-1) है। तकनीकी रूप से आप यहां सीमा की स्थिति खो रहे हैं, लेकिन किसी निरंतर सीमा स्थिति के साथ आप देखते हैं कि रिकर्सन O(n^2) है।
मैं इसके बारे में सोचने के गणित में बहुत अधिक था, और इस तथ्य को भूल गया कि हम एक रिकर्सन से निपट रहे हैं। शायद यही कारण है कि मैं इसे काफी नहीं मिला। उपर्युक्त के लिए मुझे टी (एन) <= 2 एन मिला जो सही होगा? –
आप जो पूछ रहे हैं उसे काफी समझ में नहीं आया, – Rubys
@ टोनी से बहुत ऊपर: नहीं, यह सही नहीं है। टी (एन) छोटे एन के लिए 2 एन से अधिक हो सकता है। –