Chapitre 9 : Algorithmes de recherche et complexité algorithmique⚓︎

A savoir

I. Recherche séquentielle⚓︎

1. Principe⚓︎

L'algorithme de recherche séquentielle (ou recherche par balayage) permet de rechercher une valeur dans un tableau. Il consiste simplement à parcourir le tableau en comparant les éléments à la valeur recherchée les uns après les autres: l'algorithme s'arrête lorsque la valeur est trouvée ou quand tous les éléments ont été passés en revue si elle n'y est pas.

Recherche séquentielle du nombre 87 dans le tableau ci-dessous en 11 étapes

2. Algorithme de la recherche séquentielle⚓︎

LANGAGE ALGORITHMIQUEPYTHON

DEBUT   
POUR  i ALLANT DE  0 A longueur(tab)  FAIRE    
    SI  tab[i] == valeur  ALORS    
        RENVOYER  Vrai  
RENVOYER  Faux  
FIN

    def recherche_sequentielle(tab, valeur): 
        for i in range(len(tab)):
            if tab[i] == valeur:
                return True
        return False

A savoir

II. Recherche dichotomique⚓︎

1. Principe⚓︎

L'algorithme de recherche dichotomique permet de rechercher une valeur dans un tableau trié dans l'ordre croissant: cette contrainte est une précondition nécessaire à l'utilisation de l'algorithme.

Celui-ci consiste à :

1️⃣ trouver la position la plus centrale du tableau.

2️⃣ comparer l'élément qui se trouve à cette position à la valeur recherchée.

si la valeur recherchée est égale à l'élément, alors on arrête l'algorithme
si la valeur recherchée est inférieure à l'élément on reprend l'étape 1️⃣ sur la partie gauche du tableau
si la valeur recherchée est supérieure à l'élément on reprend l'étape 1️⃣ sur la partie droite du tableau

2. Algorithme de la recherche dichotomique⚓︎

LANGAGE ALGORITHMIQUEPYTHON

DEBUT  
debut ← 1  
fin ← longueur(tab)  
TANT QUE debut < fin  
    milieu ← partie_entière((début + fin)/2)  
    SI valeur = tab[milieu]  ALORS  
        RENVOYER Vrai  
    SINON S valeur > tab[milieu] ALORS  
        debut ← milieu + 1  
    SINON SI valeur < tab[milieu] ALORS  
        fin ← milieu - 1  
RENVOYER Faux   
FIN

    def recherche_dichotomique(tab, valeur):
        debut = 0
        fin = len(tab) - 1
        while debut <= fin :
            milieu = (debut + fin) // 2
            if valeur == tab[milieu]:
                return True
            elif valeur > tab[milieu]:
                debut = milieu + 1
            elif valeur < tab[milieu]:
                fin = milieu - 1
        return False

A savoir

III. Coût comparé des deux algorithmes de recherche⚓︎

1. Coût d'un algorithme⚓︎

Le coût d'un algorithme (ou complexité temporelle) est une estimation du temps que va mettre l'algorithme pour se finir: il permet de quantifier sa performance.

Pour pouvoir comparer la performance des algorithmes entre eux il faut que les règles du calcul du coût soient indépendantes du langage de programmation utilisé et du processeur de l'ordinateur sur lequel sera exécuté le code : ainsi on se basera sur le nombre d'opérations effectuées.

Le coût d'un algorithme est le nombre d'opérations élémentaires (affectations, calculs, comparaisons) effectuées par un algorithme en fonction de la taille N des données.

On distingue plusieurs ordres de grandeurs du coût d'un algorithme. On dira que le coût est :

En O(1) ou constant si ce coût est une constante : \(C=k\)
En O(N) ou linéaire (ou d'ordre N ) si ce coût est proportionnel à N: \(C=k × N\)
En O(N²) ou quadratique s'il est proportionnel au carré de N: \(C=k × N²\)
En O(log(N)) ou logarithmique s'il est proportionnel au logarithme de N: \(C=k × log(N)\)

Les courbes ci-contre donnent l'évolution du coût en fonction du nombre d'entrées N pour chacun des cas.

Allure des courbes des différentes complexités

On peut évaluer le coût d'un algorithme :

dans le meilleur des cas : c'est la situation la plus favorable, par exemple, la recherche d'un élément situé à la première position d'une liste.
dans le pire des ca : c'est la situation la plus défavorable, par exemple, la recherche d'un élément dans une liste alors qu'il n'y figure pas.
dans le cas moyen : par exemple, la recherche d'un élément situé au centre d'une liste.

On calcule le plus souvent la complexité dans le pire des cas, car elle est la plus pertinente : il vaut mieux en effet toujours envisager le pire.

Sur un ordinateur effectuant 1000000 d'opérations par seconde le tableau suivant donne le temps de résolution d'un problème en fonction de la taille des données en entrée (pour quelques types de complexités).

Complexité Taille	log(n)	n	n * log(n)	n²	n³	\(2^n\)
n=10²	6.6 µs	0.1 ms	0.6 ms	10 ms	1 s	4 × 10⁶ a
n=10⁵	9.9 µs	1 ms	9.9 ms	1 s	16.6 mn	>10¹⁰⁰ a
n=10⁴	13.3 µs	10 ms	0.1 s	100 s	11.5 j	>10¹⁰⁰ a
n=10⁵	16.6 µs	0.1 s	1.6 s	2.7 h	31.7 a	>10¹⁰⁰ a
n=10⁶	19.9 µs	1 s	19.9 s	11.5 j	31.7 × 10³ a	>10¹⁰⁰ a

2. Comparaison des deux algorithmes de recherche⚓︎

Dans le pire des cas lorsque la valeur recherchée n'est pas dans le tableau :

le coût (ou complexité temporelle) en fonction de la taille N des données en entrée de l'algorithme de recherche séquentielle est linéaire ou en O(N): \(C=k × N\).
le coût (ou complexité temporelle) en fonction de la taille N des données en entrée de l'algorithme de recherche dichotomique est logarithmique ou en O(log(N)): \(C=k × log(N)\).

L'algorithme de recherche dichotomique est donc plus performant en moyenne que l'algorithme de recherche séquentielle.

Remarques :

1) Le coût des deux algorithmes augmente quand la taille N des données en entrée augmente.

2) Le coût de l'algorithme de recherche dichotomique est beaucoup plus faible que celui de l'algorithme de recherche séquentielle.

3) Si on multiplie par 10 la taille des données en entrée alors :

le coût de l'algorithme recherche séquentielle est aussi multiplié par 10 car il est linéaire.
le coût de l'algorithme recherche dichotomique est augmenté de 3 !

Ceci explique que l'algorithme de recherche dichotomique augmente moins vite lorsque la taille des données en entrée augmente.