complexite

C1-ALGO-04 : Caractéristiques des algorithmes#

Dans ce cours, nous utilisons des exemples introductifs des deux grandes classes d’algorithmes classiques : recherche et tri pour dériver les concepts de complexité, de convergence et de condition d’arrêt

Objectifs#

  • les élèves abordent les principales caractéristiques des algorithmes avec des exemples simples:

    • convergence

    • condition d’arrêt

    • complexité temporelle (et la notation “Big O”)

    • complexité spatiale

    • adéquation d’un algorithme avec le problème à résoudre

Exemple introductif (algorithme de recherche) : trouver un nombre entre 1 et 128#

  • liste triée

  • comment trouver un nombre ?

On joue ?#

Dichotomie#

dicho

Heuristique ?#

Une heuristique est un élément qui permet d’aider à la découverte. De manière générale, il s’agit de la partie de la science qui a pour objet les procédures de recherche et de découverte

Si on a une connaissance en amont, on peut l’utiliser pour accélérer la recherche. Par exemple :

  • Le nombre à trouver est le plus grand

  • le nombre à trouver se trouve entre 65 et 78

Remarques#

  • La liste doit être triée

  • Deux algorithmes différents amènent au même résultat mais avec des temps pour trouver la solution différents

  • Il s’agit-là d’une première approche de la complexité d’un algorithme

Ordres de grandeur#

Tri

temps

Méthode naïve

linéaire : si on double la taille de la liste, alors on double le temps

Dichotomie

logarithmique : à chaque étape, on divise par deux le nombre d’élèments

Recherche du plus grand nombre dans une liste non triée#

Que se passe-t-il si la liste n’est pas triée ?

  • doit-on la trier ? Comment la trier ?

  • autre méthode ?

Second exemple introductif : Algorithmes de tri#

Soit une liste non triée, comment la trier pour effectuer dans un second temps une recherche sur celle-ci ?

6609;9449;3597;1345;1349;5898;8298;3427;4014;2967;4167;2244;8035; 7232;4382;5799;2977;5882;2534;2052;78;7679;1258;8717;3227;5960;315; 1334;7320;2659;5503;7275;4699;9926;4621;120;8939;3876;4322;3671;611; 5947;6181;30;7634;5884;2208;7626;5954;5949;2543;5388;457;221;6649;3129; 8879;8022;3065;1072;8738;9586;9171;4423;3921;1774;2140;9150;5636;1207; 3082;7159;7897;9707;1758;524;7789;81121;1281;1373;1131;3883;8550;5890; 3569;3301;9334 ;934;9488;9014;9939;6133

Plus grand nombre dans la liste non-triée ?#

Il est obligatoire de parcourir l’ensemble des éléments de la liste et de les comparer. On utilise deux variables : l’élément à comparer et le plus grand au moment de la comparaison

Plus grand nombre dans la liste triée ?#

Il suffit de prendre le dernier, quelque soit la taille de la liste.

Trade-off : trier ou ne pas trier, telle est la question#

Est-il possible de trouver un compromis entre la recherche dans une liste non-triée ou le tri puis la recherche dans la liste triée en termes de temps de calcul et de quantité de mémoire nécessaires ?

Convergence algorithmique#

Un algorithme devrait toujours arriver à une solution. On dit alors qu’il converge lorsqu’une métrique spécifique ne varie plus.

Définitions : Complexité en temps et en espace d’un algorithme#

La complexité d’un algorithme représente la quantité de ressources nécessaires pour exécuter l’ensemble des instructions en fonction de l’entrée fournie (en fonction de la TAILLE du problème). Cette complexité se donne en temps ou en espace (quantité de mémoire nécessaire).

Par convention, on exprime la taille du problème avec la lettre n et on donne l’ordre de grandeur asymptotique de la fonction.

Complexité temporelle#

La complexité temporelle d’un algorithme est une fonction de la taille de l’entrée et qui exprime le temps d’exécution d’un algorithme. Exemple : si on a un élément à rechercher dans une liste de 1000, combien de temps cela prendra pour une liste de 2000.

Complexité spatiale#

La complexité spatiale d’un algorithme est une fonction de la taille de l’entrée et qui exprime la quantité de mémoire nécessaire à l’exécution d’un algorithme.

Meilleur et pire des cas : ordre de grandeur asymptotique#

Le comportement de la complexité (temporelle et spatiale) peut s’analyser dans le pire des cas.

L’asymptote est une courbe qui approche une autre sans jamais l’atteindre (du grec a exclusif et symptote rencontre).

asymptote

L’ordre de grandeur asymptotique de la complexité d’un algorithme est donc le pire des cas et celui qui ne sera jamais atteint.

Classe de complexité des algorithmes#

L’ordre de grandeur asymptotique s’écrit avec la notation dites Grand O (Big O en anglais).

\(\mathcal{O}{()}\)

classe

\(\mathcal{O}(1)\)

constante

\(\mathcal{log(n)}(1)\)

logarithmique

\(\mathcal{O}(n)\)

linéaire

\(\mathcal{O}(n \cdot log(n))\)

quasi-linéaire

\(\mathcal{O}(n^2)\)

quadratique

\(\mathcal{O}(n^3)\)

cubique

\(\mathcal{O}(2^n)\)

exponentielle

\(\mathcal{O}(n!)\)

factorielle

Ressources supplémentaires#

from IPython.display import YouTubeVideo

YouTubeVideo('kPRA0W1kECg', width=960, height=540)