AlegsaOnline.com

Comparaison asymptotique

Auteur: Leandro Alegsa

09-05-2021

La notation Big O est un moyen de comparer les algorithmes. Elle les compare en calculant la quantité de mémoire nécessaire et le temps nécessaire pour les réaliser.

La notation Big O est souvent utilisée pour identifier la complexité d'un problème, également appelée classe de complexité du problème. Le mathématicien Paul Bachmann (1837-1920) a été le premier à utiliser cette notation, dans la deuxième édition de son livre "Analytische Zahlentheorie", en 1896. Edmund Landau (1877-1938) a rendu cette notation populaire. C'est pourquoi, lorsque les gens parlent des symboles de Landau, ils se réfèrent à cette notation.

La notation Big O est nommée d'après le terme "ordre de la fonction", qui fait référence à la croissance des fonctions. La notation Big O est utilisée pour trouver la limite supérieure (la plus grande quantité possible) du taux de croissance de la fonction, ce qui signifie qu'elle calcule le temps le plus long nécessaire pour transformer l'entrée en sortie. Cela signifie qu'un algorithme peut être regroupé en fonction du temps qu'il peut prendre dans le pire des cas où le chemin le plus long sera emprunté à chaque fois.

Big O est une expression qui permet de trouver le temps d'exécution du pire scénario, montrant l'efficacité d'un algorithme sans avoir à exécuter le programme sur un ordinateur. Cela est également utile car différents ordinateurs peuvent avoir un matériel différent et donc avoir besoin de temps différent pour le réaliser. Comme le Big O suppose toujours le pire scénario, il peut montrer une mesure cohérente de la vitesse : quel que soit le matériel utilisé, O ( 1 )/O(1)} $O(1)$ va toujours s'exécuter plus vite que O ( n ! )/O(n !)} $O(n!)$ parce qu'ils ont des niveaux d'efficacité différents.

Exemples

Les exemples suivants utilisent tous du code écrit en Python. Notez que cette liste n'est pas exhaustive.

Constant

O(1) $O(1)$ . Prend toujours le même temps, quelle que soit la saisie. Par exemple, prenons une fonction qui accepte un entier (appelé x) et qui renvoie le double de sa valeur :

def double(x) : return x * 2 #Retourne la valeur de x fois 2

Après avoir accepté l'entrée, cette fonction fera toujours un pas pour renvoyer une sortie. Elle est constante car elle prendra toujours la même durée, c'est pourquoi elle est O ( 1 )/O(1)} $O(1)$ .

Linéaire

O(n) $O(n)$ . Augmente en fonction de la taille de l'entrée, représentée par n {\style d'affichage n} . Supposons qu'une fonction accepte n, et renvoie chaque nombre de 1 à n :

def count(n) : i = 1 #Créer un compteur appelé "i" avec une valeur de 1 alors que i <= n : #Tandis que i est inférieur ou égal à n print(i) #Imprimer la valeur de i i = i + 1 #Redéfinir i comme "la valeur de i + 1"

Si nous saisissons la valeur 5, nous obtenons 1, 2, 3, 4, 5 (style d'affichage 1, 2, 3, 4, 5) $1,2,3,4,5$ qui nécessite 5 boucles. De même, si nous saisissons 100, il en sortira 1, 2, 3...98, 99, 100 (style d'affichage 1,2,3...98,99,100) $1,2,3...98,99,100$ , ce qui nécessitera 100 boucles pour être complet. Si l'entrée est n {style d'affichage n} alors le temps d'exécution de l'algorithme est exactement n {style d'affichage n} boucles à chaque fois, donc O ( n ) {style d'affichage O(n)} $O(n)$ .

Factorial

O ( n ! ) {\displaystyle O(n !)} $O(n!)$ . Augmentation des montants factoriels, c'est-à-dire que le temps nécessaire augmente massivement avec l'entrée. Par exemple, disons que nous souhaitons visiter cinq villes dans le monde et que nous voulons voir toutes les possibilités de commande (permutation). Voici un algorithme que nous pourrions écrire en utilisant la bibliothèque itertools de Python :

