Complexité algorithme
Résolu/Fermé
azerty27
Messages postés
6
Date d'inscription
mercredi 14 août 2013
Statut
Membre
Dernière intervention
22 juin 2014
-
25 août 2013 à 10:15
azerty27 Messages postés 6 Date d'inscription mercredi 14 août 2013 Statut Membre Dernière intervention 22 juin 2014 - 5 déc. 2013 à 08:02
azerty27 Messages postés 6 Date d'inscription mercredi 14 août 2013 Statut Membre Dernière intervention 22 juin 2014 - 5 déc. 2013 à 08:02
A voir également:
- Complexité algorithme
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- Code ascii algorithme - Guide
- Remplir une matrice algorithme - Forum Pascal
- Algorithme qui calcule le carré d'un nombre - Forum Algorithmes / Méthodes
- Ecrire un algorithme qui permet de resoudre ax²+bx+c=0 - Forum Programmation
1 réponse
Doctor C
Messages postés
627
Date d'inscription
mardi 12 juin 2007
Statut
Membre
Dernière intervention
19 février 2016
398
Modifié par Doctor C le 7/11/2013 à 21:20
Modifié par Doctor C le 7/11/2013 à 21:20
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";
7 nov. 2013 à 21:41
Quand 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²)
8 nov. 2013 à 15:44
Il faudrait que je ressorte mes livres d'université!
5 déc. 2013 à 08:02