क्या संबंध T (n) = nT (n-1) + n के समय जटिलता होगी मेरे कुछ इस तरह से
f(int n)
{
c++;
if(n>0)
for(i=1;i<=n;i++)
f(n-1);
}
मैंने यह गिनने के लिए एक काउंटर लिया कि कितने समय के समारोह को बुलाया गया यह n से n के बीच उत्तर देता है! धन्यवाद।
उत्तर:
उत्तर № 1 के लिए -1हम कुछ शब्दों को सूचीबद्ध कर सकते हैं
T(0) = 0
T(1) = 1 * 0 + 1
T(2) = 2 * 1 + 2 = 4
T(3) = 3 * 4 + 3 = 15
T(4) = 4 * 15 + 4 = 64
...
हम कुछ बातें नोट कर सकते हैं। सबसे पहले, फ़ंक्शन n की तुलना में अधिक तेज़ी से बढ़ता है !; यह इससे छोटा होता है (n = 0 पर), पकड़ता है (n = 1 पर) और इसे पार करता है (n> 2) पर। तो हम जानते हैं कि एक निचली सीमा n है!।
अब, हमें ऊपरी सीमा की आवश्यकता है। हम एक बात नोटिस कर सकते हैं: सभी पर्याप्त रूप से बड़े n (n> = 2, मुझे लगता है) के लिए T (n) = nT (n-1) + n <nT (n-1) + nT (n-1)। लेकिन हम आसानी से दिखा सकते हैं कि टी (एन) = एनटी (एन -1) एन के लिए एक पुनरावृत्ति संबंध है!, इसलिए हम जानते हैं कि टी (एन) = एनटी (एन -1) + एनटी (एन -1) के लिए एक पुनरावृत्ति संबंध ) = 2 एनटी (एन -1) है (एन!) (2 ^ एन)। क्या हम बेहतर कर सकते हैं?
मैं प्रस्ताव करता हूं कि हम कर सकते हैं। हम दिखा सकते हैं कि किसी भी c> 0, T (n) = nT (n-1) + n <nT (n-1) + cnT (n-1) के लिए n के पर्याप्त बड़े मान हैं। हम पहले से ही जानते हैं कि T (n-1) नीचे से घिरा हुआ है (n-1) !; इसलिए, यदि हम c = n / (n-1) लेते हैं! हम अपनी अभिव्यक्ति को ठीक करते हैं और हम जानते हैं कि एक ऊपरी सीमा है (c ^ n) (n!)। N के रूप में c की सीमा अनंत तक जाती है? 0. [n / (n-1)!] ^ N द्वारा ग्रहण किया गया अधिकतम मान क्या है?
सौभाग्य कि कंप्यूटिंग। वोल्फ्राम अल्फा यह काफी स्पष्ट करता है कि इस फ़ंक्शन द्वारा मान लिया गया अधिकतम मूल्य n ~ 2.5 के लिए लगभग 5 या 6 है। यह मानते हुए कि आप इस बात से आश्वस्त हैं, कि टेकअवे क्या है?
n! <टी (n) <~ 6n! सभी के लिए एन। n! आपके पुनरावृत्ति के लिए थीटा-बाउंड है।
उत्तर № 2 के लिए 1
आपके कोड में कमी है +n रिकर्सन का हिस्सा है, इसलिए मैं मानता हूं कि कोड गलत है और रिकर्सन
T(n) = n*T(n-1) + n
सही है।
चलो f(n)=T(n)/n!, फिर
f(n) = T(n)/n! = n(T(n-1)+1)/n!
= T(n-1)/(n-1)! + 1/(n-1)!
= f(n-1) + 1/(n-1)!
= sum(1,n-1, 1/k!)
~ e
इस प्रकार T(n) ~ e*n!.
उत्तर № 3 के लिए -1
फंक्शन को कहा जाता है
n*f(n-1)
बार। की जगह f(n-1) इस परिभाषा के साथ देता है
n*((n-1)*f(n-2)
फिर से जगह देता है:
n*((n-1)*((n-2)*f(n-3)))
कोष्ठक निकालना:
n*(n-1)*(n-2)*...(1)
यह देता है:
n= 3: 3*2*1 = 6
n= 4: 4*3*2*1 = 24
n= 5: 5*4*3*2*1 = 120
जो है n!.