Simplifions les complexités des algorithmes!

Cela fait un moment que j'ai commencé à penser à revenir aux bases et à me rafraîchir sur les concepts fondamentaux de l'informatique. Et j'ai pensé, avant de sauter dans le pool de sujets lourds comme les structures de données, les systèmes d'exploitation, la POO, les bases de données et la conception de système (sérieusement, la liste est sans fin)?, Je devrais probablement reprendre le sujet que nous ne voulons pas tous un peu touch: analyse de la complexité de l'algorithme.

Oui! Le concept qui est négligé la plupart du temps, car la majorité d'entre nous, les développeurs, pensons: «Hmm, je n'aurai probablement pas besoin de le savoir pendant que je code!».?

Eh bien, je ne sais pas si vous avez déjà ressenti le besoin de comprendre comment fonctionne réellement l'analyse d'algorithmes. Mais si vous l'avez fait, voici mon essai pour l'expliquer de la manière la plus lucide possible. J'espère que cela aide quelqu'un comme moi.?

Qu'est-ce que l'analyse d'algorithme de toute façon et pourquoi en avons-nous besoin? ?

Avant de plonger dans l'analyse de la complexité des algorithmes, commençons par avoir une brève idée de ce qu'est l'analyse d'algorithme. L'analyse des algorithmes consiste à comparer des algorithmes en fonction du nombre de ressources informatiques utilisées par chaque algorithme.

Ce que nous voulons réaliser par cette pratique, c'est être capable de prendre une décision éclairée sur l'algorithme gagnant en termes d'utilisation efficace des ressources (temps ou mémoire, selon le cas d'utilisation). Est-ce que ça a du sens?

Prenons un exemple. Supposons que nous ayons une fonction product () qui multiplie tous les éléments d'un tableau, à l'exception de l'élément à l'index courant, et renvoie le nouveau tableau. Si je passe [1,2,3,4,5] comme entrée, je devrais obtenir [120, 60, 40, 30, 24] comme résultat.

La fonction ci-dessus utilise deux boucles for imbriquées pour calculer le résultat souhaité. Dans la première passe, il prend l'élément à la position actuelle. Dans la deuxième passe, il multiplie cet élément avec chaque élément du tableau - sauf lorsque l'élément de la première boucle correspond à l'élément actuel de la deuxième boucle. Dans ce cas, il le multiplie simplement par 1 pour garder le produit non modifié.

Êtes-vous capable de suivre? Génial!

C'est une approche simple qui fonctionne bien, mais pouvons-nous l'améliorer légèrement? Pouvons-nous le modifier de manière à ne pas avoir à faire deux utilisations des boucles imbriquées? Peut-être stocker le résultat à chaque passage et l'utiliser?

Considérons la méthode suivante. Dans cette version modifiée, le principe appliqué est que pour chaque élément, calculez le produit des valeurs de droite, calculez les produits des valeurs de gauche, et multipliez simplement ces deux valeurs. Assez mignon, n'est-ce pas?

Ici, plutôt que d'utiliser des boucles imbriquées pour calculer les valeurs à chaque exécution, nous utilisons deux boucles non imbriquées, ce qui réduit la complexité globale d'un facteur O (n) (nous y reviendrons plus tard).

Nous pouvons en déduire que le dernier algorithme fonctionne mieux que le premier. Jusqu'ici tout va bien? Parfait!

À ce stade, nous pouvons également jeter un coup d'œil sur les différents types d'analyse d'algorithme qui existent. Nous n'avons pas besoin d'entrer dans les moindres détails, mais simplement d'avoir une compréhension de base du jargon technique.

Selon le moment où un algorithme est analysé, c'est-à-dire avant la mise en œuvre ou après la mise en œuvre, l'analyse de l'algorithme peut être divisée en deux étapes:

  • Analyse Apriori - Comme son nom l'indique, en apriori (a priori), nous faisons l'analyse (espace et temps) d'un algorithme avant de l'exécuter sur un système spécifique. Donc fondamentalement, il s'agit d'une analyse théorique d'un algorithme. L'efficacité d'un algorithme est mesurée en supposant que tous les autres facteurs, par exemple la vitesse du processeur, sont constants et n'ont aucun effet sur la mise en œuvre.
  • Analyse Apostiari - L'analyse Apostiari d'un algorithme est effectuée uniquement après son exécution sur un système physique. L'algorithme sélectionné est mis en œuvre à l'aide d'un langage de programmation qui est exécuté sur une machine informatique cible. Cela dépend directement des configurations du système et des changements d'un système à l'autre.

Dans l'industrie, nous effectuons rarement des analyses Apostiari, car le logiciel est généralement conçu pour des utilisateurs anonymes qui pourraient l'exécuter sur différents systèmes.

