Calculer la complexité temporelle des boucles
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
a = 2+3 b = 2 c = a+b
la complexité des instructions ci-dessus est \(O(1)\)
Structure conditionnelle SI
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 = 2n + 1\), alors le calcul total est :
$$ \begin{equation} \label{eq1} \begin{split} Calcul \: total & = max(tA, tB) \\ & = max(O(n^3), O(2n+1)) \\ & = O(n^3) \end{split} \end{equation} $$
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,
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)\).
// Ici c est une constante for(int i=0;i<c;i++){ // quelques expressions d'ordre O(1) } // exemple : for(int i=0;i<50;i++){ // quelques expressions d'ordre O(1) }
# Ici c est une constante for i in range(c): # instructions # exemple : for i in range(50): print(i)
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)\)
for(int i=0;i<n;i+=c){ // O(n+1) // quelques expressions d'ordre O(1) // O(n) }
for i in range(n): # O(n+1) # quelques expressions d'ordre O(1) # O(n)
Si nous n'avons aucune boucle ou appel à une fonction contenant une boucle, la fonction de temps du programme ci-dessus est : $$T(n)= \sum_{i=0}^{n-1} O(1) = O(n)$$
Exemple 3 :
Combien de comparaison dans la boucle suivante
for(int i=0;i<n;i++){ // n+1 for(j=0;j<m;j++){ // n*(m+1) //quelques expressions d'ordre O(1) // n * m } }
for i in range(n): # n+1 for j in range(m): # n*(m+1) # quelques expressions d'ordre O(1) # n*m
- 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)
for(int i=0;i<n;i++){ for(j=0;j<i;j++){ printf("hello"); } }
for i in range(n): for j in range(i): print("Hello")
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 1 | 2 |
... | ... | ... |
n-1 | 0 1 2 ... n-2 | n-1 |
Donc le temps total est : $$ \begin{equation} \label{eq2} \begin{split} T(n) & = 0 + 1 + 2 + 3 + ...+ n-1 \\ & = \sum_{i=0}^{n-1} i \\ & = \frac{n*n}{2} \\ & = O(n^2) \end{split} \end{equation} $$
Exemple 5 :
p=0; for(int i=0;p<n;i++){ printf("%d",i); p=p+i; }
p=0 i=1 while p < n : print(i) p = p+i p += 1
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 $$ \begin{equation} \label{eq3} \begin{split} p & = 1+2+3+4+5+...+k \\ & = \frac{k*(k+1)}{2} > n \\ & \Rightarrow k^2 > n \\ & \Rightarrow k > \sqrt{n} \end{split} \end{equation} $$
Donc $$ T(n) = O(\sqrt{n}) $$
Exemple 6 :
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\) |
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\)
\(2^k \geqslant n\:\:\:\: \Rightarrow\: 2^k=n\:\:\:\: \Rightarrow k=log_2{n} \)
Donc $$T(n) = O(log_2{n}) $$
Exemple 7 :
for(int i=0;i<n;i++){ printf("%d",i); } for(int j=0;j<n;j++){ printf("%d",i); }
for i in range(n): print(i) for j in range(n): print(i)
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 :
p=0 for(int i=0;i<n;i=i*2){ p++; } for(int j=0;j<p;j=j*2){ printf("%d",i); }
p=0 i=1 while i< n: p++ i *= 2 j=1 while j< p: j *= 2
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 :
for(int i=1;i<n;i++){ // n+1 for(j=1;j< n; j=j*2){ // n(log n) // instructions // n(log n) } }
for i in range(n): # n+1 j=1 # n while j< n: # n(log n) j *= 2 # n(log n)
- 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.
for(i=0 ; i < n ; i+=c) for(i=n ; i > 0; i-=c)
\(\Rightarrow \:\: O(n)\)for(i=0 ; i < n ; i*=c) for(i=n ; i> 1 ; i/=c)
\(\Rightarrow \:\: 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 :
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 :
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