एक रिकर्सन एल्गोरिदम

Question

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

इस कोड को देखते हुए:

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)?

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

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

Answer 1

इस विधि 3 आदि के साथ उसके बाद ही O(n) चल रहा है, क्योंकि अगर आप इसे 5 के साथ चलाने के लिए, यह 4 के साथ प्रत्यावर्तन के लिए चला जाता है,

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 

Answer 2

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

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

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