gros Python notation o

Remarque : Si vous n’avez pas lu notre article sur la complexité temporelle, il est recommandé de commencer là. La deuxième partie de cette série suppose que vous connaissez les différentes valeurs Big O possibles.

Dans notre premier article sur Big O Notation et complexité temporelle, nous parlons du temps qu’il faut à l’algorithme pour se terminer lorsque son entrée augmente. Ceci est important lorsque nous interagissons avec de très grands ensembles de données. Un grand ensemble de données combiné à une complexité temporelle décente conduit à des algorithmes plus efficaces. Cependant, il y a un autre aspect de la notation Big O qui doit être pris en compte : la complexité de l’espace.

Qu’est-ce que la complexité de l’espace ?

La complexité du temps et la complexité de l’espace sont similaires en ce qui concerne la quantité d’entrée d’un algorithme. Lorsque la complexité temporelle est liée à la quantité d’opérations qu’un algorithme doit effectuer pour se terminer, la complexité spatiale est liée à la quantité totale d’espace nécessaire pour terminer l’algorithme. La complexité de l’espace est exprimée en termes de notation Big O.

La complexité de l’espace comprend la quantité d’espace nécessaire pour l’entrée ainsi que l’espace auxiliaire nécessaire dans l’algorithme à exécuter. L’espace auxiliaire est l’espace supplémentaire utilisé pour stocker des structures de données temporaires ou des variables utilisées pour résoudre l’algorithme. Tout comme dans la complexité temporelle, le grand O d’un algorithme considère le pire des cas, ou la limite supérieure asymptotique.

Déterminer l’espace requis pour exécuter un algorithme

Quand nous calculons la complexité spatiale d’un algorithme, jetez un ≈ìil à deux choses : la taille d’entrée et l’espace auxiliaire nécessaire pour exécuter la fonction. Dans la plupart des cas, nous ne réduisons pas la taille au nombre d’octets de l’entrée ‚Äì nous regardons simplement la quantité de mémoire que l’entrée ou l’espace auxiliaire doit utiliser.

L’entrée d’un algorithme est ce qui est transmis à la fonction lorsqu’elle est invoquée. En règle générale, il s’agira d’une sorte de valeur primitive : chaaîne, nombre ou objet. La taille exacte de chacune peut différer basé sur la langue, mais nous pouvons déterminer de manière générale combien d’espace est nécessaire.

Exemple avec des entrées et des sorties simples

(Remarque : nous utilisons Java ici afin que vous puissiez facilement discerner les types de données, mais cela peut à peu près aller pour n’importe quel langage.)

Prenez la fonction ci-dessus. Le but de cette fonction est de prendre une entrée - dans dans ce cas, deux ints(abréviation de nombres entiers) et renvoient une sortie, également un int.

81 % des participants ont déclaré qu’ils se sentaient m sont confiants quant à leurs perspectives d’emploi dans la technologie après avoir assisté à un bootcamp. Soyez jumelé à un bootcamp aujourd’hui.

Le diplômé moyen d’un bootcamp a passé moins de six mois en transition de carrière, du démarrage d’un bootcamp à la recherche de son premier emploi.

Dans notre contribution, nous avons deux variables ‚Äì int a et int b. Notre valeur renvoyée ‚Äì un int ‚Äì prend aussi de la place. Comme nos entiers ne sont évalués qu’une seule fois, nous considérons ici que la complexité spatiale est O(1) ‚Äì temps constant.

Exemple avec une entrée plus complexe

Cette fonction a un tableau en entrée. Le tableau, ne connaissant pas la longueur, a n indices. Les deux variables des deux premières lignes de la fonction sont O(1) puisqu’elles ne sont évaluées qu’une seule fois. La somme est un entier, est également O(1). Le grand O pour la complexité spatiale est O(n) pour dicter l’espace du tableau.

Conclusion

L’algorithme le plus efficace est celui qui prend le moins de temps et Mémoire. Il sera presque impossible, voire impossible, cependant, d’écrire un algorithme qui sera capable de satisfaire les deux conditions. Vous devez finalement sacrifier l’un pour l’autre. La question devient, qui sacrifiez-vous ?

La réponse est : cela dépend. Tout dépend des exigences du projet ou de l’algorithme sur lequel vous travaillez. Si vous n’avez qu’une mémoire minimale, vous devez sacrifier la complexité du temps pour utiliser le moins d’espace et vice versa .