Big-O pour les enfants de huit ans ?

Question

Je m'interroge davantage sur ce que cela signifie pour mon code. Je comprends les concepts mathématiques, mais j'ai du mal à comprendre ce qu'ils signifient sur le plan conceptuel. Par exemple, si l'on effectue une opération O(1) sur une structure de données, je comprends que le nombre d'opérations qu'elle doit effectuer n'augmentera pas parce qu'il y a plus d'éléments. Et une opération O(n) signifierait que l'on effectue un ensemble d'opérations sur chaque élément. Quelqu'un pourrait-il combler cette lacune ?

• Par exemple, que ferait exactement une opération O(n^2) ?
• Et que diable signifie qu'une opération est O(n log(n)) ?
• Et faut-il fumer du crack pour écrire un O(x !)?

Answer 1

Une façon de voir les choses est la suivante :

O(N^2) signifie que pour chaque élément, vous faites quelque chose avec chaque autre élément, par exemple en les comparant. Le tri à bulles en est un exemple.

O(N log N) signifie que pour chaque élément, vous faites quelque chose qui ne nécessite que l'examen de log N des éléments. C'est généralement parce que vous savez quelque chose sur les éléments qui vous permet de faire un choix efficace. La plupart des tris efficaces en sont un exemple, comme le tri par fusion.

O(N !) signifie faire quelque chose pour toutes les permutations possibles des N éléments. Le voyageur de commerce en est un exemple, où il existe N ! façons de visiter les nœuds, et la solution de force brute consiste à examiner le coût total de chaque permutation possible pour trouver la solution optimale.

Answer 2

Ce que la notation Big-O signifie pour votre code, c'est la façon dont il évoluera lorsque vous doublerez le nombre de "choses" sur lesquelles il opère. Voici un exemple concret :

Big-O       |  computations for 10 things |  computations for 100 things
----------------------------------------------------------------------
O(1)        |   1                         |     1
O(log(n))   |   3                         |     7
O(n)        |  10                         |   100
O(n log(n)) |  30                         |   700
O(n^2)      | 100                         | 10000

Prenez quicksort qui est O(n log(n)) contre bubble sort qui est O(n^2). Pour trier 10 choses, quicksort est 3 fois plus rapide que le tri à bulles. Mais pour un tri de 100 éléments, il est 14 fois plus rapide ! Il est donc important de choisir l'algorithme le plus rapide. Quand vous arrivez à des bases de données de plusieurs millions de lignes, cela peut faire la différence entre une requête exécutée en 0,2 seconde et une requête qui prend des heures.

Un autre élément à prendre en compte est qu'un mauvais algorithme est une chose que la loi de Moore ne peut pas arranger. Par exemple, si vous avez un calcul scientifique qui est O(n^3) et qu'il peut calculer 100 choses par jour, doubler la vitesse du processeur ne vous donne que 125 choses par jour. Cependant, si vous réduisez ce calcul à O(n^2), vous ferez 1000 choses par jour.

clarification : En fait, Big-O ne parle pas des performances comparatives de différents algorithmes au même point de taille spécifique, mais plutôt des performances comparatives du même algorithme à différents points de taille :

                 computations     computations       computations
Big-O       |   for 10 things |  for 100 things |  for 1000 things
----------------------------------------------------------------------
O(1)        |        1        |        1        |         1
O(log(n))   |        1        |        3        |         7
O(n)        |        1        |       10        |       100
O(n log(n)) |        1        |       33        |       664
O(n^2)      |        1        |      100        |     10000

Answer 3

Vous pourriez trouver utile de le visualiser :

En outre, le LogY/LogX mettre à l'échelle les fonctions n 1/2 , n, n 2 ressemblent toutes à lignes droites tandis que le LogY/X échelle 2 n , e n , 10 n sont des lignes droites et n ! est linéarithmique (ressemble à n log n ).

Answer 4

C'est peut-être trop mathématique, mais voici mon essai. (I Je suis un mathématicien).