import itertools #Import the itertools library cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rome'] #An array of our chosen cities def permutations(cities) : #Prendre un tableau de villes comme entrée : pour i dans itertools. permutations(cities) : #Pour chaque permutation de nos éléments (assignés à la variable "i") print(i) #Sortie i

Cet algorithme calculera chaque permutation unique de nos villes et la produira ensuite. Voici quelques exemples de résultats :

('Londres', 'Paris', 'Berlin', 'Amsterdam', 'Rome') ('Londres', 'Paris', 'Berlin', 'Rome', 'Amsterdam') ('Londres', 'Paris', 'Amsterdam', 'Berlin', 'Rome') ... ("Rome", "Amsterdam", "Paris", "Berlin", "Londres") ("Rome", "Amsterdam", "Berlin", "Londres", "Paris") ("Rome", "Amsterdam", "Berlin", "Paris", "Londres")

Ici, notre liste d'entrées est longue de 5 éléments, et pour chaque sélection, nos options restantes diminuent de 1. En d'autres termes, nos 5 entrées choisissent 5 × 4 × 3 × 2 × 1 $5\times 4\times 3\times 2\times 1$ éléments (ou 5 ! Si notre entrée est longue de n villes, alors le nombre de sorties est de n ! En d'autres termes, si nous passons par toutes les permutations, nous aurons besoin de O ( n ! ) $O(n!)$ boucles O(n !)} $n!$ pour les compléter.

Notation Little-o

Une version plus stricte du Big O est little-o. La différence entre big O et little-o est que little-o est une limite supérieure stricte : alors que O ( n ) {\displaystyle O(n)} $O(n)$ signifie que le temps de réalisation augmentera jusqu'à ce maximum en fonction de la taille de l'entrée, le o ( n ) {\displaystyle o(n)} $o(n)$ signifie que le temps de réalisation sera généralement inférieur à ce temps. En d'autres termes, le grand O suppose que chaque boucle prendra le chemin le plus long et que le processus prendra le plus de temps possible, alors que le petit o est plus réaliste en ce qui concerne les temps d'exécution réels ; si le nombre de boucles est basé sur le lancement d'un dé à 6 faces, le grand O supposera toujours qu'un 6 est lancé, alors que le petit o prendra en compte la probabilité égale que d'autres nombres soient lancés.

Questions et réponses

Q : Qu'est-ce que la notation Big O ?

R : La notation Big O est un moyen de comparer les taux de croissance de différentes fonctions. Elle est souvent utilisée pour comparer l'efficacité de différents algorithmes en calculant la quantité de mémoire et le temps nécessaire à leur exécution. Elle peut également être utilisée pour identifier le degré de complexité d'un problème.

Q : Qui a été le premier à utiliser cette notation ?

R : Le mathématicien Paul Bachmann (1837-1920) a été le premier à utiliser cette notation dans son livre "Analytische Zahlentheorie" en 1896.

Q : Que signifie le grand O ?

R : Big O signifie "ordre de la fonction", qui fait référence au taux de croissance des fonctions.

Q : Comment la notation Big O est-elle utilisée ?

R : La notation Big O est utilisée pour trouver une limite supérieure (le montant le plus élevé possible) sur le taux de croissance de la fonction, ce qui signifie qu'elle calcule le temps le plus long qu'il faudra pour transformer une entrée en sortie. Cela signifie que les algorithmes peuvent être regroupés en fonction du temps qu'ils prennent dans le pire des scénarios, où le chemin le plus long sera emprunté à chaque fois.

Q : Que sont les symboles de Landau ?

R : Les symboles Landau font référence à la notation Big O, nommée d'après Edmund Landau (1877-1938) qui a rendu cette notation populaire.

Q : Pourquoi Big O est-il utile ?

R : Big O nous permet de mesurer la vitesse sans avoir à exécuter les programmes sur les ordinateurs puisqu'il suppose toujours les pires scénarios, ce qui le rend cohérent quelles que soient les différences matérielles entre les ordinateurs. Il montre également l'efficacité d'un algorithme sans avoir à l'exécuter sur un ordinateur.