Introduction à l'analyse des algorithmes

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é complexité temporelle, ou volume de mémoire, appelé complexité spatiale.

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 3000nLogn et 10nLogn sur une machine. Ces deux algorithmes sont asymptotiquement identiques (l’ordre de croissance est nLogn). 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.

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

•   Le pire des cas − Le nombre maximum de mesures prises sur une instance de taille n.
•   Le meilleur des cas − Le nombre minimum de mesures prises sur une instance de taille n.
•   Cas moyen - Nombre moyen d'étapes effectuées sur une instance de taille n.

Considérons la mise en oeuvre 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

Dans le pire des cas, nous calculons jusqu'à 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. Par conséquent, la complexité temporelle de la recherche linéaire dans le pire des cas serait Θ(n).

Dans l'analyse de cas moyen, nous prenons toutes les entrées possibles et calculons le temps de calcul pour toutes les entrées. Faites la somme de toutes les valeurs calculées et divisez 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} \label{eq1} \begin{split} 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} $$

Dans l'analyse 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). Donc, la complexité temporelle dans le meilleur des cas serait Θ(1).

La plupart du temps, nous effectuons une analyse dans le pire des cas. Dans la pire analyse, nous garantissons une limite supérieure sur le temps d'exécution d'un algorithme, ce qui est une bonne information.

L'analyse de cas moyen n'est pas facile à faire dans la plupart des cas pratiques et c'est rarement fait. Dans l'analyse de cas moyen, nous devons connaître (ou prévoir) la distribution mathématique de toutes les entrées possibles.

L'analyse meilleur de cas est fausse. Garantir une limite inférieure sur un algorithme ne fournit aucune information car dans le pire des cas, un algorithme peut prendre des années à s'exécuter.