Complessità in un algoritmo di ricorsione

Attualmente sto studiando le strutture dati all'università e mi sono imbattuto in una domanda sulla complessità nella ricorsione.Complessità in un algoritmo di ricorsione

Dato questo codice:

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

So cosa fa il codice. So che nella forma in cui è ora, la complessità temporale è O (2^n).

La mia domanda tuttavia è: cambierà la complessità del tempo se invece dell'ultima chiamata di ritorno del codice scriverò: return 2*func(n-1)?

So che per quanto riguarda la complessità della memoria, stiamo parlando di una significativa riduzione dello spazio preso dalla ricorsione, ma per quanto riguarda la complessità del tempo, ci sarà qualche cambiamento?

Ho fatto i calcoli utilizzando una funzione ricorsiva e ho capito che non ci saranno cambiamenti nella complessità del tempo, ho ragione?

fonte

2015-11-05 Tom

Questo metodo sta avendo solo O(n), perché se lo si esegue con 5, va a ricorsione con 4, poi con 3 ecc

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

\\do somthing(in O(1)) 

return 2*func(n-1); 
}

Tuttavia ciò che su questo:

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

Ad esempio func (5) verrà eseguito per primo come segue

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

Quindi torna a 2, ma ci si eseguirà la parte "secondo", così l'intero processo sembra

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

Quindi non cambia la complessità drasticamente da O(n) al O(2^n)

Proviamo esempio pratico di questo codice:

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

Avere questa uscita:

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

Ma se vi ricordate risultati già calcolati, la complessità è ancora O(n) anche con il secondo approccio:

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

Avere questa uscita:

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

fonte

2015-11-05 14:16:44 libik

Quindi avevo ragione che la chiamata ricorsiva di func (n-1) + func (n-1) è in esecuzione a una complessità di O (2^n)? inoltre, come mai nella mia formula di ricorsione, quando scrivo su carta e calcola, capisco che entrambi hanno la stessa complessità temporale? – Tom

@ Tom - sì, funziona alla complessità O (2^n) ... sulla tua formula - la stai usando male o hai una formula sbagliata. Pubblica quella formula alla tua domanda e forse possiamo dirti cosa c'è di sbagliato. – libik

La mia formula è: T (n) = 2T (n-1) mentre T (0) = 1, T (1) = 2. Ho usato il "metodo di registrazione" e ho ottenuto la funzione generale: T (n) = 2^i * T (ni). dopo aver posizionato le mie condizioni di arresto come i = n-1 o i = n-2, ho raggiunto la complessità di T (n) = 2^(n-1) * T (1) = (2^n)/2 - ------> O (2^n). lo stesso risultato per l'altra condizione di arresto. cosa sto facendo male, dato che stavo ottenendo la stessa formula per entrambi i tipi di codice. – Tom

Dipende dalla semantica di il tuo linguaggio di programmazione/algoritmo.

Se per f(n) vuoi dire "chiama la funzione, non importa se è stato chiamato con lo stesso argomento prima" (come è il caso con la maggior parte dei linguaggi di programmazione), quindi la modifica ridurrà la complessità drammaticamente a O (n) . Hai una chiamata di funzione O (1) per decremento dell'argomento.

Altrimenti (se si parla di funzioni pure e si memorizzano risultati noti), entrambi gli algoritmi hanno già complessità O (n).

fonte

2015-11-05 14:17:37

Complessità in un algoritmo di ricorsione

risposta

Problemi correlati