La complexité des algorithmes

Par Mme Imen KHOUJA

Numérique et Sciences informatiques - Classe de première Avril 2020

La complexité des algorithmes

fin de la sÉquence

quiz

Fonction time

application

A retenir

Classe de complexitÉ

De quoi dÉpend la complexitÉ ?

ActivitÉ 2

ActivitÉ 1

Calcul de complexitÉ

Rappel sur les méthodes de recherches

CALCUL SUR PYTHON

Rappel sur les méthodes de Tri

Comparaison des méthodes de tri

Définition

Introduction

Index

Test

Exécution à la main

Implémentation

Ecriture de l'algorithme

Solution 1 Solution 2 ... Solution n

Traitement

Problème

PLUS D'INFOS

Plus d'infos

Tri Insertion

Tri Sélection

VS

Recherche séquentielle

Recherche dichotomique

Cas 4

Cas 3

Cas 2

Cas 1

Simulation des différentes méthodes de tri

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.

Complexité Spatiale

Complexité temporelle

1- Définition de la complexité

Renvoyer courant en secondes

time()

2- Calcul du temps d’exécution avec Python

Info

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

Info

Correction

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

Activité 1

Tri Insertion

Tri Sélection

Lorem Ipsum

Lorem Ipsum

Lorem Ipsum

Lorem Ipsum

3702.52

34.52

4.50

3.45

3115.84

32.68

5.14

4.0

1000

100

20

Résultats en secondes(x 100 000)

Correction de l'activité 1

Correction

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.

Activité 2

Dichotomiquetaille = 100

Séquentielletaille = 100

Dichotomiquetaille = 10

Séquentielletaille = 10

Lorem Ipsum

Lorem Ipsum

Lorem Ipsum

Lorem Ipsum

3115.84

Cas 3

Cas 2

CAs 1

Résultats en secondes (x 100 000)

Correction de l'activité 2

Info

Si T est le nombre d'opérations élémentaires.T= N ou T= 3N+5 ou T=N/2La complexité est en O(N)

Pire cas

Cas moyen

Meilleur cas

Conditions de départ

Taille des données N

Complexité

La notation O = Ordre de grandeur asymptotique

3- De quoi dépend la complexité ?

Info

Complexité logarithmique Complexité linéaire Complexité quadratique Complexité polynomiale Complexité exponentielle Complexité hyperexponentielle

4- Classes de complexité des algorithmes

Algorithmes avec structures itératives

Algorithmes avec structures conditionelles

Algorithmes sans structures conditionelles

Info

Info

Info

5- Calcul de la complexité

Complexité constante

O(1)

T(n) = 8

5 opérations arithmétiques

3 affectations

ExEmple : Une fonction de conversion

Algorithmes sans structures conditionnellese

O(1)

T(n) = 3

+1 affectation pour chaque alternative

1 opération arithmétique + 1 comparaison

ExEmple : Un calcul de puissance

Algorithmes avec structures conditionnelles

Complexité linéaire

5 opérations élémentaires x N fois = 5N

1 affectation, 1 addition

O(N)

T(n) = 5N +1

1 affectation, 1 addition, 1 comparaison

1 affectation

ExEmple : Calcul de la somme des n premiers entiers

Algorithmes avec structures itératives

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

Il faut définir l’unité de coˆut.

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’entier n représentant la taille des arguments.

A retenir : Plan d’étude de la complexité d’un algorithme

Solution

Solution

Calculez la complexité de chacune de ces fonctions.

6- Applications

Déterminez la complexité de chaque fonction proposée.

QUIZ

START

fonction 1

O(1)

O(n2)

O(n)

fonction 2

O ( n )

O ( 1 )

O ( n2 ) (n au carré)

fonction 3

O ( n )

O ( 1 )

O ( n2 ) (n au carré)

merci !