Utiliser un compteur, un accumulateur, ou un curseur (le tryptique CAC)
Dans de nombreux cas, on doit :
- compter le nombre d’occurrence d'une condition, dans ce cas, on utilisera un compteur
- sommer (ou faire un produit) dans une boucle, dans ce cas, on utilisera un accumulateur
- mémoriser la position d'un élément particulier, dans ce cas, on utilisera un curseur
Un compteur en action
Les compteurs sont des variables qu'on incrémente quand on trouve un éléments correspondant à un critère. Parfois il n'y a pas vraiment de critère, on compte simplement tout les éléments ou toutes les occurrences, mais la notion de comptage est fréquente en algorithmique. Nous avons déjà vu des utilisations de compteurs.
Avant de coder cette fonction, écrit le pseudocode de l'algo au brouillon
quand tu as écrit ton pseudo code, demande à ton professeur de le valider puis
recopie le sur le document papier puis implémente le ci-dessous.
Ecrire une fonction qui prend en argument une liste de nombres et renvoi le nombre de multiples de 3 dans cette liste
📌 Utiliser la syntaxe ne portant pas sur les indices pour parcourir la liste
Complexité
L'algorithme contient une boucle sur les éléments de la liste lst.
- Avant la boucle on a 1 affection → 1 opération élémentaire
- La boucle est exécutée N fois (nb d’élément dans la liste) et dans cette boucle il y a : 1 opération (%), un test, une addition et une affectation. → 4*N opérations élémentaires
- Après la boucle il n'y a rien → 0 opération élémentaire
On a donc au total, 1+4N + 0 opérations élémentaires dans ce code.
<br>
4N+1 est une fonction linéaire, on dit qu'on a une complexité linéaire et on note O(N)
Pour appréhender cette complexité "proportionnelle à N" on va mesurer le temps mis par l'algorithme pour donner la réponse
on va mesurer le temps mis pour calculer la moyenne d'une liste de N nombres avec N=10 puis 100 puis 1000 etc … jusqu'à 1 million.
A chaque fois on multiplie N par 10 et on obtient un temps t (on à par exemple le t100 pour n=100, et le t1000 pour N=100 ) et on affichera t1000 / t100 pour voir le rapport entre le deux.
pour le 1er calcul on ne peux pas comparer au t précédent, on le divisera par 1.
On observe donc que lorsque le nombre N d'éléments de la liste est multiplié 10, le temps de calcul est multiplié aussi par un facteur du même ordre de grandeur. Nous observons donc encore bien ici une complexité linéaire.
Un accumulateur en action
Pour sommer ou multiplier (ou soustraire ou diviser) dans une boucle, on utilise une variable accumulateur. Nous avons déjà vu des utilisations d'accumulateurs.
Avant de coder cette fonction, écrit le pseudocode de l'algo au brouillon
quand tu as écrit ton pseudo code, demande à ton professeur de le valider puis
recopie le sur le document papier puis implémente le ci-dessous.
Complexité
L'algorithme contient une boucle sur les éléments de la liste lst.
- Avant la boucle on a 1 affection → 1 opération élémentaire
- La boucle est exécutée N fois (longueur de la liste) et dans cette boucle il y a une addition et une affectation. → 2*N opérations élémentaires
- Après la boucle il n'y a rien → 0 opération élémentaire
On a donc au total, 1+2N + 0 opérations élémentaires dans ce code.
<br>
2N+1 est une fonction linéaire, la complexité est linéaire soit O(N)
Comme pour les multiples de 3 précédemment évaluons la complexité en executant le programme ci-dessous.
On observe bien lorsque le nombre N d'éléments de la liste est multiplié 10, le temps de calcul est multiplié aussi par un facteur du même ordre de grandeur. Nous observons donc encore bien ici une complexité linéaire.
Un curseur en action
Les curseurs sont des variables qui retiennent la position (l'index) d'un élément présentant une caractéristique particulière dans une liste. Un bon exemple est la recherche de la position du max des éléments d'une liste.
Avant de coder cette fonction, écrit le pseudocode de l'algo au brouillon
quand tu as écrit ton pseudo code, demande à ton professeur de le valider puis
recopie le sur le document papier puis implémente le ci-dessous.
Complexité
L'algorithme contient une boucle sur les éléments de la liste lst de longueur N (en partant du 2ème)
- Avant la boucle on a 1 affection → 1 opération élémentaire
- La boucle est exécutée N-1 fois et dans cette boucle il y a une comparaison addition et une affectation. → 2(N-1) opérations élémentaires
- Après la boucle il n'y a rien → 0 opération élémentaire
il y a donc 1+2N-2 = 2N-1 opérations élémentaires
On a donc une complexité linéaire soit O(N)
Il existe une variante (qu'on retrouve généralement dans tous les algorithme utilisant un curseur) à l'algorithme que nous venons de voir.
Si, au lieu de l'indice de la valeur maxi, on cherche la valeur elle même, l'algorithme est légèrement différent.:
Écrivez le pseudo-code modifié pour satisfaire cette recherche, faites le valider par votre professeur, recopier le sur votre feuille puis implementer le ci-dessous.
