Diaporama n°5¶

Algorithmique - Notions fondamentales¶

I. Généralités¶

II. Terminaison¶

III. Correction¶

IV. Complexité d'un algorithme¶

Pour une entrée quelconque,

  • Combien d'opérations mon algorithme va-t-il réaliser ? Complexité temporelle

  • Combien d'espace mémoire mon algorithme va-t-il utiliser ? Complexité spatiale

NB : ceci dépend :

  • de l'entrée elle-même,

  • de la machine sur laquelle s'exécute l'algorithme : représentation des données manipulées, implémentation des opérations, vitesse de calcul ...

Il y a beaucoup trop de paramètres à prendre en compte ...

on doit faire un certain nombre d'approximations ...

Approximations¶

  • On ne tient pas compte de toutes les entrées possibles, mais souvent de leur "taille"

  • On ne tient pas compte de la machine sur laquelle s'exécute le programme

    • Pour doubler la vitesse d'exécution, il suffit d'utiliser un machine deux fois plus rapide ... ce qui est sans lien avec l'efficacité intrinsèque de l'algorithme (ce qui nous intéresse ici).

  • On considère que toutes les opérations de base ont un coût unitaire :

    • addition, multiplication ... de deux entiers ou flottants

    • comparaison de deux entiers ou deux flottants

    • affectation, accès dans une liste ou chaîne de caractères

Attention : un appel à une fonction n'a pas forcément un coût unitaire :

  • min(L) : valeur minimale dans une liste : Quel coût ?
  • min(L) : valeur minimale dans une liste :
    • Il faut bien parcourir tous les éléments de la liste pour trouver la plus petite valeur donc ...
  • coût proportionnel à la longueur de la liste
  • L.copy() copie de liste : Quel coût ?
  • L.copy() copie de liste :
    • Il faut obtenir une nouvelle zone mémoire, et y copier les éléments de la liste donc ...
  • coût proportionnel à la longueur de la liste
  • L1 == L2 égalité de deux listes : Quel coût ?

  • L1 == L2 égalité de deux listes :

    • coût constant si les deux listes sont de longueur différentes

    • coût constant si les deux listes diffèrent sur leur premier élément

    • coût proportionnel à la longueur des deux listes si les listes deux listes sont égales (cas le plus coûteux : pire des cas)

  • L1+L2 : concaténation de deux listes : Quel coût ?
  • L1+L2 : concaténation de deux listes :
    • on crée une nouvelle liste, et on y copie les éléments des deux listes (cf PythonTutor), donc ...
  • coût proportionnel à la longueur des deux listes

Cours - définitions¶

Exemple : Recherche séquentielle dans une liste de longueur n¶

In [1]:
def recherche(L:[int],v:int) -> bool:
    """ renvoie True si v est dans la liste L, False sinon """
    for i in range(len(L)):
        if L[i] == v:
            return True
    return False

Dans le meilleur des cas ? (en fonction de $n$) :

  • v est le premier élément de la liste : 1 comparaison (la liste vide est un cas particulier : n=0)

Dans le pire des cas ? (en fonction de $n$) :

  • v n'est pas dans la liste : n comparaisons

En moyenne ? (en fonction de $n$ ?):

  • n/2 comparaisons ??? Pas si simple ... cf exercices

Cours - complexité asymptotique¶

On privilégie bien sûr les algorithmes de faible complexité lorsque c'est possible.

Passage à l'échelle : lorsqu'on double la valeur de $n$, pour un algorithme en :

  • $\mathcal{O}(1)$ : le coût ...
  • $\mathcal{O}(\log_2(n))$ : le coût ...
  • $\mathcal{O}(\sqrt{n})$ : le coût ...
  • $\mathcal{O}(n)$ : le coût ...
  • $\mathcal{O}(n^2)$ : le coût ...
  • $\mathcal{O}(n^k)$ : le coût ...
  • $\mathcal{O}(2^n)$ : le coût ...

