La complexité des algorithmes
i.khouja
Created on April 9, 2020
NSI - 1ere - Lycée Voltaire de Doha
More creations to inspire you
TALK ABOUT DYS TEACHER-TEACHER
Presentation
TALK ABOUT DYS WITH TEACHER
Presentation
ESSENTIAL OILS PRESENTATION
Presentation
ANCIENT EGYPT FOR KIDS PRESENTATION
Presentation
CIRQUE DU SOLEIL
Presentation
YURI GAGARIN IN DENMARK
Presentation
EIDIKO JEWELRY
Presentation
Transcript
La complexité des algorithmes
Numérique et Sciences informatiques - Classe de première
Avril 2020
Par Mme Imen KHOUJA
Index
Introduction
Définition
Comparaison des méthodes de tri
Rappel sur les méthodes de Tri
CALCUL SUR PYTHON
Rappel sur les méthodes de recherches
Calcul de complexitÉ
ActivitÉ 1
ActivitÉ 2
De quoi dÉpend la complexitÉ ?
Classe de complexitÉ
A retenir
application
Fonction time
quiz
fin de la sÉquence
Problème
Traitement
Solution 1
Solution 2
...
Solution n
1
Ecriture de l'algorithme
3
Implémentation
2
Exécution à la main
4
Test
VS
Tri Sélection
Tri Insertion
TRI SELECTION
1- Principe :
Le principe du tri par sélection est d'aller chercher le plus petit élément de la liste pour le mettre en premier, puis de repartir du second élément et d'aller chercher le plus petit pour le mettre en second, etc, jusqu'à l'avant dernier élément du tableau.
2- Algorithme :
Entrées : T [tableau] non trié
Sorties : T trié
Traitement :
Pour i de 1 à len(T)-1 faire
indice_min <-- i
Pour j de i+1 à len(T)-1 faire
Si T[indice_min]>T[j] alors
indice_min. <-- j
fin si
fin pour
Si indice_min != i alors
temp <-- T[indice_min]
T[indice_min] <-- T[i]
T[i] <-- temp
fin si
fin pour
3- Programme Python :
4- Lien vers le TP : Ici
Tri Insertion
1- Principe :
C'est le tri du joueur de cartes. On fait comme si les éléments à trier étaient donnés un par un, le premier élément constituant, à lui tout seul, une liste triée de longueur 1. On range ensuite le second élément pour constituer une liste triée de longueur 2, puis on range le troisième élément pour avoir une liste triée de longueur 3 et ainsi de suite...
Le principe du tri par insertion est donc d'insérer à la nième itération le nième élément à la bonne place.
2- Algorithme :
Entrées : T [Tableau] non trié
Sorties : T trié
Traitement :
Pour i de 2 à len(T) faire
temp <--T[i]
j <-- i
Tant que (temp<T[j-1]) ET (j>0) faire
T[j] <-- T[j-1]
j <-- j-1
fin tant que
T[j] <-- temp
fin pour
3- Programme en Python :
4- Lien du TP : Ici
Recherche dichotomique
1- Principe :
- La recherche dichotomique est une manière efficace et rapide de rechercher un élément dans une structure de données triée.
- L’idée consiste à réduire de moitié l’espace de recherche à chaque étape : on regarde la valeur du milieu et si ce n’est pas celle recherchée, on sait qu’il faut continuer de chercher dans la première moitié ou dans la seconde, ainsi :
- On détermine l’élément M au milieu du tableau,
- Si c’est la valeur recherchée, on s’arrête avec un succès,
- Si non, deux cas sont possibles :
* Si m est plus grand que la valeur recherchée, comme la tableau est trié, cela signifie qu’il suffit de continuer à chercher dans la première moitié du tableau,
* Sinon, il suffit de chercher dans la moitié droite. 4. on répète cela jusque avoir trouvé la valeur recherchée, ou bien avoir réduit l’intervalle de recherche à un intervalle vide, ce qui signifie que la valeur recherchée n’est pas présente.
2- Algorithme :
Entrées : T [tableau trié] , vr (Valeur à rechercher)
Sorties : res
Traitement :
d←1
f←len(T)
res ← faux
Tant que ( d <= f ) faire
m ←(d+f) div 2
Si T[m] > vr alors
f ← m-1
Si non
Si T[m] < vr alors
d ← m+1
Si non
res ← vrai
retourner (res)
fin si
fin si
fin tant que
retourner (res)
3- Programme Python :
4- Lien vers TP : Ici
Recherche séquentielle
1- Principe :
Le recherche séquentielle ou recherche linéaire est un algorithme pour trouver une valeur dans une liste. Elle consiste simplement à parcourir les éléments de la liste les uns après les autres, jusqu'à ce que l'élément soit trouvé, ou que toutes les cases aient été lues. Elle est aussi appelée recherche par balayage.
2- Algorithme :
Entrées : T [tableau] , vr (Valeur à rechercher)
Sorties : res
Traitement :
i <-- 1
Tant que (T[i] ≠ VR) ET( i < len(T)) faire
i <-- i+1
Fin tant que
Si T[i] = VR alors
res <-- vrai
Si non
res <-- faux
Fin si
retourner (res)
3- Programme Python :
4- Lien vers le TP : Ici
Simulation des différentes méthodes de tri
1- Définition de la complexité
Complexité temporelle
Complexité Spatiale
La complexité (temporelle) d’un algorithme est le temps nécessaire à résoudre un problème mathématique P,
En informatique théorique, ce temps est mesurée par le nombre d'opérations élémentaires (affectations, comparaisons, opérations arithmétiques) effectuées par un algorithme.
2- Calcul du temps d’exécution avec Python
Renvoyer
Combien de temps la fonction a-t-elle mis à s’exécuter ?
Modifications à apporter au programme principal
#-------------programme principal--------------------
import time
import random
#N= saisie_taille_tab()
#tab=remplir(N)
tab = [random.randint(0,20) for i in range(10)]
print(tab)
t1=tab
start_time1 = time.time()
tri_insertion(t1)
end_time1 = time.time()
print("Temps d execution de la fonction tri_insertion : ", end_time1 - start_time1, " secondes.")
start_time2 = time.time()
tri_selection(tab)
end_time2 = time.time()
print("Temps d execution de la fonction tri_sélection : ", end_time2 - start_time2, " secondes.")
print(tab)
Activité 1
Sur votre TP python, calculez le temps d’exécution de chaque fonction de tri étudiée en utilisant la fonction time().
import random
#N= saisie_taille_tab()
#tab=remplir(N)
tab = [random.randint(0,20) for i in range(100)]
print(tab)
Correction de l'activité 1
Résultats en secondes(x 100 000)
5
20
100
1000
4.0
5.14
32.68
3115.84
3.45
4.50
34.52
3702.52
Lorem Ipsum
Lorem Ipsum
Lorem Ipsum
Lorem Ipsum
Tri Sélection
Tri Insertion
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
Activité 2
Calculez le temps d’exécution des fonctions recherche séquentielle et dichotomique en utilisant la fonction time() pour une liste de taille 10 puis 100 en testant les scénarios suivants :
- L'élément à rechercher se trouve au début de la liste.
Correction de l'activité 2
Résultats en secondes (x 100 000)
CAs 1
Cas 2
Cas 3
?
?
3115.84
?
?
?
Lorem Ipsum
Lorem Ipsum
Lorem Ipsum
Lorem Ipsum
Séquentielle
Dichotomique
Séquentielle
Dichotomique
?
?
?
?
?
?
?
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
Attention, le nombre de secondes a été multiplie. par 100 000 pour plus de lisibilité.
3- De quoi dépend la complexité ?
La notation O = Ordre de grandeur asymptotique
Complexité
Taille des données
Conditions de départ
Meilleur cas
Cas moyen
Pire cas
Si T est le nombre d'opérations élémentaires.
Si T(n)=4 alors la complexité est en O(1)
Si T(n)=3n+2 alors la complexité est en O(n)
Si T = (2*N2 + 3*N + 5) alors la complexité est en O(n2) (n au carré)
4- Classes de complexité des algorithmes
Complexité logarithmique
5- Calcul de la complexité
Algorithmes sans structures conditionnellese
ExEmple : Une fonction de conversion
3 affectations
5 opérations arithmétiques
T(n) = 8
O(1)
Complexité constante
Algorithmes avec structures conditionnelles
ExEmple : Un calcul de puissance
1 opération arithmétique +
T(n) = 3
O(1)
Algorithmes avec structures itératives
ExEmple : Calcul de la somme des n premiers entiers
1 affectation
1 affectation, 1 addition, 1 comparaison
T(n) = 5N +1
O(N)
1 affectation, 1 addition
5 opérations élémentaires x N fois = 5N
Complexité linéaire
A retenir : Plan d’étude de la complexité d’un algorithme
Il faut définir l’entier n représentant la taille des arguments.
1
On prendra par exemple :
- n = n si l’argument est un entier n
- n = la longueur de L si l’argument est un tableau de longueur n
2
Il faut définir l’unité de coˆut.
On prendra par exemple :
- le nombre de multiplications si la multiplication est l’opération dominante
- le nombre d’itérations si le nombre d’opérations et de tests sont constants par itération
6- Applications
Calculez la complexité de chacune de ces fonctions.
Deux affections (i et somme), deux additions (i et somme) et une comparaison.
On a d'autre part une affectation, lors de l'initialisation de la variable somme.
Ainsi T(n)=5n+1 ---> O(n)=n ----> Complexité linéaire
Cet algorithme ne comporte pas de structures de contrôle, il est juste constitué de trois opérations arithmétiques.
On a donc T(n)=3 ----> O(n)=1 ----> Complexité constante.
START
QUIZ
Déterminez la complexité de chaque fonction proposée.
2
3
1
A
Dans cette fonction, on exécute n-1 le test de comparaison. La complexité est donc n-1 = O(n).
B
C
O(n)
O(n2)
O(1)
fonction 1
Fonction en C++
3
1
A
B
C
Pire des cas : n fois la boucle --> T ( n) = 1 + n + 1 = O ( n )
O ( n2 ) (n au carré)
O ( 1 )
O ( n )
2
fonction 2
1
A
la boucle "pour i de 1 jusquà n-1 faire" s'exécute n-1 fois (donc une somme de n-1 termes) et qu'à chaque fois la boucle "pour j de i+1 jusquà n faire" exécute (n-(i+1)+1 fois la comparaison "si Tab[ j ] < Tab[ m ] alors".
La complexité en nombre de comparaison est égale à la somme des n-1 termes suivants (i = 1, ...i = n-1)
La complexité en nombre de comparaison est de de l'ordre de n², que l'on écrit O(n²).
B
C
O ( n2 ) (n au carré)
O ( 1 )
O ( n )
2
3
fonction 3
TRI SELECTION
3
2
1
4
merci !