Si quelque chose est O( f ( n )), alors c'est le temps d'exécution sur n seront égaux à A f ( n ) + B (mesurée, par exemple, en cycles d'horloge ou en opérations du processeur). Il est essentiel de comprendre que vous avez également ces constantes A y B qui découlent de la mise en œuvre spécifique. B représente essentiellement les "frais généraux constants" de votre opération, par exemple un prétraitement que vous effectuez et qui ne dépend pas de la taille de la collection. A représente la vitesse de votre algorithme de traitement des articles.

La clé, cependant, c'est d'utiliser la notation du grand O pour déterminer le degré d'évolutivité d'un produit . Ces constantes n'ont donc pas vraiment d'importance : si vous essayez de comprendre comment passer de 10 à 10 000 éléments, qui se soucie de la constante de surcharge ? B ? De même, d'autres préoccupations (voir ci-dessous) l'emporteront certainement sur le poids de la constante multiplicative A .

Donc la vraie affaire est f ( n ). Si f ne se développe pas du tout avec n par exemple f ( n ) = 1, alors vous vous adapterez fantastiquement - votre temps d'exécution sera toujours juste de A + B . Si f croît linéairement avec n c'est-à-dire f ( n ) = n Si vos utilisateurs attendent 10 ns pour 10 éléments, ils attendront 10000 ns pour 10000 éléments (en ignorant la constante additive). Mais s'il augmente plus rapidement, comme n 2 alors vous êtes dans le pétrin ; les choses commenceront à ralentir beaucoup trop lorsque vous aurez des collections plus importantes. f ( n ) = n log( n ) est généralement un bon compromis : votre opération ne peut pas être simple au point de donner une mise à l'échelle linéaire, mais vous avez réussi à réduire les choses de telle sorte que la mise à l'échelle sera bien meilleure que celle de f ( n ) = n 2 .

En pratique, voici quelques bons exemples :

• O(1) : récupérer un élément d'un tableau. Nous savons exactement où il se trouve en mémoire, alors nous allons le chercher. Peu importe que la collection ait 10 éléments ou 10 000 ; il est toujours à l'index (disons) 3, donc nous sautons simplement à l'emplacement 3 en mémoire.
• O( n ) : récupération d'un élément dans une liste chaînée. Ici, A \= 0,5, car en moyenne, vous devrez parcourir la moitié de la liste chaînée avant de trouver l'élément que vous recherchez.
• O( n 2 ) : divers algorithmes de tri "muets". Car généralement leur stratégie consiste, pour chaque élément ( n ), vous regardez tous les autres éléments (donc fois un autre n donnant n 2 ), alors positionnez-vous au bon endroit.
• O( n log( n )) : divers algorithmes de tri "intelligents". Il s'avère que vous n'avez besoin de regarder, disons, que 10 éléments dans un groupe de 10 éléments. 10 -pour se trier intelligemment par rapport aux éléments suivants tout le monde autre dans la collection. Parce que tous les autres sont également va regarder 10 éléments, et le comportement émergent est orchestré juste comme il faut pour que cela soit suffisant pour produire une liste triée.
• O( n !) : un algorithme qui "essaie tout", puisqu'il y a (proportionnellement à) n ! les combinaisons possibles de n des éléments susceptibles de résoudre un problème donné. Il passe donc en revue toutes les combinaisons possibles, les essaie et s'arrête dès qu'il réussit.

Answer 5

La réponse de don.neufeld est très bonne, mais je l'expliquerais probablement en deux parties : tout d'abord, il existe une hiérarchie approximative de O() dans laquelle la plupart des algorithmes s'inscrivent. Ensuite, vous pouvez examiner chacun d'entre eux pour obtenir des esquisses de ce que vous pouvez faire. typique Les algorithmes de cette complexité temporelle le font.

Pour des raisons pratiques, les seuls O() qui semblent avoir de l'importance sont les suivants :

• O(1) "temps constant" - le temps requis est indépendant de la taille de l'entrée. En tant que catégorie approximative, j'inclurais ici des algorithmes tels que les recherches de hachage et les recherches d'union, même si aucun d'entre eux n'est réellement O(1).
• O(log(n)) "logarithmique" - il devient plus lent avec des entrées plus grandes, mais une fois que votre entrée est assez grande, il ne changera pas assez pour s'en inquiéter. Si votre temps d'exécution est correct avec des données de taille raisonnable, vous pouvez le submerger avec autant de données supplémentaires que vous le souhaitez et il sera toujours correct.
• O(n) "linéaire" - plus l'entrée est importante, plus le temps est long, dans un compromis équilibré. Trois fois la taille de l'entrée prendront environ trois fois plus de temps.
• O(n log(n)) "mieux que quadratique" - l'augmentation de la taille de l'entrée fait mal, mais c'est encore gérable. L'algorithme est probablement décent, c'est juste que le problème sous-jacent est plus difficile (les décisions sont moins localisées par rapport aux données d'entrée) que les problèmes qui peuvent être résolus en temps linéaire. Si la taille de vos données d'entrée augmente, ne supposez pas que vous pourriez nécessairement gérer une taille deux fois plus grande sans modifier votre architecture (par exemple en déplaçant les choses vers des calculs par lots la nuit, ou en ne faisant pas les choses par image). Il n'y a pas de problème si la taille de l'entrée augmente un peu, cependant ; faites juste attention aux multiples.
• O(n^2) "quadratique" - cela ne fonctionnera vraiment que jusqu'à une certaine taille de votre entrée, alors faites attention à la taille qu'elle pourrait atteindre. De même, votre algorithme peut être nul - réfléchissez bien pour voir s'il existe un algorithme O(n log(n)) qui vous donnerait ce dont vous avez besoin. Une fois que vous êtes ici, soyez très reconnaissant pour l'incroyable matériel dont nous avons été dotés. Il n'y a pas si longtemps, ce que vous essayez de faire aurait été impossible à toutes fins pratiques.
• O(n^3) "cubique" - pas qualitativement si différent de O(n^2). Les mêmes commentaires s'appliquent, mais en plus grand nombre. Il y a une bonne chance qu'un algorithme plus intelligent puisse réduire ce temps à quelque chose de plus petit, par exemple O(n^2 log(n)) ou O(n^2.8...), mais là encore, il y a une bonne chance que cela ne vaille pas la peine. (Vous êtes déjà limité dans votre taille d'entrée pratique, donc les facteurs constants qui peuvent être nécessaires pour les algorithmes plus intelligents vont probablement écraser leurs avantages pour les cas pratiques. De plus, la réflexion est lente ; laisser l'ordinateur la mastiquer peut vous faire gagner du temps dans l'ensemble).
• O(2^n) "exponentiel" - soit le problème est fondamentalement difficile à calculer, soit vous êtes un idiot. Ces problèmes ont une saveur reconnaissable. La taille de vos données d'entrée est plafonnée à une limite stricte assez spécifique. Vous saurez rapidement si vous entrez dans cette limite.

Et c'est tout. Il existe de nombreuses autres possibilités qui se situent entre celles-ci (ou qui sont supérieures à O(2^n)), mais elles ne se produisent pas souvent dans la pratique et elles ne sont pas qualitativement très différentes de l'une d'entre elles. Les algorithmes cubiques sont déjà un peu exagérés ; je ne les ai inclus que parce que je les ai rencontrés assez souvent pour qu'ils méritent d'être mentionnés (par exemple, la multiplication de la matrice).

Que se passe-t-il réellement pour ces classes d'algorithmes ? Je pense que vous avez bien commencé, bien qu'il existe de nombreux exemples qui ne correspondent pas à ces caractérisations. Mais pour ce qui est de ce qui précède, je dirais que cela se passe généralement comme suit :

• O(1) - vous ne regardez au maximum qu'un morceau de taille fixe de vos données d'entrée, et peut-être aucun. Exemple : le maximum d'une liste triée.
  • Ou la taille de votre entrée est limitée. Exemple : addition de deux nombres. (Notez que l'addition de N nombres est un temps linéaire).
• O(log n) - chaque élément de votre entrée vous en dit suffisamment pour ignorer une grande partie du reste de l'entrée. Exemple : lorsque vous regardez un élément de tableau dans une recherche binaire, sa valeur vous indique que vous pouvez ignorer la "moitié" de votre tableau sans en regarder aucun. De même, l'élément que vous regardez vous donne un résumé suffisant d'une fraction de l'entrée restante pour que vous n'ayez pas besoin de le regarder.
  • Les moitiés n'ont rien de spécial, cependant - si vous ne pouvez ignorer que 10 % de votre entrée à chaque étape, c'est toujours logarithmique.
• O(n) - vous effectuez une quantité fixe de travail par élément d'entrée. (Mais voir ci-dessous).
• O(n log(n)) - il existe quelques variantes.
  • Vous pouvez diviser l'entrée en deux piles (en un temps linéaire maximum), résoudre le problème indépendamment sur chaque pile, puis combiner les deux piles pour former la solution finale. L'indépendance des deux piles est essentielle. Exemple : mergesort récursif classique.
  • Chaque passage en temps linéaire sur les données vous amène à mi-chemin de votre solution. Exemple : quicksort si vous pensez en termes de distance maximale de chaque élément à sa position finale triée à chaque étape de partitionnement (et oui, je sais que c'est en fait O(n^2) à cause des choix de pivot dégénérés. Mais pratiquement parlant, cela tombe dans ma catégorie O(n log(n))).
• O(n^2) - vous devez examiner chaque paire d'éléments d'entrée.
  • Ou vous ne le faites pas, mais vous pensez le faire, et vous utilisez le mauvais algorithme.
• O(n^3) - hum... Je n'ai pas une caractérisation rapide de ceux-ci. C'est probablement l'un de :
  • Vous multipliez des matrices
  • Vous regardez chaque paire d'entrées mais l'opération que vous faites nécessite de regarder à nouveau toutes les entrées.
  • la structure graphique entière de votre entrée est pertinente
• O(2^n) - vous devez considérer chaque sous-ensemble possible de vos entrées.

Aucune d'entre elles n'est rigoureuse. Surtout pas les algorithmes en temps linéaire (O(n)) : Je pourrais trouver un certain nombre d'exemples où il faut examiner toutes les entrées, puis la moitié d'entre elles, puis la moitié de celles-ci, etc. Ou l'inverse : on réunit des paires d'entrées, puis on récure sur la sortie. Cela ne correspond pas à la description ci-dessus, puisque vous ne regardez pas chaque entrée une seule fois, mais le temps de calcul reste linéaire. Pourtant, dans 99,2% des cas, le temps linéaire signifie que l'on ne regarde chaque entrée qu'une seule fois.