J'étudie actuellement les structures de données à l'université et suis tombé sur une question sur la complexité de la récursivité.
Étant donné ce code:
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);
}
Je sais ce que fait le code. Je sais que sous sa forme actuelle, la complexité temporelle est O (2 ^ n).
Ma question est cependant: la complexité temporelle changera-t-elle si au lieu du dernier appel de retour du code j'écrirai: return 2*func(n-1) ?
Je sais qu'en ce qui concerne la complexité de la mémoire, nous parlons d'une réduction importante de l'espace occupé par la récursivité, mais en ce qui concerne la complexité temporelle, y aura-t-il un changement?
J'ai fait le calcul en utilisant une fonction récursive et j'ai compris qu'il n'y aura pas de changement dans la complexité du temps, ai-je raison?
Réponses:
4 pour la réponse № 1Cette méthode a seulement O(n), car si vous l'exécutez avec 5, il passe en récursivité avec 4, puis avec 3, etc.
Unsigned func (unsigned n)
{
if (n ==0) return 1;
if(n==1) return 2;
\do somthing(in O(1) )
return 2*func(n-1);
}
Mais qu'en est-il:
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);
}
Par exemple, func (5) s'exécutera d'abord comme suit
5 -> 4 -> 3 -> 2 -> 1
Ensuite, il revient à 2, mais là, il exécutera la "deuxième" partie, de sorte que l'ensemble du processus ressemble à
5 -> 4 -> 3 -> 2-> 1; 2-> 1; 3->2->1; etc.
Par conséquent, cela change radicalement la complexité de O(n) à O(2^n)
Essayons d'exemple pratique ce code:
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);
}
}
Ayant cette sortie:
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
Mais si vous vous souvenez des résultats déjà calculés, la complexité est toujours O(n) même avec la deuxième approche:
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];
}
}
Ayant cette sortie:
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 pour la réponse № 2
Cela dépend de la sémantique de votre langage de programmation / algorithme.
Si par f(n) vous voulez dire "appeler la fonction, peu importe si elle étaitappelé avec le même argument avant "(comme c'est le cas avec la plupart des langages de programmation), votre modification réduira considérablement la complexité en O (n). Vous avez un appel de fonction O (1) par décrémentation de l'argument.
Sinon (si vous parlez de fonctions pures et de mémorisation de résultats connus), les deux algorithmes ont déjà la complexité O (n).