एक रिकर्सन एल्गोरिदम में जटिलता - एल्गोरिदम, रिकर्सन, बिग-ओ, समय-जटिलता, जटिलता-सिद्धांत

मैं वर्तमान में विश्वविद्यालय में डेटा संरचनाओं का अध्ययन कर रहा हूं और पुनरावृत्ति में जटिलता के बारे में एक सवाल पर ठोकर खाई है।

इस कोड को दिया:

Unsigned func (unsigned n)
{
if (n ==0) return 1;
if(n==1) return 2;

\do somthing(in O(1) )

return func(n-1) + func(n-1);
}

मुझे पता है कि कोड क्या करता है। मुझे पता है कि इस रूप में अब समय जटिलता ओ (2 ^ एन) है।

हालांकि मेरा सवाल यह है कि क्या कोड की अंतिम रिटर्न कॉल के बजाय यदि मैं लिखूंगा तो समय की जटिलता बदल जाएगी: return 2*func(n-1) ?

मैं जानता हूं कि जहां तक ​​मेमोरी कॉम्प्लेक्सिटी की बात है, हम रिकर्सन द्वारा लिए गए स्पेस में भारी कमी की बात कर रहे हैं, लेकिन जहां तक ​​कॉम्प्लेक्सिटी की बात है, क्या इसमें कोई बदलाव होगा?

मैंने एक पुनरावर्ती फ़ंक्शन का उपयोग करके गणित किया और यह समझ में आया कि क्या समय की जटिलता में कोई बदलाव नहीं होगा, क्या मैं सही हूं?

उत्तर:

उत्तर № 1 के लिए 4

यह विधि केवल चल रही है O(n), क्योंकि यदि आप इसे 5 के साथ चलाते हैं, तो यह 4 के साथ पुनरावृत्ति में चला जाता है, फिर 3 के साथ।

Unsigned func (unsigned n)
{
if (n ==0) return 1;
if(n==1) return 2;

\do somthing(in O(1) )

return 2*func(n-1);
}

हालाँकि इस बारे में क्या:

Unsigned func (unsigned n)
{
if (n ==0) return 1;
if(n==1) return 2;

\do somthing(in O(1) )

return func(n-1) + func(n-1);
}

उदाहरण के लिए func (5) यह निम्नलिखित के रूप में पहले निष्पादित करेगा

5 -> 4 -> 3 -> 2 -> 1

फिर यह 2 पर लौटता है, लेकिन वहां यह "दूसरा" भाग निष्पादित करेगा, इसलिए पूरी प्रक्रिया दिखती है

5 -> 4 -> 3 -> 2-> 1; 2-> 1; 3->2->1; etc.

इसलिए यह जटिलता को काफी हद तक बदल देता है O(n) सेवा मेरे O(2^n)

---

इस कोड को व्यावहारिक उदाहरण देने की कोशिश करें:

public class Complexity {
private static int counter;
public static void main(String[] args) {
for (int i = 0; i < 20; i++) {
counter = 0;
func(i);
System.out.println("For n="+i+" of 2*func the number of cycles is " + counter);
counter = 0;
func2(i);
System.out.println("For n="+i+" of func + func the number of cycles is " + counter);
}
}

public static int func(int n) {
counter++;
if (n == 0) {
return 1;
}
if (n == 1) {
return 2;
}
return 2 * func(n - 1);
}

public static int func2(int n) {
counter++;
if (n == 0) {
return 1;
}
if (n == 1) {
return 2;
}
return func2(n - 1) + func2(n - 1);
}
}

इस उत्पादन के बाद:

For n=0 of 2*func the number of cycles is 1
For n=0 of func + func the number of cycles is 1
For n=1 of 2*func the number of cycles is 1
For n=1 of func + func the number of cycles is 1
For n=2 of 2*func the number of cycles is 2
For n=2 of func + func the number of cycles is 3
For n=3 of 2*func the number of cycles is 3
For n=3 of func + func the number of cycles is 7
For n=4 of 2*func the number of cycles is 4
For n=4 of func + func the number of cycles is 15
For n=5 of 2*func the number of cycles is 5
For n=5 of func + func the number of cycles is 31
For n=6 of 2*func the number of cycles is 6
For n=6 of func + func the number of cycles is 63
For n=7 of 2*func the number of cycles is 7
For n=7 of func + func the number of cycles is 127
For n=8 of 2*func the number of cycles is 8
For n=8 of func + func the number of cycles is 255
For n=9 of 2*func the number of cycles is 9
For n=9 of func + func the number of cycles is 511
For n=10 of 2*func the number of cycles is 10
For n=10 of func + func the number of cycles is 1023
For n=11 of 2*func the number of cycles is 11
For n=11 of func + func the number of cycles is 2047
For n=12 of 2*func the number of cycles is 12
For n=12 of func + func the number of cycles is 4095
For n=13 of 2*func the number of cycles is 13
For n=13 of func + func the number of cycles is 8191
For n=14 of 2*func the number of cycles is 14
For n=14 of func + func the number of cycles is 16383
For n=15 of 2*func the number of cycles is 15
For n=15 of func + func the number of cycles is 32767
For n=16 of 2*func the number of cycles is 16
For n=16 of func + func the number of cycles is 65535
For n=17 of 2*func the number of cycles is 17
For n=17 of func + func the number of cycles is 131071
For n=18 of 2*func the number of cycles is 18
For n=18 of func + func the number of cycles is 262143
For n=19 of 2*func the number of cycles is 19
For n=19 of func + func the number of cycles is 524287

