human
-> Big O Notation, peu importe ce que je lis ou combien de personnes me l'expliquent, je n'obtiens toujours pas ce que c'est sur terre !Expliquez comme si j'avais cinq ans.
gpt
Essayons une explication intuitive plutôt que mathématique.Des généralisations, des déclarations de balayage et des simplifications excessives seront faites: imaginez que vous voulez alphabétiser votre collection de cartes de baseball.Il devrait être facile de voir que si vous n'avez que 3 cartes, vous pouvez résoudre ce problème beaucoup plus rapidement que si vous en avez 3000.Imaginez maintenant que vous n'avez toujours pas organisé votre collection et que vous souhaitez vérifier si vous avez Albert Pujols quelque part dans votre pile de cartes.Encore une fois, si vous n'avez que 3 cartes, vous pouvez trouver la réponse à ce problème rapidement;Mais si vous en avez 3000, cela pourrait vous prendre tout l'après-midi.Beaucoup de problèmes, ceux intéressants que les mathématiciens aiment étudier, sont comme ça - plus l'ensemble des choses que vous devez examiner pour résoudre un problème particulier (que nous appelons cela la «contribution» au problème),Plus il faudra longtemps pour résoudre.* * Big - O Notation vise à vous donner une idée de combien de temps il faudra pour résoudre un problème à mesure que l'entrée devient de plus en plus grande.* * Remarquez que je n'ai pas dit "combien de temps" cela prend, mais * combien de temps cela prend * pour chaque élément supplémentaire que vous ajoutez à l'entrée.Big - o La notation dit "à mesure que l'entrée devient plus grande, le temps nécessaire pour résoudre le problème augmentera de * * pas plus * * que ce facteur ici." Revenant au problème de Pujols, la seule façon de le résoudre est deRegardez chaque carte de la pile.Bien sûr, nous pourrions avoir de la chance et trouver la carte que nous recherchons dans le premier essai, mais dans le pire - un scénario de cas que nous le trouverons mort en dernier ou ne le trouverons pas du tout;Nous devons juste regarder chaque carte pour être sûr que nous avons la bonne réponse.Si regarder une carte prend 1 seconde, regarder trois cartes prendra 3 secondes, mais regarder trois mille cartes prendra 3000 secondes.Ainsi, pour résoudre le problème Pujols, il faudra un temps constant (par exemple, 1 seconde) pour chaque élément de l'entrée (par exemple, 3000 cartes).Classiquement, nous appelons la taille de l'entrée * n *, donc la durée totale pour trouver des pujols dans une pile de cartes non triée est * n \ * 1sec *.Étant donné que la 1 seconde est constante, la seule chose affectant vraiment combien de temps il faut pour résoudre le problème à mesure que * n * devient plus grand, est * n * lui-même, nous disons donc que le problème des pujols est * o (n) * (prononcé"Big - o de * n *" ou alternativement "commander * n *.") Maintenant, imaginez que je vous ai demandé de trouver la carte Pujols * * après * * Vous avez alphabétisé les 3000 cartes de votre collection.C'est un problème beaucoup plus rapide à résoudre !Tournez simplement vers la section "P" de votre classeur de carte et regardez chaque carte.Si se tourner vers la bonne page prend 5 secondes et chaque section dans le classeur contient au plus 200 cartes (rappelez-vous, regarder une carte prend 1 seconde), le pire - Scénario de cas pour trouver des pujols prendra * 5sec + (200 \ * 1sec) = * * * 205 secondes * * (vous pouvez réellement rendre cela plus rapide, mais je ne vais pas y entrer. Google "Recherche binaire").Vous pourriez avoir 200 cartes, ou vous pourriez avoir 5000 cartes et cela prendrait toujours 205 secondes dans le pire des cas, généralement beaucoup plus rapidement.Ainsi, en alphabétisant et en indexant (les informaticiens appelleraient ce "hachage") votre collection, vous avez essentiellement rendu la taille de l'entrée sans pertinence, nous pouvons maintenant résoudre le problème Pujols dans le pire du cas constant.Dans la notation Big - O, nous dénotons ce * o (1) *, ce qui est comme dire "Ajout d'éléments à l'entrée multiplie le temps nécessaire pour résoudre le problème par un facteur de * 1 *" - pas du tout l'augmentation du temps.D'autres problèmes peuvent répondre différemment à l'augmentation de * n *, vous verrez donc des choses comme * o (log n), o (n log n), o (n ^ 2), o (2 ^ n) * et de nombreuses autres variations.La chose importante à retenir est que la fonction entre la parenthèse vous donne une limite supérieure à la vitesse à laquelle le temps de résoudre un problème augmente à mesure que la taille de l'entrée augmente.Le temps pourrait toujours devenir plus lent que ce que dit la notation Big - O, mais jamais plus vite.