Notation Big O et structures de données
Pour lancer cette série sur les structures de données, nous allons couvrir quelque chose d'un peu théorique connu sous le nom de notation grand O.
Des bases aux structures de données
Cela fait longtemps qu'on ne s'est pas vu! Il semble que cela fait un petit moment que nous n'avons pas parlé de Java sur The Renegade Coder. En fait, la dernière leçon était le didacticiel de clôture de la série Java Basics :Review of the Java Basics Series. Cette leçon a revisité tous les sujets que nous avons abordés tout au long de cette série, tels que la structure de classe, les boucles et le flux de contrôle.
À ce stade, il serait probablement judicieux de commencer à aborder des sujets Java plus avancés tels que l'héritage et le polymorphisme. Au lieu de cela, nous allons nous tourner vers quelque chose d'un peu plus théorique. Ne vous inquiétez pas ! Ces rubriques nous aideront lorsque nous reviendrons sur des rubriques Java plus avancées. Au lieu de cela, nous allons commencer à nous attaquer aux structures de données en acquérant une meilleure compréhension de la notation Big O.
Que sont les structures de données ?
Si nous nous souvenons jusqu'au didacticiel Java Basics Review, nous nous souviendrons que nous avons créé un programme de notation des tests. Pour que le programme fonctionne, nous avons dû introduire un nouveau concept :le tableau.
Le tableau nous a permis de stocker une liste de tests que nous évaluerions ensemble. C'était assez puissant car cela nous donnait la possibilité de stocker plusieurs tests sans donner à chacun son propre champ. Nous venons de créer un seul champ pouvant stocker autant de tests que nous le voulions.
Ce mécanisme de stockage est connu sous le nom de structure de données . En d'autres termes, une structure de données est un moyen d'organiser les données.
Qu'est-ce que la notation Big O ?
Heureusement, notre tableau n'est pas le seul moyen d'organiser les données. Nous aurions pu utiliser une liste chaînée, ou peut-être un arbre, ou même une table de hachage. Ne vous inquiétez pas si certains de ces termes sont nouveaux. Nous les couvrirons en détail au fur et à mesure que cette série avance.
Avec toutes ces options, comment savoir laquelle choisir ? La clé est de comprendre chaque structure de données à un niveau fondamental. Par exemple, combien de temps faut-il pour insérer un nouvel élément dans la structure de données ? Combien de temps faut-il pour rechercher un élément dans la structure de données ? Ces temps changent-ils au fur et à mesure que la structure des données grandit ? Si oui, cela a-t-il un impact positif ou négatif sur notre conception ?
Définition
Essentiellement, ces types de questions conduisent à un concept connu sous le nom de notation Big O ou Big O. Big O est souvent utilisé pour décrire la limite supérieure asymptotique de performance ou de complexité pour une fonction donnée. En d'autres termes, Big O peut être utilisé comme une estimation des performances ou de la complexité d'un algorithme donné.
Cela dit, le grand O n'a rien à voir avec les meilleures, moyennes ou pires performances ou complexité. Cependant, il peut décrire un algorithme dans n'importe laquelle de ces situations. Si cela semble déroutant, ne vous inquiétez pas. La terminologie mathématique peut être difficile à saisir. Je vous recommande de lire la définition formelle du grand O, de sorte que vous serez au moins plus à l'aise avec les mathématiques.
Quoi qu'il en soit, plongeons dans quelque chose d'un peu plus pratique.
Explication
En connaissant Big O pour différentes caractéristiques d'une structure de données, nous sommes en mesure de prendre des décisions assez rapidement. Mais qu'est-ce que la notation Big O ? C'est une mesure qui s'affiche généralement comme suit :
O(N log(N))
Oh oh ! On dirait que nous devrons rafraîchir un peu nos compétences en mathématiques. Ce que nous examinons ci-dessus est la limite supérieure asymptotique d'une fonction qui a un paramètre N. Dans les algorithmes, N est généralement la taille de l'ensemble d'entrée.
Par exemple, si nous voulions trier une liste de taille 10, alors N serait 10. En d'autres termes, Big O nous indique combien de temps ou d'espace un algorithme pourrait prendre compte tenu de la taille de l'ensemble de données.
Cependant, Big O n'est presque jamais utilisé dans plug'n chug mode. Au lieu de cela, il est utilisé pour décrire les performances ou la complexité d'un algorithme lorsque la taille de l'ensemble de données tend vers l'infini. Après tout, en tant que développeurs de logiciels, nous nous soucions de l'évolutivité. Nous voulons être en mesure de choisir la bonne structure de données pour le travail dès la première fois. Sinon, nous pourrions voir notre conception s'arrêter au fil du temps.
Exemples de grands O
La meilleure façon de comprendre Big O est peut-être de partager quelques exemples de codage. De cette façon, nous aurons une idée de certaines applications du monde réel. Pour commencer, nous allons commencer par O(1).
O(1) Exemple
Étant donné un scénario meilleur, pire ou moyen, O (1) fait référence à un algorithme qui ne s'exécutera pas pire qu'un temps ou un espace constant proportionnel à la taille de l'ensemble de données. Par exemple :
public int getFirstElement(int[] myList) {
return myList[0];
} Dans cet exemple, nous extrayons le premier élément d'un tableau. Étant donné que chaque élément d'un tableau a une taille fixe, nous pouvons accéder à n'importe lequel d'entre eux en temps constant. Pour ce faire, nous multiplions la taille d'un élément par l'index auquel nous voulons accéder et ajoutons ce produit à l'adresse mémoire du premier élément :
memory_address_of(element_11) = memory_address_of(element_0) + size_of_element * index_of(element_11)
Cette méthode fonctionne pour nous donner le premier élément d'un tableau en temps constant.
O(N) Exemple
Étant donné un scénario meilleur, pire ou moyen, O (N) fait référence à un algorithme qui s'exécute dans un temps ou un espace linéaire au plus égal à la taille de l'ensemble de données. En d'autres termes, le temps ou l'espace d'exécution augmente linéairement avec la taille de l'ensemble de données. Par exemple :
public int sumSet(int[] values) {
int sum = 0;
for (int i = 0; i < values.length; i++) {
sum += value[i];
}
return sum;
} Dans ce cas, la boucle doit itérer sur tous les éléments de l'ensemble de données pour produire la somme. À mesure que la taille de l'ensemble de données augmente, le temps de calcul de la somme augmente de manière linéaire.
O(N²) Exemple
Étant donné un scénario meilleur, pire ou moyen, O(N²) fait référence à un algorithme qui s'exécute dans le temps ou dans l'espace proportionnel au carré de la taille de l'ensemble de données. En d'autres termes, si nous avions un ensemble de données contenant 4 éléments, il faudrait 16 itérations pour compléter l'algorithme. Comme nous pouvons le constater, ce problème évolue assez rapidement.
Pour un exemple de O(N²), essayons un algorithme de tri. En particulier, nous allons implémenter le tri à bulles. Le tri à bulles est généralement un mauvais algorithme de tri, mais nous verrons comment cela se passe beaucoup plus tard dans la série.
public static void bubbleSort(int[] numberList) {
int n = numberList.length;
int temp = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j < (n - i); j++) {
if (numberList[j - 1] > numberList[j]) {
temp = numberList[j - 1];
numberList[j - 1] = numberList[j];
numberList[j] = temp;
}
}
}
}
Ici, nous pouvons voir que l'algorithme de tri à bulles utilise une boucle imbriquée. En particulier, nous verrons que le nombre d'itérations sur l'ensemble de données est i * j . Une boucle imbriquée est généralement un drapeau rouge qui démontre que nous avons un algorithme O(N²) (pas une vérité universelle, mais nous le verrons plus tard).
Mais qu'en est-il de l'espace ?
Comme indiqué à plusieurs reprises déjà, Big O est une mesure de limite supérieure asymptotique de la performance pour un algorithme particulier. Nous avons principalement examiné des exemples de performances en termes de temps, mais Big O peut également être utilisé pour mesurer la complexité de l'espace. En d'autres termes, Big O peut être utilisé pour mesurer l'impact d'un algorithme sur la mémoire.
Par exemple, un algorithme avec une complexité spatiale O (N²) nécessiterait un espace proportionnel au carré de l'ensemble de données d'entrée. Par espace, nous entendons des emplacements de mémoire physique. Pour l'algorithme O(N²) avec une taille de données d'entrée de 10, nous aurions besoin d'allouer 100 emplacements physiques en mémoire. Parfois, l'utilisation de la mémoire nous permet de réduire les comparaisons et les calculs redondants qui réduisent la durée d'exécution d'un algorithme.
Décomposer Big O
Maintenant que nous avons une meilleure compréhension de Big O, voyons l'impact réel qu'il peut avoir sur un algorithme. Le widget Wolfram Alpha suivant devrait aider à mettre un peu en perspective les performances de l'algorithme. Utilisez les lignes de fonction pour écrire des équations telles que 1, x et x². Étendez ensuite l'axe des x pour avoir une meilleure idée de l'impact de ces taux de croissance à mesure que la taille de l'ensemble de données augmente.
Si nous traitons l'axe des x comme s'il s'agissait de la taille de l'ensemble de données, nous pouvons rapidement voir l'impact qu'un mauvais algorithme peut avoir sur le temps ou l'espace d'exécution. Par exemple, regardez simplement la différence entre O(N) et O(N²). Au moment où la taille des données d'entrée atteint deux, l'algorithme O(N²) commence à prendre deux fois plus de temps ou d'espace que l'algorithme O(N).
Bien sûr, à petite échelle, Big O n'est guère pertinent. C'est en partie dû à la vitesse des processeurs modernes, mais c'est aussi dû au fait que la surcharge de l'algorithme peut avoir plus d'impact sur le temps d'exécution que l'algorithme réel. Par exemple, un algorithme O(N) peut mettre en cache certains calculs avant de s'exécuter. À long terme, il bat à chaque fois un algorithme O(N²). Cependant, à petite échelle, la mise en cache peut ajouter suffisamment de surcharge à l'algorithme O(N) pour que l'algorithme O(N²) ait réellement l'avantage. Gardez cela à l'esprit pendant que nous continuons.
Mesurer Big O
Afin de pouvoir réellement appliquer Big O, nous devrons pouvoir le mesurer pour un algorithme donné. Nous devrions maintenant comprendre que l'expression entre parenthèses est la mesure réelle du Big O. En d'autres termes, nous devrons être en mesure d'examiner un extrait de code et de déterminer l'expression qui décrit les performances les plus défavorables de cette fonction.
Quelques remarques
Avant de commencer à analyser les algorithmes, nous devons couvrir quelques aspects clés de Big O. Premièrement, lors de la mesure de Big O, nous ne nous soucions que du terme avec le plus grand ordre. Par exemple :
f(x) = x² + 3x - 17
Cette fonction pourrait très bien décrire les performances les plus défavorables d'un algorithme. Cependant, le terme avec le plus grand ordre est x². Par conséquent, le Big O de cet algorithme est O(N²).
Deuxièmement, les constantes sont également ignorées lors de la mesure de Big O. Par exemple :
f(x) = 5x² + 9
Avec cette fonction, on pourrait penser que le 5 est significatif car il est ajouté au terme de plus grand ordre. Naturellement, nous signalerions que le Big O pour cet algorithme est O(5N²). La vérité est que nous ne nous soucions pas de cette constante car Big O mesure simplement le taux de croissance d'une fonction lorsqu'elle tend vers l'infini. Par conséquent, nous déclarerions également cet algorithme comme O(N²).
Cependant, nous avons maintenant un peu de mal. Les deux algorithmes de cette section sont notés O(N²), mais ces algorithmes auront certainement des durées d'exécution différentes. Après tout, nous avons toujours affaire à des ensembles de données finis. Par conséquent, les fonctions d'origine doivent avoir un certain poids pendant l'exécution.
Cela nous amène au point final. Big O n'a d'importance que pour les très grands ensembles de données, et même dans ce cas, ce n'est pratique que pour choisir entre deux algorithmes avec différentes mesures de Big O. Sinon, cela revient à exécuter les algorithmes. Après tout, la théorie c'est bien, mais les preuves tangibles c'est mieux.
Stratégies de mesure Big O
Mesurer Big O est aussi simple que de parcourir le code et d'attribuer à chaque opération une mesure Big O. À partir de là, nous combinons nos mesures en une expression que nous réduisons finalement au terme d'ordre le plus élevé. En d'autres termes, nous avons juste besoin d'isoler le goulot d'étranglement, et nous aurons notre réponse.
O(1) Exemple
Pour être complet, revenons en arrière et évaluons réellement nos exemples à la main. Pour commencer, parcourons notre algorithme O(1) :
public int getFirstElement(int[] myList) {
return myList[0];
}
Si nous devions appeler cette méthode, la première chose qui se passerait serait d'évaluer myList[0] . Comme indiqué précédemment, l'accès aléatoire à un tableau est une opération à temps constant. Par conséquent, cette opération reçoit une cote de temps constante de O(1). Puisque la méthode se termine, nous avons notre réponse.
O(N) Exemple
Compliquons maintenant un peu plus les choses en utilisant l'algorithme O(N) :
public int sumSet(int[] values) {
int sum = 0;
for (int i = 0; i < values.length; i++) {
sum += value[i];
}
return sum;
}
Si nous tombons dans cette méthode, nous effectuons d'abord une affectation de variable qui est une opération à temps constant ou O(1). Ensuite, nous entrons dans notre boucle qui commence par une autre affectation de variable. À ce stade, nos performances globales ressemblent à quelque chose comme O(1) + O(1) .
Ensuite, nous allons effectuer une comparaison en temps constant. Cependant, cela fait partie de la boucle. Par conséquent, nous devons déterminer combien de fois la boucle itère. Dans ce cas, un tableau de taille 50 provoquerait 50 itérations alors qu'un tableau de taille 300 provoquerait 300 itérations. Cette relation est linéaire, donc la boucle dans son ensemble fonctionne en O(N). À l'intérieur de la boucle, nous avons 4 opérations à temps constant :une comparaison, une recherche dans un tableau, une addition et une incrémentation. Ces quatre opérations se produisent à chaque fois que la boucle s'exécute, nous voudrons donc utiliser la multiplication. Dans l'ensemble, les performances de l'algorithme peuvent être modélisées à l'aide de l'expression suivante :
2O(1) + O(N) * 4O(1)
Ici, nous pouvons isoler le goulot d'étranglement assez facilement. Puisque le plus grand terme d'ordre est O(N), nous pouvons continuer et donner à l'algorithme une note de O(N).
O(N²) Exemple
Enfin, revoyons notre algorithme O(N²).
public static void bubbleSort(int[] numberList) {
int n = numberList.length;
int temp = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j < (n - i); j++) {
if (numberList[j - 1] > numberList[j]) {
temp = numberList[j - 1];
numberList[j - 1] = numberList[j];
numberList[j] = temp;
}
}
}
} Ici, nous avons une complication supplémentaire - une boucle imbriquée. Cela peut compliquer les choses, car nous devons être prudents lorsque nous calculons le nombre total d'itérations. Dans les boucles avec des compteurs, nous devons faire attention à qui itère chaque compteur. Heureusement, les deux compteurs de cet algorithme appartiennent à leurs boucles respectives. Cela rend ce calcul beaucoup plus facile car nous n'avons qu'à faire attention aux conditions de la boucle.
Boucle externe
Dans ce cas, nous commençons par trois opérations à temps constant. Oui, la longueur d'un tableau est accessible en temps constant. C'est une valeur fixe, donc Java la traite essentiellement comme une constante qui peut être récupérée à tout moment. Ensuite, nous tombons dans notre boucle externe. Ici, la condition de boucle est déterminée par la longueur de notre ensemble de données, nous pouvons donc continuer et appeler cette opération O(N).
Boucle interne
Ensuite, nous tombons dans la boucle intérieure qui s'étend également sur la longueur de N (ou plutôt N - 1). Nous pouvons continuer et ignorer la valeur constante puisque la tendance de la boucle est toujours linéaire. En conséquence, la boucle interne a également un taux de croissance de O(N). Alors que se passe-t-il dans cette situation ? Allons-y et établissons l'équation :
3O(1) + O(N) * (O(N) * 5O(1))
Dans ce cas, nous ne pouvons pas dire exactement que cet algorithme s'exécute en temps linéaire. C'est parce que les termes linéaires sont multipliés plutôt qu'additionnés.
Cela dit, les mathématiques ne sont pas essentielles ici. Tout ce que nous avons à faire est d'identifier le goulot d'étranglement qui, dans ce cas, est clairement la boucle imbriquée. Si nous regardons ce qui se passe réellement, nous exécutons une opération linéaire un nombre linéaire de fois. En d'autres termes, nous exécutons N itérations N fois pour un total de N² itérations. En conséquence, nous pouvons donner à cet algorithme une note de O(N²).
Comparaison d'algorithmes
Bon, maintenant nous savons ce qu'est Big O et comment le mesurer, mais comment comparer les algorithmes une fois que nous avons fait notre mesure ? À ce stade, tout est mathématique. Nous devons juste être en mesure de comparer les taux de croissance de diverses fonctions. Cela dit, examinons quelques exemples :
O(N) vs. O(N²)
O(N!) vs. O(2^N)
O(N log(N)) vs. O(N √N)
Nous avons ici trois exemples qui devraient montrer les différentes façons dont nous pouvons comparer les algorithmes.
O(N) contre O(N²)
Pour commencer, regardons-en une à laquelle nous devrions déjà pouvoir répondre rapidement :O(N) vs. O(N²) Avec celui-ci, on peut intuitivement dire que N² croît plus vite que N, mais comment le sait-on ? Une astuce consiste à séparer les termes. Par exemple :O(N) vs. O(N * N) . Maintenant, nous pouvons à peu près simplement annuler les termes en double et regarder ce qui reste. Pour notre exemple, nous nous retrouvons avec un terme N supplémentaire dans O(N²) qui croît beaucoup plus rapidement que le terme constant qui reste dans O(N), donc l'algorithme O(N) est clairement le gagnant.
O(N !) contre O(2^N)
Maintenant, notre deuxième exemple devient un peu plus compliqué. Ici, nous avons une fonction factorielle par rapport à une fonction exponentielle. Sans savoir à l'avance laquelle croît le plus vite, la meilleure façon de le savoir est de convertir chaque fonction en une série et de déterminer laquelle croît le plus vite. Par exemple :
N! = 1 * 2 * 3 * ... * N 2^N = 2 * 2 * 2 * 2 * ... * 2
Maintenant, nous pouvons voir qu'après le deuxième terme, la fonction factorielle dépasse la fonction exponentielle. En fait, nous pouvons même faire un petit plug'n chug pour voir quand la fonction factorielle dépasse la fonction exponentielle.
N = 1 N! = 1 2^N = 2 ------- N = 2 N! = 2 2^N = 4 ------- N = 3 N! = 6 2^N = 8 ------- N = 4 N! = 24 2^N = 16
Au moment où N =4, la fonction factorielle a déjà dépassé la fonction exponentielle. Dans ce cas, nous devrions accrocher l'algorithme avec le taux de croissance exponentiel.
O(N log(N)) contre O(N √N)
Enfin, nous avons notre première comparaison utilisant les logs et les racines carrées. Celui-ci combine quelques astuces d'en haut. Tout d'abord, nous noterons que les deux fonctions ont un facteur N, nous pouvons donc continuer et les ignorer. Ce qui nous intéresse vraiment, c'est la différence entre une racine carrée et un logarithme. L'astuce ici est de reconnaître qu'une racine carrée n'est en réalité qu'une autre fonction exponentielle où la puissance est de ½. Cependant, cela ne signifie pas qu'un O(√N) est mauvais. En fait, c'est en fait mieux que O(N). Le fait qu'il soit toujours exponentiel est ce qui le rend pire que O(log(N)). Allons de l'avant et faisons quelques plug'n chug pour le prouver.
N = 1 log(1) = 0 √1 = 1 ------- N = 2 log(2) = 0.30102999566 √2 = 1.41421356237
Au moment où notre ensemble de données atteint une valeur de deux, la fonction racine carrée a déjà pris le relais. En fin de compte, nous prendrons l'algorithme O(N log(N)).
Implications de Big O
Bien sûr, pourquoi Big O est-il important ? Les ordinateurs d'aujourd'hui sont si rapides que nous remarquerions à peine la différence avec un petit ensemble de données. Mais ce n'est que le problème ! Nous avons tendance à supposer de petits ensembles de données lorsque nous commençons un projet. Au moment où l'ensemble de données est suffisamment volumineux pour avoir un impact sur le projet, nous avons déjà renoncé à l'optimisation. Au fil du temps, notre ensemble de données s'agrandit et nous commençons à rencontrer de sérieux problèmes. Ensuite, nous devons revenir en arrière et identifier le goulot d'étranglement. Parfois, c'est facile. La plupart du temps, ce n'est pas le cas.
Au fur et à mesure que nous avancerons dans les différentes structures de données, nous reviendrons sur ce concept. En fait, cela deviendra assez important au fur et à mesure que nous jouerons avec les fonctionnalités de chaque structure de données. Ce sera également un sujet de discussion principal lorsque nous aborderons les algorithmes de tri. À la fin de cette série, nous devrions être assez à l'aise pour parler des performances et de la complexité des algorithmes.
Si vous voulez prendre une longueur d'avance, je vous recommande de jeter un coup d'œil à la feuille de triche Big O. C'est une excellente référence si vous recherchez un guichet unique pour toutes les différentes structures de données et leurs performances associées. Ce ne sera pas super utile tout de suite, mais c'est un bon outil à avoir sous la main.
