Complexité asymptotique - notations

Dans la conception de l'algorithme, l'analyse de la complexité d'un algorithme est un aspect essentiel. La complexité algorithmique est principalement liée à ses performances, à sa rapidité ou à sa lenteur.

La complexité d'un algorithme décrit son efficacité en termes de quantité de mémoire nécessaire pour traiter les données et de temps de traitement.

La complexité d'un algorithme est analysée selon deux perspectives: le temps et l'espace.

C’est une fonction décrivant le temps requis pour exécuter un algorithme en termes de taille de l’entrée. le nombre de comparaisons entre entiers, le nombre de fois où une boucle interne est exécutée ou une autre unité naturelle liée à la quantité de temps réel que prendra l'algorithme.

C’est une fonction décrivant la quantité de mémoire d’un algorithme en termes de taille de l’entrée à cet algorithme. Nous parlons souvent de mémoire "supplémentaire" nécessaire, sans compter la mémoire nécessaire pour stocker l'entrée elle-même. Encore une fois, nous utilisons des unités naturelles (mais de longueur fixe) pour mesurer cela.

La complexité de l'espace est parfois ignorée parce que l'espace utilisé est minime et / ou évident. Cependant, il devient parfois un problème aussi important que le temps.

L’idée principale de l’analyse asymptotique est de disposer d’une mesure de l’efficacité des algorithmes ne dépendant pas de constantes spécifiques à une machine, ni d’implémenter des algorithmes ni de comparer le temps pris par les programmes.

Les notations asymptotiques sont des outils mathématiques permettant de représenter la complexité temporelle des algorithmes d'analyse asymptotique. Les 3 notations asymptotiques suivantes sont principalement utilisées pour représenter la complexité temporelle des algorithmes.

Lorsque nous disons des bornes serrées, nous entendons que la complexité temporelle représentée par la notation Big-Θ est similaire à la valeur moyenne ou à la plage dans laquelle le temps réel d'exécution de l'algorithme sera.

On dit que \(f(n) = \theta(g(n)) \) quand il existe des constantes c1 et c2 telles que \(c_{1}.g(n) \leqslant f(n) \leqslant c_{2}.g(n) \) pour toutes les valeurs suffisamment grande de n. Ici, n est un entier positif.

Cela signifie que la fonction f est bornée par la fonction g

Un moyen simple d'obtenir la notation Thêta d'une expression consiste à supprimer les termes d'ordre faible et à ignorer les constantes principales.

Exemple

Considérons une fonction donnée \(f(n) = 4.n^3 + 10.n^2 + 5.n + 1\)

Considérant \(g(n) = n^3\),   \(4.g(n) \leqslant f(n) \leqslant 5.g(n)\) pour toutes les grandes valeurs de n.
Par conséquent, la complexité de f(n) peut être représentée par \(\theta (g(n))\) c’est-à-dire \(\theta(n^3)\).

Cette notation s'appelle la limite supérieure de l'algorithme ou le pire des cas d'un algorithme.
Cela nous indique qu'une certaine fonction ne dépassera jamais une durée spécifiée pour une valeur quelconque de l'entrée n.

La question est de savoir pourquoi nous avons besoin de cette représentation alors que nous avons déjà la notation Θ, qui représente le temps d'exécution étroitement lié à tout algorithme.

Prenons un petit exemple pour comprendre cela. Considérons un algorithme de recherche linéaire, dans lequel nous parcourons les éléments du tableau, un par un, pour rechercher un nombre donné.

Dans le pire des cas, en partant du début du tableau, nous trouvons l'élément ou le nombre que nous recherchons à la fin, ce qui conduit à une complexité temporelle de n, où n représente le nombre total d'éléments. Mais il peut arriver que l’élément recherché soit le premier élément du tableau, auquel cas la complexité temporelle sera de 1.

Maintenant, dans ce cas, dire que la recherche linéaire est de complexité Θ(n) signifie que le temps requis sera toujours lié à n, car c’est le bon moyen de représenter la complexité moyenne du temps. , mais lorsque nous utilisons la notation Big-O, nous entendons par là que la complexité temporelle est O(n), ce qui signifie que la complexité temporelle ne dépassera jamais n, définissant ainsi la limite supérieure, ce qui signifie qu'elle peut être inférieure à ou égal à n, qui est la représentation correcte.

C'est la raison pour laquelle, la plupart du temps, vous verrez que la notation Big-O est utilisée pour représenter la complexité temporelle d'un algorithme, car cela a plus de sens.

On dit que \(f(n) = O(g(n)) \) quand il existe une constante c telle que \(f(n) \leqslant c.g(n) \) pour toutes les valeurs suffisamment grande de n. Ici, n est un entier positif.

Exemple

Considérons une fonction donnée, \(f(n) = 4.n^3 + 10.n^2 + 5.n + 1\).
Considérant \(g(n) = n^{3}\), \(f(n)\leqslant 5.g(n)\) pour toutes les valeurs de \( n> 2 \).
Par conséquent, la complexité de \(f(n)\) peut être représentée par \(O(g(n))\), c’est-à-dire \(O(n^3)\)

La notation Ω est utilisée pour définir la limite inférieure de tout algorithme ou nous pouvons dire le meilleur des cas de tout algorithme.

Ceci indique toujours le temps minimum requis pour tout algorithme pour toutes les valeurs d'entrée, donc le meilleur des cas pour tout algorithme.

En termes simples, lorsque nous représentons une complexité temporelle pour tout algorithme sous la forme de Big-Ω, nous voulons dire que l'algorithme prendra au moins ce temps pour terminer son exécution. Cela peut certainement prendre plus de temps que cela aussi.

On dit que \(f(n) = \Omega(g(n)) \) quand il existe une constante c telle que \(c.g(n) \leqslant (f(n) \) pour toutes les valeurs suffisamment grande de n. Ici, n est un entier positif.

Exemple

Considérons une fonction donnée, \(f(n) = 4.n^3 + 10.n^2 + 5.n + 1\).
Considérant \(g(n) = n^3\), \(f(n)\geqslant 4.g(n)\) pour toutes les valeurs de \( n> 0 \).
Par conséquent, la complexité de \(f(n)\) peut être représentée par \(\Omega(g(n))\), c’est-à-dire \(\Omega(n^3)\)