Złożoność w algorytmie rekursji

Question

Obecnie studiuję struktury danych na uniwersytecie i natknąłem się na pytanie o złożoność rekursji.

Biorąc pod uwagę ten kod:

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); 
} 

wiem co kod robi. Wiem, że w obecnej formie złożoność czasu wynosi O (2^n).

Moje pytanie brzmi jednak: czy złożoność czasu zmieni się, jeśli zamiast ostatniego wywołania zwrotnego kodu napiszę: return 2*func(n-1)?

Wiem, że jeśli chodzi o złożoność pamięci, mówimy o znacznej redukcji przestrzeni zajmowanej przez rekurencję, ale jeśli chodzi o złożoność czasu, czy nastąpi jakakolwiek zmiana?

Zrobiłem matematykę używając funkcji rekursywnej i doszedłem do zrozumienia, że ​​nie będzie zmian w złożoności czasu, czy mam rację?

Answer 1

Metoda ta jest posiadanie tylko O(n), bo jeśli go uruchomić z 5, to idzie do rekursji z 4, potem 3 itd

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

\\do somthing(in O(1)) 

return 2*func(n-1); 
} 

Jednak co na ten temat:

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); 
} 

Na przykład func (5) wykona najpierw jako następującą kolejno:

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

Następnie powraca do 2, ale nie będzie to wykonać „drugiej” strony, więc cały proces wygląda

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

Dlatego nie zmienia złożoność drastycznie od O(n) do O(2^n)

---

Spróbujmy praktyczny przykład ten kod:

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); 
    }  
} 

Mając to wyjście:

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 

---

Ale jeśli pamiętam już obliczone wyniki, złożoność jest jeszcze O(n) nawet przy drugim podejściu:

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]; 
    }   
} 

Mając to wyjście:

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

To zależy od semantyczny od twój język programowania/algorytmu.

Jeśli przez f(n) masz na myśli "zadzwoń do funkcji bez względu na to, czy została ona wywołana z tym samym argumentem przed" (jak to jest w przypadku większości języków programowania), to twoja zmiana dramatycznie zredukuje złożoność do O (n) . Masz jedno wywołanie funkcji O (1) na jeden ubytek argumentu.

W przeciwnym razie (jeśli mówimy o czystych funkcjach i zapamiętujemy znane wyniki), oba algorytmy mają już złożoność O (n).