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

Ecriture de l'algorithme

Implémentation

Exécution à la main

Test

Tri Sélection

Tri Insertion

Plus d'infos

PLUS D'INFOS

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 t ri par insertion est donc d'insérer à la n_ième itération le n_iè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

Recherche séquentielle

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 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

Cas 1

Cas 2

Cas 3

Cas 4

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

time()

Renvoyer

courant en secondes

Combien de temps la fonction a-t-elle mis à s’exécuter ?

Info

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().

Effectuez le test pour une liste de taille : 5, 20, 100 et 1000

Correction

Info

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)

100

1000

4.0

5.14

32.68

3115.84

3.45

4.50

34.52

3702.52

Lorem Ipsum

Tri Sélection

Tri Insertion

Python

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.

- L'élément à rechercher se trouve au milieu de la liste.

- L'élément à rechercher ne se trouve pas dans la liste.

Correction

Correction de l'activité 2

Résultats en secondes (x 100 000)

CAs 1

Cas 2

Cas 3

3115.84

Lorem Ipsum

Séquentielle

taille = 10

Dichotomique

taille = 10

Séquentielle

taille = 100

Dichotomique

taille = 100

Python

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.

T= N ou T= 3N+5 ou T=N/2

La complexité est en O(N)

Info

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

Complexité linéaire

Complexité quadratique

Complexité polynomiale

Complexité exponentielle

Complexité hyperexponentielle

Info

5- Calcul de la complexité

Info

Algorithmes sans structures conditionelles

Algorithmes avec structures conditionelles

Algorithmes avec structures itératives

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 +

1 comparaison

1 affectation pour chaque alternative

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.

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

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

- le nombre de comparaisons si aucune autre opération importante n’est effectuée

6- Applications

Calculez la complexité de chacune de ces fonctions.

Solution

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.

Dans cette fonction, on exécute n-1 le test de comparaison. La complexité est donc n-1 = O(n).

O(n)

O(n2)

O(1)

fonction 1

Fonction en C++

Fonction en Python

Pire des cas : n fois la boucle --> T ( n) = 1 + n + 1 = O ( n )

O ( n2 ) (n au carré)

O ( 1 )

O ( n )

fonction 2

RECHERCHE SEQUENTIELLE

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²).

O ( n2 ) (n au carré)

O ( 1 )

O ( n )

fonction 3

TRI SELECTION

merci !

La complexité des algorithmes

More creations to inspire you

TALK ABOUT DYS TEACHER-TEACHER

TALK ABOUT DYS WITH TEACHER

ESSENTIAL OILS PRESENTATION

ANCIENT EGYPT FOR KIDS PRESENTATION

CIRQUE DU SOLEIL

YURI GAGARIN IN DENMARK

EIDIKO JEWELRY

Transcript