La complexité du temps et de l'espace pouvant varier d'un système à l'autre, l'analyse Apriori est la méthode la plus pratique pour trouver la complexité des algorithmes. En effet, nous ne regardons que les variations asymptotiques (nous y reviendrons plus tard) de l'algorithme, ce qui donne la complexité en fonction de la taille d'entrée plutôt que des configurations du système.

Maintenant que nous avons une compréhension de base de ce qu'est l'analyse d'algorithme, nous pouvons passer à notre sujet principal: la complexité des algorithmes. Nous nous concentrerons sur l' analyse Apriori , en gardant à l'esprit la portée de cet article, alors commençons.

Plongez dans la complexité avec une analyse asymptotique

L'analyse de la complexité des algorithmes est un outil qui nous permet d'expliquer comment un algorithme se comporte lorsque l'entrée augmente.

Ainsi, si vous souhaitez exécuter un algorithme avec un ensemble de données de taille n , par exemple, nous pouvons définir la complexité comme une fonction numérique f (n) - temps par rapport à la taille d'entrée n .

Maintenant, vous devez vous demander, n'est-il pas possible pour un algorithme de prendre différentes quantités de temps sur les mêmes entrées, en fonction de facteurs tels que la vitesse du processeur, le jeu d'instructions, la vitesse du disque et la marque du compilateur? Si oui, tapotez-vous dans le dos, car vous avez absolument raison !?

C'est là que l' analyse asymptotique entre en jeu. Ici, le concept consiste à évaluer les performances d'un algorithme en termes de taille d'entrée (sans mesurer le temps réel de fonctionnement). Donc, fondamentalement, nous calculons comment le temps (ou l'espace) pris par un algorithme augmente à mesure que nous rendons la taille d'entrée infiniment grande.

L'analyse de complexité est effectuée sur deux paramètres:

  1. Temps : La complexité temporelle donne une indication sur le temps qu'un algorithme prend pour se terminer par rapport à la taille d'entrée. La ressource qui nous préoccupe dans ce cas est le CPU (et l'heure de l'horloge murale).
  2. Espace : La complexité de l'espace est similaire, mais elle indique la quantité de mémoire «requise» pour exécuter l'algorithme par rapport à la taille d'entrée. Ici, nous traitons la RAM système en tant que ressource.

es-tu encore avec moi? Bien! Maintenant, il existe différentes notations que nous utilisons pour analyser la complexité par l'analyse asymptotique. Nous allons les parcourir tous un par un et comprendre les principes fondamentaux de chacun.

Le grand oh (Big O)

La toute première notation et la plus populaire utilisée pour l'analyse de complexité est la notation BigO. La raison en est qu'il donne l'analyse du pire des cas d'un algorithme. L'univers nerd est principalement préoccupé par le mauvais comportement d'un algorithme et par la manière dont il peut être amélioré. BigO nous fournit exactement cela.

Entrons dans le côté mathématique pour comprendre les choses à leur base.

Considérons un algorithme qui peut être décrit par une fonction f (n). Donc, pour définir le BigO de f (n) , nous devons trouver une fonction, disons, g (n) , qui la limite. Cela signifie qu'après une certaine valeur, n0, la valeur de g (n) dépasserait toujours f (n) .

Nous pouvons l'écrire comme,

f (n) ≤ C g (n)

où n≥n0; C> 0; n0≥1

Si les conditions ci-dessus sont remplies, on peut dire que g (n) est le BigO de f (n), ou

f (n) = O (g (n))

Pouvons-nous appliquer la même chose pour analyser un algorithme? Cela signifie essentiellement que dans le pire des cas d'exécution d'un algorithme, la valeur ne doit pas dépasser un certain point, qui est g (n) dans ce cas. Par conséquent, g (n) est le BigO de f (n).

Passons en revue quelques notations bigO couramment utilisées et leur complexité et comprenons-les un peu mieux.

  • O (1): décrit un algorithme qui s'exécutera toujours dans le même temps (ou espace) quelle que soit la taille de l'ensemble de données d'entrée.
function firstItem(arr){ return arr[0];}

L' exécution de la fonction firstItem () ci-dessus prendra toujours le même temps, car elle renvoie le premier élément d'un tableau, quelle que soit sa taille. Le temps d'exécution de cette fonction est indépendant de la taille de l'entrée, et a donc une complexité constante de O (1).

En le reliant à l'explication ci-dessus, même dans le pire des cas de cet algorithme (en supposant que l'entrée soit extrêmement grande), le temps d'exécution resterait constant et ne dépasserait pas une certaine valeur. Ainsi, sa complexité BigO est constante, c'est-à-dire O (1).

  • O (N): décrit un algorithme dont les performances augmenteront de manière linéaire et proportionnelle à la taille de l'ensemble de données d'entrée. Jetez un œil à l'exemple ci-dessous. Nous avons une fonction appelée matchValue ( ) qui retourne true chaque fois qu'un cas correspondant est trouvé dans le tableau. Ici, puisqu'il faut itérer sur l'ensemble du tableau, le temps d'exécution est directement proportionnel à la taille du tableau.
