Pourquoi l'algorithme est dans O(n2)?
Je croyais que la complexité des algorithmes récursifs croit exponentiellement.
Salut Louis
Ce n’est pas le cas. Il existe même des algorithmes récursifs qui sont plus efficaces que O(n^2). Voir ex 2 de l’examen 2016.
Dans ce cas là l’instruction qui sera caractérisera la complexité (qui sera exécutée le plus souvent) est la comparaison « si L[1] = L[i] »
Dans le pire cas que aucun élément est egal à un autre. Cette conditions sera testée n-1 fois. Donc un appel de cette fonction ce laisse écrire comme (ce sont des maths conceptuelles - le calcul n’est formellement pas super correct):
Complexité_fonction(n) = (n-1) + Compexité_fonction(n-1) + c
Pour le deuxième appel:
Complex_fonc(n-1) = (n-2) + Complex_fonc(n-2) + c
....
Coplex_fonc n(1) = c
Combien de fois on peut soustraire 1 de n? -> n fois.
Donc on aura n*((n-d)+ c) —> O(n^2)
Ce n’est pas le cas. Il existe même des algorithmes récursifs qui sont plus efficaces que O(n^2). Voir ex 2 de l’examen 2016.
Dans ce cas là l’instruction qui sera caractérisera la complexité (qui sera exécutée le plus souvent) est la comparaison « si L[1] = L[i] »
Dans le pire cas que aucun élément est egal à un autre. Cette conditions sera testée n-1 fois. Donc un appel de cette fonction ce laisse écrire comme (ce sont des maths conceptuelles - le calcul n’est formellement pas super correct):
Complexité_fonction(n) = (n-1) + Compexité_fonction(n-1) + c
Pour le deuxième appel:
Complex_fonc(n-1) = (n-2) + Complex_fonc(n-2) + c
....
Coplex_fonc n(1) = c
Combien de fois on peut soustraire 1 de n? -> n fois.
Donc on aura n*((n-d)+ c) —> O(n^2)
Bonjour,
Un algorithme récursif ne croît pas nécessairement de manière exponentielle. Par exemple, on pourrait tout à fait développer une version récursive de la recherche dichotomique en O(logn).
Ce n'est toutefois pas une règle absolue en soi. Il arrive parfois qu'une traduction fidèle d'un algorithme itératif en une version récursive aboutisse à une complexité différente, parfois moins bonne.
Je ne crois pas que la suite de Fibonacci ait été vue en cours, mais il s'agit d'un très bon exemple où la version itérative a une complexité O(n) alors que la version récursive a une complexité O(2^n).
Pour compléter : exemples d'algorithmes récursifs vus en cours :
- non exponentiels : recherche par dichotomie (en O(log(n) ; leçon I.1), somme des N premiers entiers (en O(n) ; leçon I.2), tri par insertion (en O(n^2) ; leçon I.2)
- exponentiel avec version itérative linéaire : coefficients du binôme (leçon I.2).
Merci pour les réponses