मैं एक पुनरावर्ती एल्गोरिदम की समय जटिलता की गणना कैसे कर सकता हूं?एक पुनरावर्ती एल्गोरिदम की समय जटिलता
int pow1(int x,int n) {
if(n==0){
return 1;
}
else{
return x * pow1(x, n-1);
}
}
int pow2(int x,int n) {
if(n==0){
return 1;
}
else if(n&1){
int p = pow2(x, (n-1)/2)
return x * p * p;
}
else {
int p = pow2(x, n/2)
return p * p;
}
}
। ए (मेरी राय में) अच्छा परिचय डॉन Knuths में पाया जा सकता Concrete Mathematics।
हालांकि, अब इन उदाहरणों का विश्लेषण करें:
हम एक फ़ंक्शन को परिभाषित करते हैं जो हमें फ़ंक्शन द्वारा आवश्यक समय देता है। मान लें कि t(n)pow(x,n) द्वारा आवश्यक समय को इंगित करता है, यानी n का फ़ंक्शन।
फिर हम निष्कर्ष निकाल सकते हैं, कि t(0)=c, अगर हम pow(x,0) कहते हैं, हम चाहे (n==0) की जाँच करने के लिए है क्योंकि, और उसके बाद 1, जो निरंतर समय (इसलिए निरंतर c) में किया जा सकता है लौटने।
अब हम दूसरे मामले पर विचार करते हैं: n>0। यहां हम t(n) = d + t(n-1) प्राप्त करते हैं। ऐसा इसलिए है क्योंकि हमने n==1 की जांच करने के लिए फिर से की गणना की है, इसलिए (t(n-1)), और परिणाम x से गुणा करें।जांच और गुणा निरंतर समय (स्थिर d) में किया जा सकता है, pow की रिकर्सिव गणना t(n-1) की आवश्यकता है।
अब हम "विस्तार" कर सकते हैं अवधि t(n):
t(n) =
d + t(n-1) =
d + (d + t(n-2)) =
d + d + t(n-2) =
d + d + d + t(n-3) =
... =
d + d + d + ... + t(1) =
d + d + d + ... + c
इसलिए, यह कब तक ले करता है जब तक हम t(1) तक पहुँचने? चूंकि हम t(n) पर शुरू करते हैं और हम प्रत्येक चरण में 1 घटाते हैं, t(n-(n-1)) = t(1) तक पहुंचने के लिए n-1 चरण लेते हैं। यही कारण है, अन्य हाथों पर है, जिसका अर्थ है कि हम n-1 बार लगातार d मिलता है, और t(1)c लिए मूल्यांकन किया जाता है।
तो हम प्राप्त:
t(n) =
...
d + d + d + ... + c =
(n-1) * d + c
तो हम कि t(n)=(n-1) * d + c हे (एन) के तत्व है जो मिलता है।
pow2Masters theorem का उपयोग किया जा सकता है। चूंकि हम मान सकते हैं कि एल्गोरिदम के लिए समय कार्य एकान्त रूप से बढ़ रहे हैं। तो अब हम समय t(n)pow2(x,n) की गणना के लिए की जरूरत है: n>0 के लिए
t(0) = c (since constant time needed for computation of pow(x,0))
हम
/t((n-1)/2) + d if n is odd (d is constant cost)
t(n) = <
\ t(n/2) + d if n is even (d is constant cost)
पाने के लिए "सरल" ऊपर जा सकता है:
t(n) = floor(t(n/2)) + d <= t(n/2) + d (since t is monotonically increasing)
तो हम t(n) <= t(n/2) + d प्राप्त करें, जिसे मास्टर्स प्रमेय का उपयोग करके t(n) = O(log n) पर हल किया जा सकता है (देखें अनुभाग में पॉपुल विकिपीडिया लिंक में एआर एल्गोरिदम, उदाहरण "बाइनरी सर्च")।
यह थोड़ा जटिल हो सकता है, लेकिन मुझे लगता है कि हमेशा की तरह Master's theorem उपयोग करने के लिए है।
प्रत्यावर्तन अनदेखी दोनों कार्यों की जटिलता हे (1)
पहले एल्गोरिथ्म pow1 के लिए (x, n) जटिलता हे (एन) क्योंकि प्रत्यावर्तन की गहराई के साथ n रैखिक संबद्ध है।
दूसरी जटिलता के लिए ओ (लॉग एन) है। यहां हम लगभग लॉग 2 (एन) बार की मरम्मत करते हैं। 2 फेंकना हम लॉग एन प्राप्त करते हैं।
तो मुझे लगता है कि आप x को शक्ति एन में बढ़ा रहे हैं। पाउ 1 ओ (एन) लेता है।
आप कभी भी एक्स के मान को नहीं बदलते हैं, लेकिन जब तक यह 1 तक नहीं मिलता है तब तक आप 1 से 1 लेते हैं (और फिर आप वापस आते हैं) इसका मतलब है कि आप एक बार रिकर्सिव कॉल एन बार बनायेंगे।
चलो बस pow1 से शुरू करें, क्योंकि यह सबसे आसान है।
आपके पास एक ऐसा कार्य है जहां ओ (1) में एक रन किया जाता है। (हालत की जांच, वापसी, और गुणा निरंतर समय है।)
जो आपने छोड़ा है वह आपके रिकर्सन है। आपको क्या करना है यह विश्लेषण करना है कि फ़ंक्शन कितनी बार कॉल करना समाप्त कर देगा। पाउ 1 में, यह एन बार होगा। एन * हे (1) = हे (एन)।
पाउ 2 के लिए, यह वही सिद्धांत है - फ़ंक्शन का एक रन ओ (1) में चलता है। हालांकि, इस बार आप हर बार एन को रोक रहे हैं। इसका मतलब है कि यह लॉग 2 (एन) बार चलाएगा - प्रति बिट प्रभावी ढंग से एक बार। log2 (एन) * हे (1) = हे (लॉग (एन))।
कुछ है जो आप मदद कर सकता है तथ्य यह है कि प्रत्यावर्तन हमेशा यात्रा के रूप में (बहुत बस व्यक्त किया जा सकता हमेशा फायदा उठाने के लिए है, लेकिन यह संभव है। हम के रूप में
result = 1;
while(n != 0)
{
result = result*n;
n = n - 1;
}
अब आप एक पुनरावृत्ति एल्गोरिथ्म है pow1 व्यक्त कर सकते हैं बजाय, और आप पुनरावर्ती कार्यों का विश्लेषण कर रहा है (या यहां तक कि उन्हें का मूल्यांकन) एक nontrivial कार्य है यह आसान इसे उस तरह से विश्लेषण करने के लिए मिल सकती है।
यह लिंक आपकी समस्या का सटीक उत्तर प्रदान करता है। क्या - यहाँ है हे (1) * स्रोत (http://www.cs.ucf.edu/~dmarino/ucf/cop3502/lec_biswas/recursion12.pdf)
* दोनों कार्यों की जटिलता है? – kennytm
यह ओ (1) रिकर्सिव कॉल को अनदेखा कर रहा है लेकिन अलग-अलग व्यक्त किया जा सकता है। मुद्दा यह है कि कुल जटिलता पूरी तरह से रिकर्सन गहराई पर निर्भर करती है। – fgb