---

लेकिन अगर आपको पहले से ही गणना किए गए परिणाम याद हैं, तो जटिलता अभी भी है O(n) दूसरे दृष्टिकोण के साथ भी:

public class Complexity {
private static int counter;
private static int[] results;

public static void main(String[] args) {
for (int i = 0; i < 20; i++) {
counter = 0;
func(i);
System.out.println("For n="+i+" of 2*func the number of cycles is " + counter);
counter = 0;
func2(i);
System.out.println("For n="+i+" of func + func the number of cycles is " + counter);
counter = 0;
results = new int[i+1];
func3(i);
System.out.println("For n="+i+" of func + func with remembering the number of cycles is " + counter);
}
}

public static int func(int n) {
counter++;
if (n == 0) {
return 1;
}
if (n == 1) {
return 2;
}
return 2 * func(n - 1);
}

public static int func2(int n) {
counter++;
if (n == 0) {
return 1;
}
if (n == 1) {
return 2;
}
return func2(n - 1) + func2(n - 1);
}

public static int func3(int n) {
counter++;
if (n == 0) {
return 1;
}
if (n == 1) {
return 2;
}

if (results[n] == 0){
results[n] = func3(n - 1) + func3(n - 1);
}

return results[n];
}
}

इस उत्पादन के बाद:

For n=0 of 2*func the number of cycles is 1
For n=0 of func + func the number of cycles is 1
For n=0 of func + func with remembering the number of cycles is 1
For n=1 of 2*func the number of cycles is 1
For n=1 of func + func the number of cycles is 1
For n=1 of func + func with remembering the number of cycles is 1
For n=2 of 2*func the number of cycles is 2
For n=2 of func + func the number of cycles is 3
For n=2 of func + func with remembering the number of cycles is 3
For n=3 of 2*func the number of cycles is 3
For n=3 of func + func the number of cycles is 7
For n=3 of func + func with remembering the number of cycles is 5
For n=4 of 2*func the number of cycles is 4
For n=4 of func + func the number of cycles is 15
For n=4 of func + func with remembering the number of cycles is 7
For n=5 of 2*func the number of cycles is 5
For n=5 of func + func the number of cycles is 31
For n=5 of func + func with remembering the number of cycles is 9
For n=6 of 2*func the number of cycles is 6
For n=6 of func + func the number of cycles is 63
For n=6 of func + func with remembering the number of cycles is 11
For n=7 of 2*func the number of cycles is 7
For n=7 of func + func the number of cycles is 127
For n=7 of func + func with remembering the number of cycles is 13
For n=8 of 2*func the number of cycles is 8
For n=8 of func + func the number of cycles is 255
For n=8 of func + func with remembering the number of cycles is 15
For n=9 of 2*func the number of cycles is 9
For n=9 of func + func the number of cycles is 511
For n=9 of func + func with remembering the number of cycles is 17
For n=10 of 2*func the number of cycles is 10
For n=10 of func + func the number of cycles is 1023
For n=10 of func + func with remembering the number of cycles is 19
For n=11 of 2*func the number of cycles is 11
For n=11 of func + func the number of cycles is 2047
For n=11 of func + func with remembering the number of cycles is 21
For n=12 of 2*func the number of cycles is 12
For n=12 of func + func the number of cycles is 4095
For n=12 of func + func with remembering the number of cycles is 23
For n=13 of 2*func the number of cycles is 13
For n=13 of func + func the number of cycles is 8191
For n=13 of func + func with remembering the number of cycles is 25
For n=14 of 2*func the number of cycles is 14
For n=14 of func + func the number of cycles is 16383
For n=14 of func + func with remembering the number of cycles is 27
For n=15 of 2*func the number of cycles is 15
For n=15 of func + func the number of cycles is 32767
For n=15 of func + func with remembering the number of cycles is 29
For n=16 of 2*func the number of cycles is 16
For n=16 of func + func the number of cycles is 65535
For n=16 of func + func with remembering the number of cycles is 31
For n=17 of 2*func the number of cycles is 17
For n=17 of func + func the number of cycles is 131071
For n=17 of func + func with remembering the number of cycles is 33
For n=18 of 2*func the number of cycles is 18
For n=18 of func + func the number of cycles is 262143
For n=18 of func + func with remembering the number of cycles is 35
For n=19 of 2*func the number of cycles is 19
For n=19 of func + func the number of cycles is 524287
For n=19 of func + func with remembering the number of cycles is 37

---

जवाब के लिए 2 № 2

यह आपकी प्रोग्रामिंग / एल्गोरिथम भाषा के शब्दार्थ पर निर्भर करता है।

अगर द्वारा f(n) आपका मतलब है "फ़ंक्शन को कॉल करें चाहे वह कोई भी होउसी तर्क के साथ कहा जाता है "" (जैसा कि अधिकांश प्रोग्रामिंग भाषाओं के मामले में है), तो आपका परिवर्तन ओ (एन) के लिए नाटकीय रूप से जटिलता को कम कर देगा। आपके पास तर्क की गिरावट के अनुसार एक ओ (1) फ़ंक्शन कॉल है।

अन्यथा (यदि आप शुद्ध कार्यों के बारे में बोल रहे हैं और ज्ञात परिणामों को याद कर रहे हैं), दोनों एल्गोरिदम में जटिलता ओ (एन) पहले से ही है।

---