Langage Python

Complexité algorithmique

Quand on tente de résoudre un problème, la question se posesouvent du choix d'un algorithme. Quels critères peuvent guider ce choix ? Deuxbesoins contradictoires sont fréquemment en présence : l'algorithme doit :

1.    Etre simple à comprendre, à mettre en œuvre, àmettre au point.

2.    Mettre intelligemment à contribution desressources de l'ordinateur et, plus précisément, il doit s'exécuter le plus rapidement possible.

Si un algorithme ne doit servir qu'un petit nombre de fois, le premier critère est le plus important. Par contre, s'il doit être employé souvent, le temps d'exécution risque d'être un facteur plus déterminant que le temps passé à l'écriture.

L’étude de la complexité des algorithmes a pour objectif l’estimation du coût d’un algorithme. Cette mesure permet donc la comparaison de deux algorithmes sans avoir à les programmer.

Si l’on prend en compte pour l’estimation de la complexité les ressources de la machine telles que la fréquence d’horloge, le nombre de processeurs, le temps d’accès disque etc., on se rend compte immédiatement de la complication voire l’impossibilité d’une telle tâche. Pour cela, on se contente souvent d’estimer la relation entre la taille des données et le temps d’exécution, et ceci indépendamment de l’architecture utilisée.

Il s’agit d’un modèle simplifié qui tient compte des ressources technologiques ainsi que leurs coûts associés. 

Plan:

I.      Introduction

1.     Méthode empirique

2.     Méthode mathématique

II.     Complexité asymptotique

1.     Notation O (grand o)

2.     Quelques propriétés de la notation O

III.        Différentes formes de complexité

1.     Complexité dans le pire des cas (Worst case)

2.     Complexité dans le meilleur des cas (Best case)

3.     Complexité en moyenne (Average case)

4.     Illustration : cas du tri par insertion

4.1.      Problématique du tri

4.2.      Principe du tri par insertion

4.3.      Algorithme

4.4.      Complexité

4.4.1.       Complexité au meilleur 

4.4.2.       Complexité au pire

4.4.3.       Complexité en moyenne

5.     Classes de complexité

IV.        La Récursivité, Souplesse et Complexité

1.     Récursivité

1.1.      Définition

1.2.      Récursivité simple

1.3.      Récursivité multiple

1.4.      Récursivité mutuelle

1.5.      Récursivité imbriquée

1.6.      Principe et dangers de la récursivité

1.6.1.       Principe et intérêt

1.6.2.       Difficultés 

1.6.3.       Importance de l’ordre des appels récursifs

2.     Dérécursivation

V.     Diviser pour régner

1.     Principe

2.     Analyse des algorithmes « diviser pour régner »

VI.        Résolution des récurrences

1.     Équations de récurrence linéaires

2.     Résolution des récurrences « diviser pour régner »

2.1.      Théorème 1 (Résolution des récurrences « diviser pour régner »)

2.2.      Exemples

2.2.1.       La multiplication de matrices

2.2.2.       Exemple-2

3.     Autres récurrences 

4.     Pourquoi estimer la complexité d’un algorithme ?

Télécharger le cours

Partager ce cours avec tes amis :
 
Rédigé par Mostafa Sedoki
Professeur d'Informatique dans les CPGE

Cours Similaires :