Ecriture d'une relation de récurrence pour une méthode

Question

J'ai un peu de code et j'ai besoin d'écrire une relation de récurrence pour cela. Le code calcule simplement 2 élevés à la puissance nième. Toute aide est appréciée.

public static int two(int n) { 

    if (n==0) { 
     return 1; 
    } else if (n%2 == 0) { 
     int x = two(n/2); 
     return x*x; 
    } else { 
     return 2 * two(n-1) 
} 

Answer 1

La formulation de la fonction est presque une relation de récurrence. Fondamentalement, tout ce que vous devez faire est d'effectuer un changement de variables de sorte que l'argument à two dans la récursivité est n. Par exemple, prenez la fonction Fibonacci suivante:

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

Vous ne voulez pas utiliser cette mise en œuvre, car il est horriblement inefficace, mais il fait écrire la relation de récurrence facile:

 
fib0=1 
fib1=1 
fibn+2 = fibn+1 + fibn 

Avec le fibonacci Par exemple, vous n'avez pas réellement besoin d'effectuer le changement de variables. Cependant, avec votre fonction two, il sera plus simple d'écrire la relation.

Answer 2

Les lignes qui n'ont pas d'appels récursifs sont effectuées dans un temps constant que nous appellerons c.

T(n)=T(n-1)+c if n is odd. 
T(n)=T(n/2)+c if n is even. 

Après chaque appel récursif avec n impair, le prochain appel récursif nous soit avec n-1 même. Donc, dans le pire des cas, nous commençons par n impair -> n-1 est pair -> (n-1)/2 est impair -> (n-1)/2-1 est pair et ainsi de suite ...

Si par exemple nous commençons par n = 19 alors 19 est impair -> 18 est pair -> 9 est impair -> 8 est pair -> 4 est pair -> 2 est pair -> 0.

La profondeur de l'arbre récursif est sur lgn, et comme à chaque niveau il y a des opérations c alors le temps courant est clgn = O (lgn).