CALCULER LA COMPLEXITÉ TEMPORELLE DES BOUCLES
01-10-2019 ⁞ ESSADDOUKI ⁞ MP, PSI et la TSI, Analyse des algorithmes,
Annonce supprimée. Détails
Pour analyser un code de programmation ou un algorithme, il convient de noter que chaque instruction affecte les performances
globales de l'algorithme. Par conséquent, chaque instruction doit être analysée séparément pour analyser les performances globales.
Mais gardez à l’esprit que la complexité temporelle d’une fonction (ou d’un ensemble d’instructions) est considérée comme étant O (1)
si elle ne contient ni boucle, ni récursivité, ni appel à aucune autre fonction temporelle non constante.
Les structures de contrôle présentes dans chaque code de programmation ont une analyse asymptotique spécifique.
dans ce cours, nous discuterons en détail de la façon d'analyser ces structures de contrôle pour décider de la complexité d'un
algorithme
Les structures de contrôle communes dans chaque algorithme sont
Structure conditionnelle IF-ELSE
Boucle WHILE
Boucle FOR
Supposons que notre algorithme se compose de deux parties A et B. A prend le temps tA et B prend le temps tB pour le calcul. Le calcul
total "tA + tB" est conforme à la règle maximale, donc le temps de calcul est (max(tA, tB)).
So let's start and dive in
Méthode de comptage
La complexité est une question de comptage. Pour comprendre comment analyser un algorithme, nous devons savoir compter le
nombre de comparaisons, d'affectations, etc. En général, nous devons compter les opérations élémentaires.
La liste suivante montre les différentes opérations élémentaires
Affectation
Addition, soustraction, division
Comparaison
Comme compter devient difficile quand on a beaucoup d'opérations élémentaires, on compte toutes ces opérations élémentaires
comme O(1)
Exemple
1 a = 2+3 ?
2 b = 2
3 c = a+b
la complexité des instructions ci-dessus est O(1)
Structure conditionnelle SI
Langage C Python
1 if(condition){ ?
2 // bloc A
3 }
4 else{
5 // bloc B
6 }
Supposons que le bloc A prenne le temps tA et le bloc B prenne le temps tB, alors selon la règle maximale, ce temps de calcul est
max(tA,tB).
Exemple
Supposons que tA = n
3
et tB , alors le calcul total est :
= 2n + 1
Calcul total = max(tA, tB)
3
= max(O(n ), O(2n + 1))
3
= O(n )
Boucle for
Avant de commencer à prendre des exemples sur la façon de calculer la complexité de la boucle for, je vais prendre un exemple et le
décomposer, pour montrer comment compter le nombre d'opérations élémentaires,
Langage C Python
1 a=3+b
2 for(int i=0;i<n;i++){
3 printf("%d",i);
4 }
La première ligne contenant une affectation et l'addition de deux nombres est une instruction simple, nous comptons donc cette ligne
comme étant O(1).
En venant à la boucle for
Nous ne faisons l'initialisation qu'une fois au début de la boucle for (i = 0)
A chaque itération, on incrémente "i" de 1, on fait l'incrémentation n fois
Chaque fois que nous incrémentons i, nous vérifions si la nouvelle valeur devient égale ou supérieure à n, nous effectuons
donc la comparaison n + 1 fois (n fois lorsque i <n et une comparaison supplémentaire lorsque i devient égal à n)
Selon la règle maximale, la boucle est exécutée n+1 (max (1, n + 1, n))
En conclusion, la boucle for est exécutée n+1 fois, mais les instructions à l'intérieur de la boucle for sont exécutées n fois.
Pour l'exemple ci-dessus, car à l'intérieur de la boucle, nous n'imprimons que la valeur de i, qui prend un temps constant. on peut donc
dire que cette instruction est exécutée n fois, ce qui signifie que la complexité du programme est O(n).
T (n) = 2n + 2 = O(n)
Exemple 1 :
Une boucle ou une récursion qui s'exécute un nombre de fois constant est considérée comme un O(1). Par exemple, la boucle suivante
est O(1).
Langage C Python
1 // Ici c est une constante
2 for(int i=0;i<c;i++){
3 // quelques expressions d'ordre O(1)
4 }
5
6 // exemple :
7 for(int i=0;i<50;i++){
8 // quelques expressions d'ordre O(1)
9 }
Exemple 2 :
si la boucle est incrémentée ou décrémentée d'une valeur constante, la complexité est d'ordre O(n)
Langage C Python
1 for(int i=0;i<n;i+=c){ // O(n+1) ?
2 // quelques expressions d'ordre O(1) // O(n)
3
4 }
Si nous n'avons aucune boucle ou appel à une fonction contenant une boucle, la fonction de temps du programme ci-dessus est :
n−1
T (n) = ∑ O(1) = O(n)
i=0
Exemple 3 :
Combien de comparaison dans la boucle suivante
Langage C Python
1 for(int i=0;i<n;i++){ // n+1 ?
2 for(j=0;j<m;j++){ // n*(m+1)
3 //quelques expressions d'ordre O(1) // n * m
4 }
5 }
La boucle externe (depend de i) est exécutée n + 1 fois
la boucle interne est exécutée m + 1, et nous savons que les instructions à l'intérieur d'une boucle sont exécutées n fois; la
boucle interne est donc exécutée n(m + 1)
Les instructions exécutées à l'intérieur de la boucle interne sont exécutées n ∗ m fois.
Donc, la complexité de ce programme est O(n ∗ m)
Si n = m la complexité devient O(n 2 )
Exemple 4 :
cet exemple est différent de l'exemple précédent car ici j dépend de i (j<i)
Langage C Python
1 for(int i=0;i<n;i++){ ?
2 for(j=0;j<i;j++){
3 printf("hello");
4 }
5 }
Pour comprendre clairement comment nous pouvons trouver la complexité du programme ci-dessus, je vais utiliser un tableau pour
tracer les itérations
la première colonne contenant les valeurs de i, la deuxième colonne contenant les valeurs de j et la troisième colonne contenant le
nombre de fois que Hello est affiché
i j nombre
0 0 0
1 0 1
2 0 2
1
... ... ...
n-1 0 n-1
1
2
...
n-2
Donc le temps total est :
T (n) = 0 + 1 + 2 + 3+. . . +n − 1
n−1
= ∑i
i=0
n ∗ n
=
2
2
= O(n )
Exemple 5 :
Langage C Python
1 p=0; ?
2 for(int i=0;p<n;i++){
3 printf("%d",i);
4 p=p+i;
5 }
Je vais tracer les valeurs de i et p dans un tableau et vous montrer comment calculer la complexité
Nous ne connaissons pas la dernière valeur de i, alors nommons la dernière valeur de i en tant que k
i p
1 0+1=1
2 1+2=3
3 1+2+3
4 1+2+3+4
... ...
k 1+2+3+...+k
Nous avons donc besoin de calculer la valeur de k
la boucle s'arrête lorsque p devient supérieur à n. donc on suppose que p>n
Puisque
p = 1 + 2 + 3 + 4 + 5+. . . +k
k ∗ (k + 1)
= > n
2
2
⇒ k > n
⇒ k > √n
Donc
T (n) = O(√n)
Exemple 6 :
Langage C Python
1 p=0;
2 for(int i=0;i<n;i*=2){
3 printf("%d",i);
4 }
Je vais utiliser la même méthode et tracer les valeurs de i dans un tableau
Itération i
0 1 2
0
1 2 2
1
Itération i
2 4 2
2
3 8 2
3
... ... ...
k 2
k
la boucle s'arrête lorsque i devient supérieur ou égale à n. donc on suppose que i ≥ n
Puisque i = 2
k
k k
2 ⩾ n ⇒ 2 = n ⇒ k = log 2 n
Donc
T (n) = O(log 2 n)
La complexité temporelle d'une boucle est considérée comme O(Log n) si la variable de boucle est divisée/multipliée par une
valeur constante.
Exemple 7 :
Langage C Python
1 for(int i=0;i<n;i++){ ?
2 printf("%d",i);
3 }
4 for(int j=0;j<n;j++){
5 printf("%d",i);
6 }
Comme vous pouvez le constater dans cet exemple, les deux boucles étant indépendantes, la complexité de ce programme est égale à la
somme de la complexité des deux boucles.
La première boucle est exécutée n fois
La deuxième boucle est exécutée n fois
donc
T (n) = n + n = 2n = O(n)
Exemple 8 :
Langage C Python
1 p=0
2 for(int i=0;i<n;i=i*2){
3 p++;
4 }
5 for(int j=0;j<p;j=j*2){
6 printf("%d",i);
7 }
Comme vous pouvez le voir, les deux boucles sont dépendantes et de la forme de l'exemple 6
La complexité de la première boucle est log 2 n
La complexité de la première boucle est log 2 p
Donc T (n) = O(log 2 p)
Puisque p = log 2 n
Alors
T (n) = O(log(log n))
Exemple 9 :
Langage C Python
1 for(int i=1;i<n;i++){ // n+1 ?
2 for(j=1;j< n; j=j*2){ // n(log n)
3 // instructions // n(log n)
4 }
5 }
La boucle externe est exécutée n + 1 fois
La boucle interne est exécutée n log n (le premier n fait référence au nombre de fois que les instructions à l'intérieur de la
boucle externe sont exécutées)
alors selon la règle maximale, ce temps de calcul est max(n, nlogn)
T (n) = O(n log n)
Conclusion
En général, si vous avez une boucle for, vous pouvez appliquer l'une des formules ci-dessous.
1 for(i=0 ; i < n ; i+=c)
2 for(i=n ; i > 0; i-=c)
⇒ O(n)
1 for(i=0 ; i < n ; i*=c)
2 for(i=n ; i> 1 ; i/=c)
⇒ O(log c n)
Boucle While
pour analyser les boucles while, on peut utiliser la même procédure que dans la boucle "for"
Exemple 1 :
Langage C Python
1 i=0;
2 while(i<n){
3 i++;
4 }
Comme vous pouvez le voir, "i" prend initialement 0 et après chaque itération est incrémenté de 1.
La complexité temporelle prise par cette boucle est donc identique à celle de l'exemple 2 dans la boucle "for".
T (n) = O(n)
Exemple 2 :
Langage C Python
1 a=1;
2 while(a<b){
3 a = a*2;
4 }
Comme vous pouvez le constater dans cet exemple, la variable de boucle est multipliée à chaque fois par 2. La complexité temporelle
prise par cette boucle est la même que celle de l'exemple 6 dans la boucle for.
T (n) = O(log 2 n)
Comment calculer la complexité temporelle des fonctions récursives?
La complexité temporelle d'une fonction récursive peut être écrite comme une relation de récurrence mathématique. Pour calculer la
complexité temporelle, il faut savoir résoudre les récurrences. Nous aborderons ensuite les techniques de résolution des récurrences.
See you in the next course :D
Partager ce cours avec tes amis :
⇐ Complexité asymptotique - notations
Rédigé par ESSADDOUKI Mostafa
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and
inspire.
Qui sommes-nous / Termes et conditions / Politique de confidentialité / Contact
Copyrights © 2020 - TechMentor Labs.
