Big O Notation : qu'est-ce que c'est et pourquoi est-ce important ?

C'est amusant! Communiquer avec Big O est l'une des premières transitions qui font fondre le visage pour les développeurs en début de carrière.

Voyons pourquoi.

Mais d'abord, un arrêt au stand. Vous souvenez-vous de ces problèmes de mots absolument ridicules de l'école primaire ?

Sally est allée à l'épicerie et a acheté 37 pastèques. Elle avait 20 dollars. Chaque pastèque coûte 0,70 $. Combien d'argent Sally a-t-elle quand elle rentre à la maison ?

Vous êtes-vous demandé : « Comment Sally va-t-elle pouvoir rentrer à la maison ? Avec 37 pastèques ?

Stupide Sally.

Certaines personnes disent que c'est perdre la forêt pour les arbres. Je dis que c'est juste une façon terriblement paresseuse de construire des problèmes pratiques.

Le but de Big O Notation est de pouvoir parler, littéralement communiquer avec d'autres personnes , d'une qualité de notre métier. L'accent particulier ici est de permettre la comparaison entre les solutions dans le scénario le plus défavorable à mesure que la taille de l'entrée augmente.

On veut pouvoir parler de solutions potentielles (la même chose que de dire : algorithmes ) dans l'abstrait. C'est un point crucial : dans l'abstrait . Nous ne nous soucions pas du tout des données dont nous disposons . Lorsque nous jouons avec ces idées, nous supposons un ensemble de données théoriquement gigantesque, mais fini.

Quand on pense aux données dont on dispose , c'est raisonner dans le concret. Quand on pense à Big O Notation, on raisonne dans l'abstrait. Il est FACILE de se rabattre sur un raisonnement concret. C'est là que nous passons la majeure partie de notre vie. C'est facile, généralement évident et confortable.

Dois-je traverser la rue maintenant ? Y a-t-il une voiture ? Non? OK, croix.

Ne le faites pas lorsque vous raisonnez dans l'abstrait !

Définitions, rapidement

Ça vous dérange si je vous fais une faveur ici ? Il y a un tas de termes mathématiques qui pourraient également gêner. Voici un visuel, dans l'ordre, du meilleur des cas au pire, pour certains termes courants de Big O. Nous en avons besoin pour pouvoir réfléchir et apprendre au lieu de rester bloqués sur la terminologie.

O(1) - "Temps constant"

Peu importe la taille de l'entrée, le système renvoie toujours le résultat dans le même laps de temps.

O(log n) - "Heure du journal"

Au fur et à mesure que la solution (ou l'algorithme) itère sur l'entrée, chaque itération devient plus rapide !

O(n) - "Temps linéaire"

Au fur et à mesure que l'algorithme itère, chaque itération prend le même temps que l'itération précédente.

O(n log n) - pas de terminologie sophistiquée ici

Montre que les idées peuvent être combinées (yikes). Au fur et à mesure que nous itérons, chaque itération devient plus lente mais ralentit assez lentement.

O(n^2) - "n au carré"

Pour chaque itération, les itérations ralentissent assez rapidement.

O(n!) - "n factoriel"

Pour chaque itération, les itérations deviennent plus lentes super rapides.

Le but est d'essayer de rester le plus loin possible de "n factoriel" et d'essayer de ne pas devenir bien pire que Constant.

Avec tout cela compris, essayons maintenant de combler le fossé.

Combler le fossé entre la pensée concrète et la pensée abstraite

Comprendre la notation Big O

La notation Big O est utilisée pour décrire les performances ou la complexité d'un algorithme (solution). Il fournit une compréhension de haut niveau de la façon dont un algorithme (solution) fonctionnera à mesure que la taille de l'entrée augmente.

Par exemple, un algorithme de complexité O(n) verra son temps d'exécution augmenter linéairement avec la taille de l'entrée.

Pensée concrète vs abstraite

Le défi survient lorsque les développeurs confondent le raisonnement sur des données spécifiques avec un raisonnement sur l'algorithme lui-même. Des phrases comme "mais ces données sont réelles" peuvent signaler cette confusion.

Bien que le raisonnement sur les données réelles puisse vous aider à démarrer, il est essentiel de séparer la solution de l'entrée actuelle.

Pourquoi le malentendu ?

Les développeurs en début de carrière peuvent faire cette erreur en raison d'un manque d'expérience avec des problèmes à plus grande échelle ou d'être trop absorbés par les spécificités d'un problème actuel. Il est essentiel de séparer les détails concrets de la complexité abstraite pour créer des solutions évolutives.

Conséquences pratiques

Lorsque l'entrée augmente de 100 ou 100 000 fois, qu'arrive-t-il à l'algorithme ? Une complexité de solution incroyablement complexe peut s'effondrer avec un ensemble de données plus volumineux.

Un algorithme qui semble correct pour de petits ensembles de données peut échouer de manière spectaculaire avec des plus grands, entraînant des problèmes de performances et d'autres défis.

Apprendre à penser dans l'abstrait

Développer la capacité de penser abstraitement aux problèmes nécessite de la pratique et des conseils. Certaines stratégies incluent :

• Création de modèles abstraits : Représentation des problèmes de manière généralisée.

• Analyser les algorithmes séparément des données : évaluer le comportement de l'algorithme indépendamment de points de données spécifiques.

• Construire des scénarios de mise à l'échelle : imaginer comment l'algorithme fonctionnera avec différentes tailles d'entrée.

La pensée abstraite en général, et la notation Big O en particulier, sont des compétences essentielles dans la conception d'algorithmes - en d'autres termes, trouver une solution à un problème.

En apprenant à séparer la complexité des problèmes de la complexité des algorithmes , les développeurs peuvent éviter les pièges courants et améliorer leurs capacités de résolution de problèmes lorsqu'ils travaillent seuls ET améliorer considérablement leur capacité à travailler avec d'autres personnes qui ont également investi du temps pour apprendre à communiquer de cette façon.

Les problèmes complexes n'exigent pas souvent des solutions complexes. (Sally n'avait probablement pas besoin de 37 pastèques pour commencer… qu'est-ce qu'elle va faire avec 37 pastèques ?!)