soit F (n) = 0.5F (n-1) et F (0) = 1
a. écrire une fonction fun1, une fonction récursive pour évaluer le terme de n
b. écrire une fonction fun2, une fonction non récursive pour évaluer le terme de n
c. quelle est la complexité temporelle de fun1 et à partir de quel terme n il sera préférable d'utiliser fun1 vs fun2 concernant la complexité de l'espace
En général, la fonction évalue le n terme de la suite {1,1 / 2,1 / 4,1 / 8, ...}
a.
double fun2( int n ){ double sum = 1, i; for (i=0 ; i < n; i++) sum=sum*(0.5); return sum; }b.
double fun1( int n ){ if (n == 0) return 1; else return 0.5*fun1(n-1); }c. Intuitivement et mathématiquement en utilisant la somme des séquences géométriques, nous pouvons montrer qu'il s'agit de
O(n)
- existe-t-il un autre moyen?
- comment gérer la complexité de l'espace?
4 Réponses :
Vous pouvez vous répondre en jetant un œil sur le code généré: https://godbolt.org/z / Gd9XxM
Je recherche une approche naïve :) mais merci pour l'approche avancée
Je comprends que c'est une question de devoir donc je ne ferai rien sur les optimisations du compilateur et la récursion de queue car ce n'est pas la propriété du programme lui-même mais cela dépend du compilateur s'il optimisera une fonction récursive ou non.
/ p>
Votre première approche est clairement O (n) car elle appelle récursivement f1 et tout ce qu'elle fait une multiplication.
Votre deuxième approche est également clairement O (n) car il ne s'agit que d'une simple boucle. Donc, pour la complexité du temps, les deux sont les mêmes O (n)
En ce qui concerne la complexité spatiale, fun1 a besoin de n enregistrements de fonction, donc c'est une complexité d'espace O (n) tandis que fun2 n'a besoin que d'une variable, donc c'est une complexité d'espace O (1). Pour ce qui est de la complexité spatiale, fun2 est une meilleure approche.
Alors que vos versions de fun1 et fun2 sont de complexité spatiale différente, leur complexité temporelle est O (n) .
Cependant , la fonction non récursive peut aussi s'écrire:
#import <math.h>
double fun2(int n) {
return pow(0.5, n);
}
Cette fonction est de complexité spatio-temporelle O (1) et le sera plus efficace pour la plupart des n (probablement n > 5).
Quant à la question d'origine: c'est très délicat car cela dépend de l'optimisation du compilateur:
Une implémentation naïve est de fun1 est de complexité spatiale O (n) comme un appel de fun1 (n) le fera ont une profondeur récursive de n et nécessitent donc n cadres d'appel sur la pile. Sur la plupart des systèmes, cela ne fonctionnera que jusqu'à un certain n . Ensuite, vous obtenez une erreur Stack Overflow car la pile a une taille limitée.
Un compilateur d'optimisation reconnaîtra qu'il s'agit d'une fonction récursive de queue et l'optimisera en quelque chose de très proche de fun2 , qui a une complexité spatiale de O (1) car il utilise un nombre fixe de variable avec une taille fixe indépendante de n et non récursivité.
Vous devez préciser que vous parlez de complexité temporelle, car la question concerne également la complexité spatiale.
Pour une approche récursive et itérative, la complexité peut être réduite à O (log n) :
La profondeur récursive de la solution suivante est log n :
double fun4( int n ){
int i;
double f = (n % 2 ? 0.5 : 1.0);
for (i = n; i > 1; i /= 2)
f *= 0.5*0.5;
return f;
}
Le nombre d'itérations dans la boucle suivante est également log n :
double fun3( int n ){
double f;
if ( n == 0 )
return 1.0;
f = fun3( n/2 );
return f * f * (n % 2 ? 0.5 : 1.0);
}
p >
Qu'en est-il? Qu'est-ce qu'il est censé accomplir?
Une réflexion sur la complexité de l'espace: (en laissant de côté l'optimisation de la récursivité de queue)
fun1 ()devra consommer n cadres de pile (ou appeler des contextes ou autre) là oùfun2 ()consommera toujours exactement 1.@Scheff
0.5 * fun1 (n-1)n'est jamais une récursion de queue car il doit faire une multiplication avec le résultat.@Sylwester Il semble que j'ai surestimé ce que les compilateurs modernes sont capables de reconnaître. J'ai bidouillé un peu avec le plus récent gcc et cliquetis dans godbolt qui "prouvait" que vous aviez raison. Heureux d'avoir écrit " peut arriver" ... ;-)