Complexité algorithmique

Sommaire

Index

Introduction

Problématique

Parmi plusieurs algorithmes (programmes) résolvant le même problème, comment définir lequel est le plus efficace.

Exemple

Deux personnes proposent deux programmes différents.

Ces deux programmes résolvent le même problème avec deux algorithmes différents.

Quelle est le programme le plus efficace des deux ?

Comparer les algorithmes

  1. Premier critère: correction de l’algorithme
  2. Second critère: complexité

Correction de l’algorithme

Problème correctement résolu

Le programme fait ce qu’on attend de lui

Correction d’un algorithme — Wikipédia

Exemple: somme de nombres

On te demande de faire une fonction qui va renvoyer la somme de tous les chiffres partant de 1 jusqu’au nombre passé en paramètre. Plus clairement, quelque chose qui aurait ce comportement:

n = 3
output = getSum(n)
print(output)
# imprime : 6  car 1 + 2 + 3 = 6

Solution triviale:

def getSum(n):
    sum = 0
    for number in range(1, n + 1):
        sum += number
    return sum

Ça marche: mise en production, tout fonctionne

Mais 2 semaines plus tard, on s’aperçoit que le programme est très lent.

Et on identifie que la fonction qui pose problème est la fonction getSum

En effet, le paramètre qui lui est passé dépasse souvent le milliard.

Un autre développeur remplace le code de la fonction par celui-ci:

def getSum(n):
    return n * (n + 1) / 2

Cette fonction répond instantanément même avec un paramètre à 100 milliards.

En interrogeant le développeur par messagerie sur le pourquoi du remplacement, il répond:

Salut ! Ta solution avait une tendance linéaire O(n) sauf que l’input était énorme. J’ai trouvé une solution constante O(1). Peu importe l’input, ça sera rapide maintenant.

Complexité algorithmique

Types de complexité

Complexité temporelle

Temps d’exécution: mesure de la durée nécessaire à la résolution d’un problème

Temps mis par le processeur pour effectuer les instructions décrites par l’algorithme.

Complexité spatiale

Espace = matériel informatique

Ressources nécessaires à l’exécution du programme: par exemple la quantité de mémoire (vive ou de stockage).

Critère le plus important

Complexité temporelle

Complexité temporelle des algorithmes

Mesure

La mesure de la complexité se fait indépendamment de la puissance (vitesse, capacités) du microprocesseur.

Évaluation

Plus la complexité est faible, plus l’algorithme est performant.

Critère

Complexité asymptotique

Approximation du temps d’exécution:

Intérêt

Indépendant de la puissance de l’ordinateur utilisé

Dimensionnement

Approximation donné par la notation :

Définition

Estimation du nombre d’opérations à exécuter pour terminer complètement l’algorithme.

Opération

Suite d’instructions nécessaires pour réaliser une tâche algorithmique.

Instruction

Une instruction n’est pas une opération.

Exemple

Programme
Variables
    age: entier
Début
    AFFICHER("Indiquer votre âge:")
    age <-- LIRE()
Fin

Dans ce programme:

Complexité O(1)

Le programme suivant a une complexité \(O(1)\)

Programme
Variables
    age: entier
Début
    AFFICHER("Indiquer votre âge:")
    age <-- LIRE()
Fin

On parle aussi de complexité constante

Augmentation du nombre d’instructions

Programme
Variables
    age: entier
    genre: texte
    nom: texte
    prenom: texte
Début
    AFFICHER("Indiquer votre âge:")
    age <-- LIRE()
    AFFICHER("Indiquer votre genre:")
    age <-- LIRE()
    AFFICHER("Indiquer votre nom:")
    nom <-- LIRE()
    AFFICHER("Indiquer votre prenom:")
    prenom <-- LIRE()
Fin

Complexité: \(O(4)\)

4 est ici un facteur multiplicateur

Le facteur multiplicateur est toujours négligé : \(O(4 \times 1)\)

Complexité: \(O(1)\)

Si le nombre d’opérations est toujours le même lors de l’exécution, la complexité est \(O(1)\)

Complexité \(O(n)\)

Complexité linéaire

Tableau Tableau[14] en Numérique
Variables Moyenne, Somme en Numérique
Début
Somme <-- 0
Pour i <-- 0 à 13
  Somme <-- Somme + Tableau[i]
i Suivant
Moyenne <-- Somme / 14
Fin

Exemple 2

Tableau Note[11] en Numérique
Variables Moy, Som en Numérique
Début
Pour i <-- 0 à 11
  Ecrire "Entrez la note n°", i
  Lire Note[i]
i Suivant
Som <-- 0
Pour i <-- 0 à 11
  Som <-- Som + Note[i]
i Suivant
Moy <-- Som / 12
Fin

Complexité \(O(n^2)\)

Complexité quadratique

Variables
largeur, longueur : entier
Début
    largeur <-- 30
    longueur <-- 80
    Pour i ALLANT DE 0 à largeur
        Pour i ALLANT DE 0 à longueur
            AFFICHER_SL("+")
        FIN POUR
        AFFICHER("")
    FIN POUR
Fin

Complexité logarithmique

Exemple : recherche dichotomique

Référence: recherche dichotomique

Références