function matchValue(arr, k){ for(var i = 0; i < arr.length; i++){ if(arr[i]==k){ return true; } else{ return false; } } }

Cela montre également comment Big O favorise le pire scénario de performance. Un cas correspondant pourrait être trouvé pendant toute itération de la forboucle et la fonction reviendrait tôt. Mais la notation Big O supposera toujours la limite supérieure (pire des cas) où l'algorithme effectuera le nombre maximum d'itérations.

  • O (N²): Ceci représente un algorithme dont les performances sont directement proportionnelles au carré de la taille de l'ensemble de données d'entrée. Ceci est courant avec les algorithmes qui impliquent des itérations imbriquées sur l'ensemble de données. Des itérations imbriquées plus profondes donneront O (N³), O (N⁴), etc.
function containsDuplicates(arr){ for (var outer = 0; outer < arr.length; outer++){ for (var inner = 0; inner < arr.length; inner++){ if (outer == inner) continue; if (arr[outer] == arr[inner]) return true; } } return false;}
  • O (2 ^ N): désigne un algorithme dont la croissance double à chaque ajout à l'ensemble de données d'entrée. La courbe de croissance d'une fonction O (2 ^ N) est exponentielle - commençant très peu profond, puis montant fulgurant. Un exemple de fonction O (2 ^ N) est le calcul récursif des nombres de Fibonacci:
function recursiveFibonacci(number){ if (number <= 1) return number; return recursiveFibonacci(number - 2) + recursiveFibonacci(number - 1);}

Comprenez-vous cela? Parfait. Sinon, n'hésitez pas à lancer vos requêtes dans les commentaires ci-dessous. :)

Maintenant que nous avons une meilleure compréhension de la notation BigO, passons au type suivant d'analyse asymptotique qui est le Big Omega (Ω).

Le Big Omega (Ω) ?

L e Big Omega (Ω) nous fournit le meilleur scénario d'exécution d'un algorithme. Cela signifie que cela nous donnerait la quantité minimale de ressources (temps ou espace) qu'un algorithme prendrait pour s'exécuter.

Plongeons-nous dans les mathématiques pour l'analyser graphiquement.

Nous avons un algorithme qui peut être décrit par une fonction f (n). Donc, pour définir le BigΩ de f (n) , nous devons trouver une fonction, disons, g (n) , qui est la plus étroite à la borne inférieure de f (n) . Cela signifie qu'après une certaine valeur, n0, la valeur de f (n) dépasserait toujours g (n) .

Nous pouvons l'écrire comme,

f (n) ≥ C g (n)

où n≥n0; C> 0; n0≥1

Si les conditions ci-dessus sont remplies, on peut dire que g (n) est le BigΩ de f (n), ou

f (n) = Ω (g (n))

Peut-on en déduire que Ω (…) est complémentaire de O (…)? Passons à la dernière section de ce message…

Le grand Thêta (θ) ?

L e Big Theta (θ) est une sorte de combinaison de BigO et BigΩ. Cela nous donne le scénario moyen de l'exécution d'un algorithme. Cela signifie que cela nous donnerait la moyenne du meilleur et du pire des cas. Analysons-le mathématiquement.

Considérons un algorithme qui peut être décrit par une fonction f (n). Le Bigθ de f (n) serait une fonction, disons, g (n) , qui la limite le plus étroitement par la borne inférieure et supérieure, de telle sorte que,

C₁g (n) ≤ f (n) ≤ C₂ g (n)

C₁, C₂ >0, n≥ n0,

n0 ≥ 1

Meaning, after a certain value, n0, the value of C₁g(n) would always be less than f(n), and value of C₂ g(n) would always exceed f(n).

Now that we have a better understanding of the different types of asymptotic complexities, let’s have an example to get a clearer idea of how all this works practically.

Consider an array, of size, say, n, and we want to do a linear search to find an element x in it. Suppose the array looks something like this in the memory.

Going by the concept of linear search, if x=9, then that would be the best case scenario for the following case (as we don’t have to iterate over the whole array). And from what we have just learned, the complexity for this can be written as Ω(1). Makes sense?

Similarly, if x were equal to 14, that would be the worst case scenario, and the complexity would have been O(n).

What would be the average case complexity for this?

θ(n/2) => 1/2 θ(n) => θ(n) (As we ignore constants while calculating asymptotic complexities).

So, there you go folks. A fundamental insight into algorithmic complexities. Did it go well with you? Leave your advice, questions, suggestions in the comments below. Thanks for reading!❤️

References:-

  • A nice write-up by Dionysis “dionyziz” Zindros: //discrete.gr/complexity/
  • A good series on algorithm & data structures: //interactivepython.org/runestone/static/pythonds/AlgorithmAnalysis/WhatIsAlgorithmAnalysis.html