La complexité des algorithmes

La complexité des algorithmes

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

Par Mme Imen KHOUJA

Index

Rappel sur les méthodes de recherches

Introduction

Comparaison des méthodes de tri

Rappel sur les méthodes de Tri

Définition

Fonction time

CALCUL SUR PYTHON

ActivitÉ 1

De quoi dÉpend la complexitÉ ?

ActivitÉ 2

Classe de complexitÉ

Calcul de complexitÉ

application

A retenir

fin de la sÉquence

quiz

Problème

Implémentation

Ecriture de l'algorithme

Test

Exécution à la main

Solution 1 Solution 2 ... Solution n

Traitement

VS

Tri Insertion

Tri Sélection

PLUS D'INFOS

Plus d'infos

Recherche dichotomique

Recherche séquentielle

Simulation des différentes méthodes de tri

Cas 1

Cas 2

Cas 3

Cas 4

1- Définition de la complexité

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

Complexité Spatiale

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

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

Info

Correction

Résultats en secondes(x 100 000)

20

1000

100

Tri Sélection

5.14

3115.84

4.0

34.52

Tri Insertion

3.45

3702.52

4.50

32.68

Lorem Ipsum

Lorem Ipsum

Lorem Ipsum

Lorem Ipsum

Correction de l'activité 1

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

Résultats en secondes (x 100 000)

CAs 1

Cas 2

Cas 3

Séquentielletaille = 10

3115.84

Séquentielletaille = 100

Dichotomiquetaille = 10

Lorem Ipsum

Lorem Ipsum

Lorem Ipsum

Lorem Ipsum

Dichotomiquetaille = 100

Correction de l'activité 2

3- De quoi dépend la complexité ?

La notation O = Ordre de grandeur asymptotique

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)

Taille des données N

Conditions de départ

Complexité

Meilleur cas

Cas moyen

Pire cas

Info

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é

Algorithmes avec structures conditionelles

Algorithmes sans structures conditionelles

Algorithmes avec structures itératives

Info

Info

Info

ExEmple : Une fonction de conversion

3 affectations

5 opérations arithmétiques

T(n) = 8

O(1)

Complexité constante

Algorithmes sans structures conditionnellese

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 conditionnelles

ExEmple : Calcul de la somme des n premiers entiers

1 affectation

1 affectation, 1 addition, 1 comparaison

1 affectation, 1 addition

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

T(n) = 5N +1

Complexité linéaire

O(N)

Algorithmes avec structures itératives

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

Solution

QUIZ

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

START

fonction 1

O(n)

O(n2)

O(1)

fonction 2

O ( n2 ) (n au carré)

O ( 1 )

O ( n )

fonction 3

O ( n2 ) (n au carré)

O ( 1 )

O ( n )

merci !