Passage à l'échelle : lorsqu'on double la valeur de $n$, pour un algorithme en :

  • $\mathcal{O}(1)$ : le coût ne varie pas (car indépendant de $n$)
  • $\mathcal{O}(\log_2(n))$ : le coût est augmenté d'une constante (car $\log_2(2n)$ = $1+\log_2(n)$)
  • $\mathcal{O}(\sqrt{n})$ : le coût est multiplié par $\sqrt{2}$ (car $\sqrt{2n}$ = $\sqrt{2}\times \sqrt{n}$)
  • $\mathcal{O}(n)$ : le coût est multiplié par 2 (car $2n = 2 \times n$)
  • $\mathcal{O}(n^2)$ : le coût est multiplié par 4 (car $(2n)^2 = 4 \times n^2$)
  • $\mathcal{O}(n^k)$ : le coût est multiplié par $2^k$ (car $(2n)^k = 2^k \times n^k$)
  • $\mathcal{O}(2^n)$ : le coût est mis au carré (car $2^{2n} = (2^n)^2$)

Complexité : quelle utilité ?¶

Estimation du temps d'exécution

Supposons que l'on dispose d'une machine qui réalise $10^8$ opérations par seconde.

Durée d'exécution en fonction de $n$ et de la complexité de l'algorithme

Complexité n=10 n=20 n=50 n=1000 n=1000000
$\mathcal{O}(1)$ 10ns 10ns 10ns 10ns 10ns
$\mathcal{O}(\log(n))$ 30ns 40ns 60ns 100ns 200ns
$\mathcal{O}(n)$ 100ns 200ns 500ns 10µs 10ms
$\mathcal{O}(n\log n)$ 300ns 1µs 3µs 1ms 200ms
$\mathcal{O}(n^2)$ 1µs 4µs 25µs 10ms 3h
$\mathcal{O}(2^n)$ 10µs 10ms 130j $10^{14}$ ans ...
$\mathcal{O}(n!)$ 36ms 761ans $10^{49}$ ans ... ..

NB : âge de l'univers : $10^{10}$ ans

Exemple : problème du "voyageur de commerce"¶

Un étudiant souhaite faire le tour des $n=27$ capitales européennes. Soucieux de minimiser son bilan carbone, il veut que son trajet soit le plus court possible.

image.png

Algorithme "naïf" :¶

"on énumère les 27! permutations possibles, en conservant celle qui donne le plus court chemin" (complexité en $\mathcal{O}(n!)$)

En traitant 10⁸ permutations par seconde (machine actuelle) ...

il faudra 3000 milliards d'années pour obtenir le résultats...

Pour n grand, seuls les algorithmes de complexité polynomiale (ou inférieure) sont utilisables en pratique¶

Cours - fin¶

Quelques algorithmes classiques et complexité associées¶

Algorithmes en $\mathcal{O}(1)$ : nombre borné d'opérations

  • échange de contenu de deux variables

Algorithmes en $\mathcal{O}(n)$ : sur une séquence de longueur $n$

  • Somme des valeurs

  • Compter le nombre d'occurrences

  • Recherche séquentielle d'un élément

  • Recherche du minimum et toutes les variantes

    • recherche du maximum, du minimum et du maximum, des positions des maximums, des 2 plus grandes valeurs ...

Autres algorithmes classiques :

  • Algorithmes de tri (cf cours à venir) : $\mathcal{O}(n\log_2(n))$ ou $\mathcal{O}(n^2)$

  • Recherche dichotomique dans une liste triée (cf cours à venir) : $\mathcal{O}(\log_2(n))$

La complexité spatiale¶

A priori ... on dispose de beaucoup de "mémoire"

Ordres de grandeur :

  • 1 caractère : 1 octet (8bits)
  • 1 page : 3000 caractères (3ko)
  • 1 livre : 300 pages (900ko $\simeq$ 1Mo)
  • Une belle bibliothèque personnelle : 1000 livres (1Go)
  • la Bibliothèque Nationale : 10 millions de livres (10 To)

image-5.png

image-2.png

Attention toutefois ... :

  • allouer/libérer de la mémoire prend du temps

  • la mémoire est organisée de façon hiérarchique

image.png

  • plus on doit aller chercher "profond" dans la mémoire, plus cela prend de temps ...