Complexité d'algorithmes
Fermé
Lucie22
-
18 mars 2022 à 21:17
KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 - 19 mars 2022 à 14:57
KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 - 19 mars 2022 à 14:57
A voir également:
- Complexité d'algorithmes
- Complexité ✓ - Forum Programmation
- Complexité - Forum C
- Complexité Fibonacci ✓ - Forum Programmation
- Les algorithmes les plus connus - Forum Programmation
- Algorithmes - Forum Facebook
1 réponse
KX
Messages postés
16734
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
24 avril 2024
3 015
19 mars 2022 à 14:57
19 mars 2022 à 14:57
Bonjour,
"J'ai du mal à comprendre la notion de complexité d'algorithmes."
Pour faire simple, il s'agit d'estimer le nombre de ressources que ton programme devra traiter. Dans ton cas il s'agit de la complexité en temps de calcul, mais cela pourrait aussi être une complexité en mémoire.
Cela permet d'anticiper théoriquement le comportement du programme quand on augmente le nombre de données à traiter. On peut ainsi comparer deux algorithmes entre eux et choisir lequel sera le plus adapté, par exemple le plus rapide, le moins gourmand en mémoire, ou un compromis entre les deux.
"Le premier n'étant pas récursif, je pense avoir trouvé qu'il s'agit d'une complexité O(n) [...] j'en suis arrivée à trouver une complexité en O(n) pour le troisième, et en O(log(n)) pour les 2 autres."
Je suis d'accord avec les résultats. Toutefois, au niveau du raisonnement dire qu'il est en O(n) car il n'est pas récursif est faux, on pourrait très bien réécrire les autres algorithmes en enlevant leur récursivité, ils conserveraient quand même leur complexité logarithmique en temps.
Remarque : enlever la récursivité de l'algorithme diminuerait cependant la complexité en mémoire.
"comment je suis censé procéder pour trouver la complexité d'algo récursifs ?"
On peut le faire mathématiquement, en se servant d'outils simples tels que les suites, le raisonnement par récurrence, ou plus avancés comme la comparaison asymptotique, d'où viennent notamment les notation de Landeau comme O(n)
Exemple, avec multiRec
Si x = 0 : f(x) = 1 => on est passé une fois dans la méthode
Si x > 0 et x%2 == 0 : f(x)= 1 + f(x/2) => on passe une fois dans la méthode, plus le nombre de fois pour f(x/2)
Si x > 0 et x%2 != 0 : f(x)= 1 + f((x-1)/2) = 1 + f(x/2) => on a donc un seul cas pour x > 0
Soit x=2^n : f(x)=1+f(x/2) <=> f(2^n)=1+f(2^(n-1))=2+f(2^(n-2))=3+f(2^(n-3))= ... = n + f(2^0)
Donc f(2^n) = O(n) <=> f(x) = O(ln(x))
Pour résumer :
"J'ai du mal à comprendre la notion de complexité d'algorithmes."
Pour faire simple, il s'agit d'estimer le nombre de ressources que ton programme devra traiter. Dans ton cas il s'agit de la complexité en temps de calcul, mais cela pourrait aussi être une complexité en mémoire.
Cela permet d'anticiper théoriquement le comportement du programme quand on augmente le nombre de données à traiter. On peut ainsi comparer deux algorithmes entre eux et choisir lequel sera le plus adapté, par exemple le plus rapide, le moins gourmand en mémoire, ou un compromis entre les deux.
"Le premier n'étant pas récursif, je pense avoir trouvé qu'il s'agit d'une complexité O(n) [...] j'en suis arrivée à trouver une complexité en O(n) pour le troisième, et en O(log(n)) pour les 2 autres."
Je suis d'accord avec les résultats. Toutefois, au niveau du raisonnement dire qu'il est en O(n) car il n'est pas récursif est faux, on pourrait très bien réécrire les autres algorithmes en enlevant leur récursivité, ils conserveraient quand même leur complexité logarithmique en temps.
Remarque : enlever la récursivité de l'algorithme diminuerait cependant la complexité en mémoire.
"comment je suis censé procéder pour trouver la complexité d'algo récursifs ?"
On peut le faire mathématiquement, en se servant d'outils simples tels que les suites, le raisonnement par récurrence, ou plus avancés comme la comparaison asymptotique, d'où viennent notamment les notation de Landeau comme O(n)
Exemple, avec multiRec
Si x = 0 : f(x) = 1 => on est passé une fois dans la méthode
Si x > 0 et x%2 == 0 : f(x)= 1 + f(x/2) => on passe une fois dans la méthode, plus le nombre de fois pour f(x/2)
Si x > 0 et x%2 != 0 : f(x)= 1 + f((x-1)/2) = 1 + f(x/2) => on a donc un seul cas pour x > 0
Soit x=2^n : f(x)=1+f(x/2) <=> f(2^n)=1+f(2^(n-1))=2+f(2^(n-2))=3+f(2^(n-3))= ... = n + f(2^0)
Donc f(2^n) = O(n) <=> f(x) = O(ln(x))
Pour résumer :
- multiIter : O(n) en temps, O(1) en mémoire
- multiRec : O(ln(n)) en temps, O(ln(n)) en mémoire
- puissanceRec : O(n) en temps, O(n) en mémoire
- exponentiationRapide : O(ln(n)) en temps, O(ln(n)) en mémoire