1 réponse
Doctor C
- Messages postés
- 1259
- Date d'inscription
- mardi 12 juin 2007
- Statut
- Membre
- Dernière intervention
- 19 février 2016
Bon, mes cours d'analyse d'algo sont un peu loin mais voici ma pensée:
Algo 1:
La boucle externe (i) varie selon le nombre d'éléments à traiter n moins 10. Cette boucle a une complexité de O(n-10) ce qui peut être réduit à O(n).
La boucle interne (j) possède une complexité constante, c'est-à-dire 10.
L'algorithme aurait donc une complexité de O(10n), la constante étant négligeable, on peut simplement retirer le 10 et on obtient: O(n)
Algo 2:
La boucle externe (i) varie selon le nombre d'éléments à traiter n. Cette boucle a une complexité de O(n).
La boucle interne (j) varie proportionnellement à i (qui est directement lié à n), cette boucle possède donc aussi une complexité de O(n).
L'algorithme aura donc une complexité de O(n) * O(n) = O(n²).
Echo "Lima Mike Alfa";
Algo 1:
La boucle externe (i) varie selon le nombre d'éléments à traiter n moins 10. Cette boucle a une complexité de O(n-10) ce qui peut être réduit à O(n).
La boucle interne (j) possède une complexité constante, c'est-à-dire 10.
L'algorithme aurait donc une complexité de O(10n), la constante étant négligeable, on peut simplement retirer le 10 et on obtient: O(n)
Algo 2:
La boucle externe (i) varie selon le nombre d'éléments à traiter n. Cette boucle a une complexité de O(n).
La boucle interne (j) varie proportionnellement à i (qui est directement lié à n), cette boucle possède donc aussi une complexité de O(n).
L'algorithme aura donc une complexité de O(n) * O(n) = O(n²).
Echo "Lima Mike Alfa";
- Messages postés
-
15932
- Date d'inscription
- samedi 31 mai 2008
- Statut
- Modérateur
- Dernière intervention
- 9 juillet 2020
2 629Quand i=1 on fait 1 boucle j, quand i=2 on fait 2 boucles j, , quand i=3 on fait 3 boucles j, etc.
Du coup on fait 1+2+3+...+n boucles j au total. Soit n(n+1)/2 opérations élémentaires x += 3
La complexité est donc de O(n²/2+n/2+1) = O(n²)
- Messages postés
-
1259
- Date d'inscription
- mardi 12 juin 2007
- Statut
- Membre
- Dernière intervention
- 19 février 2016
384Il faudrait que je ressorte mes livres d'université!