Introduction à l'analyse des algorithmes

Analyse des algorithmes

Pourquoi se préoccuper des performances ?

Lors du développement d'un logiciel, de nombreux éléments importants doivent être pris en compte, tels que la convivialité, la modularité, la sécurité, la facilité de maintenance, etc. Pourquoi se préoccuper des performances ?

La réponse à cette question est simple : nous ne pouvons avoir toutes les choses ci-dessus que si nous avons des performances. La performance est donc comme une devise à travers laquelle nous pouvons acheter toutes les choses ci-dessus. Une autre raison d'étudier la performance est la vitesse.

Dans l'analyse théorique des algorithmes, il est courant d'estimer leur complexité au sens asymptotique, c'est-à-dire d'estimer la fonction de complexité pour une entrée arbitrairement grande.

L'analyse des algorithmes est une partie importante de la théorie de la complexité de calcul, qui fournit une estimation théorique des ressources requises d'un algorithme pour résoudre un problème de calcul spécifique. La plupart des algorithmes sont conçus pour fonctionner avec des entrées de longueur arbitraire. L'analyse des algorithmes consiste à déterminer la quantité de ressources en temps et en espace nécessaires à son exécution.

Habituellement, l'efficacité ou la durée d'exécution d'un algorithme est définie comme une fonction liant la longueur en entrée au nombre d'étapes, appelée complexité temporelle, ou volume de mémoire, appelé complexité spatiale.

Le besoin d'analyse

Les algorithmes sont souvent assez différents les uns des autres, même si leur objectif est le même. Par exemple, nous savons qu'un ensemble de nombres peut être trié en utilisant différents algorithmes. Le nombre de comparaisons effectuées par un algorithme peut varier avec d'autres pour la même entrée. Par conséquent, la complexité temporelle de ces algorithmes peut différer. Dans le même temps, nous devons calculer l'espace mémoire requis par chaque algorithme.

Comment pouvons-nous savoir lequel est le meilleur ?

Une façon naïve de faire cela consiste à implémenter les deux algorithmes et à exécuter les deux programmes sur votre ordinateur pour différentes entrées et voir lequel prend moins de temps.

Mais cette approche peut échouer dans certains cas :

• Il est possible que pour certaines entrées, le premier algorithme fonctionne mieux que le second. Et pour certaines entrées, le second fonctionne mieux.
• Il est également possible que, pour certaines entrées, le premier algorithme fonctionne mieux sur une machine et que le second fonctionne mieux sur une autre machine pour certaines autres entrées.

Une autre approche est l'analyse asymptotique. L'analyse asymptotique est la grande idée qui traite les problèmes ci-dessus dans l'analyse des algorithmes. Dans l'analyse asymptotique, nous évaluons les performances d'un algorithme en termes de taille d'entrée (nous ne mesurons pas le temps d'exécution réel). Nous calculons comment le temps (ou l'espace) pris par un algorithme augmente avec la taille d'entrée.

Est-ce que l'analyse asymptotique fonctionne toujours ?

L'analyse asymptotique n'est pas parfaite, mais c'est le meilleur moyen disponible pour analyser des algorithmes. Par exemple, supposons qu'il existe deux algorithmes de tri qui prennent respectivement 3000n log n et 10n log n sur une machine. Ces deux algorithmes sont asymptotiquement identiques (l'ordre de croissance est n log n). Ainsi, avec l'analyse asymptotique, nous ne pouvons pas déterminer lequel est le meilleur car nous ignorons les constantes dans l'analyse asymptotique.

En outre, dans l'analyse asymptotique, nous parlons toujours de tailles d'entrée supérieures à une valeur constante. Il se peut que ces entrées volumineuses ne soient jamais données à votre logiciel et qu'un algorithme asymptotiquement plus lent donne toujours de meilleurs résultats dans votre situation particulière. Vous pouvez donc choisir un algorithme asymptotiquement plus lent mais plus rapide pour votre logiciel.

Types d'analyse

Généralement, nous effectuons les types d'analyse suivants :

• Le pire des cas (Worst case) − Le nombre maximum d'opérations effectuées sur une instance de taille n.
• Le meilleur des cas (Best case) − Le nombre minimum d'opérations effectuées sur une instance de taille n.
• Cas moyen (Average case) − Le nombre moyen d'opérations effectuées sur une instance de taille n.

Analyse asymptotique - Exemple de la recherche linéaire

Considérons l'implémentation suivante de la recherche linéaire.

#include <stdio.h>

int recherche(int tab[], int n, int x)
{
    int i;
    for (i = 0; i < n; i++)
    {
        if (tab[i] == x)
            return i;
    }
    return -1;
}

int main()
{
    int T[] = {1, 3, 17, 80, 25, 10, 30, 15};
    int x = 25, n, pos;
    n = sizeof(T) / sizeof(T[0]); // calculer la taille du tableau

    pos = recherche(T, n, x);
    if (pos < 0)
        printf("l'élément %d n'appartient pas à la table", x);
    else
        printf("l'élément %d est trouvé dans le tableau à la position %d", x, pos);

    return 0;
}

def recherche(tab, n, x):
    i = 0
    for i in range(i, n):
        if (tab[i] == x):
            return i
    return -1


T = [1, 3, 17, 80, 25, 10, 30, 15]
x = 25
n = len(T)
pos = recherche(T, n, x)
if (pos < 0):
    print("l'élément {} n'appartient pas à la table".format(x))
else:
    print("l'élément {} est trouvé dans le tableau à la position {}".format(x, pos))

Lorsque le code ci-dessus est compilé et exécuté, il produit le résultat suivant :

l'élément 25 est trouvé dans le tableau à la position 4

Analyse des différents cas

Le pire des cas - Worst case

Dans le pire des cas, nous calculons la limite supérieure du temps d'exécution d'un algorithme. Nous devons connaître le cas qui entraîne l'exécution d'un nombre maximal d'opérations.

Pour la recherche linéaire, le pire des cas se produit lorsque l'élément à rechercher (x dans le code ci-dessus) n'est pas présent dans le tableau. Lorsque x n'est pas présent, la fonction recherche() le compare à tous les éléments de tab[] un à un.

Cas moyen - Average case

Dans l'analyse de cas moyen, nous prenons toutes les entrées possibles et calculons le temps de calcul pour toutes les entrées. Faisons la somme de toutes les valeurs calculées et divisons la somme par le nombre total d'entrées. Nous devons connaître (ou prédire) la distribution des cas.

Pour le problème de la recherche linéaire, supposons que tous les cas soient uniformément distribués (y compris le cas où x n'est pas présent dans le tableau). Nous additionnons donc tous les cas et divisons la somme par \((n + 1)\).

\[ \begin{equation} \begin{split} \text{Temps moyen} & = \frac{\sum_{i=1}^{n+1} \Theta(i)}{n+1} \\ & = \frac{\Theta((n+1)*(n+2)/2)}{n+1} \\ & = \Theta(n) \end{split} \end{equation} \]

Le meilleur des cas - Best case

Dans l'analyse du meilleur des cas, nous calculons la limite inférieure du temps d'exécution d'un algorithme. Nous devons connaître le cas qui entraîne l'exécution d'un nombre minimal d'opérations.

Dans le problème de la recherche linéaire, le meilleur des cas se produit lorsque x est présent au premier emplacement. Le nombre d'opérations dans le meilleur des cas est constant (ne dépend pas de n).

Tableau récapitulatif pour la recherche linéaire

Quel type d'analyse privilégier ?