J'ai entendu plusieurs fois que pour des valeurs suffisamment petites de n, O (n) peut être pensé / traité comme si c'était O (1).

Exemple :

La motivation pour le faire est basée sur l'idée incorrecte que O (1) est toujours meilleure que O (lg n), est toujours meilleure que O (n). L'ordre asymptotique d'une opération n'est pertinent que si, dans des conditions réalistes, la taille du problème devient réellement importante. Si n reste petit, alors chaque problème est O (1)!

Qu'est-ce qui est suffisamment petit? dix? 100? 1000? À quel moment dites-vous "nous ne pouvons plus traiter cela comme une opération gratuite"? Y a-t-il une règle d'or?

Il semble que cela puisse être spécifique à un domaine ou à un cas, mais existe-t-il des règles générales sur la façon de penser à ce sujet?

Tous les ordres de grandeur impliquent un constant , plusieurs d'entre eux en fait. Lorsque le nombre d'éléments est suffisamment grand, cette constante n'a pas d'importance. La question est de savoir si le nombre d'éléments est suffisamment petit pour que cette constante domine.$C$

Voici une façon visuelle d'y penser.

Tous ont une constante de démarrage qui détermine leur point de départ sur l'axe Y. Chacun a également une constante critique dominant la vitesse à laquelle ils augmenteront.$C$

• Pour , C détermine le temps.$O(1)$$C$
• est vraiment C × n , où C détermine l'angle.$O(n)$$C \times n$$C$
• est en réalité ( C × n ) 2 , où C détermine la netteté de la courbe.$O(n^2)$$(C \times n)^2$$C$

Pour déterminer quel algorithme vous devez utiliser, vous devez estimer l'endroit où les temps d'exécution se croisent. Par exemple, une solution avec un temps de démarrage élevé ou un C élevé perdra au profit d'une solution O ( n ) avec un temps de démarrage faible et un C faible pour un nombre d'éléments relativement important.$O(1)$$C$$O(n)$$C$

Voici un exemple réel. Vous devez déplacer un tas de briques à travers une cour. Vous pouvez les déplacer quelques-unes à la fois avec vos mains, ou aller chercher une énorme rétrocaveuse lente pour les soulever et les conduire en un seul voyage. Quelle est votre réponse s'il y a trois briques? Quelle est votre réponse s'il y en a trois mille?

Voici un exemple CS. Disons que vous avez besoin d'une liste qui est toujours triée. Vous pouvez utiliser un arbre qui se maintiendra dans l'ordre pour . Ou vous pouvez utiliser une liste non triée et trier à nouveau après chaque insertion ou suppression à O ( n log n ) . Parce que les opérations d'arborescence sont compliquées (elles ont une constante élevée) et que le tri est si simple (constante faible), la liste gagnera probablement des centaines ou des milliers d'éléments.$O(\log{n})$$O(n \log{n})$

Vous pouvez observer ce genre de chose, mais en fin de compte, l'analyse comparative est ce qui le fera. Vous devez également surveiller le nombre d'articles que vous aurez généralement et atténuer le risque d'être remis plus. Vous aurez également besoin de documenter votre hypothèse comme «les performances se dégraderont rapidement sur éléments» ou «nous supposons une taille maximale définie de X ».$X$$X$

Étant donné que ces exigences sont susceptibles de changer, il est important de mettre ce type de décisions derrière une interface. Dans l'exemple d'arborescence / liste ci-dessus, n'exposez pas l'arborescence ou la liste. De cette façon, si vos hypothèses s'avèrent fausses ou si vous trouvez un meilleur algorithme, vous pouvez changer d'avis. Vous pouvez même faire un hybride et changer dynamiquement d'algorithmes à mesure que le nombre d'éléments augmente.

Cela s'appuie en grande partie sur les réponses déjà publiées, mais peut offrir une perspective différente.

Il est révélateur que la question traite de "valeurs suffisamment petites de n ". L'intérêt de Big-O est de décrire comment le traitement se développe en fonction de ce qui est en cours de traitement. Si les données en cours de traitement restent petites, il n'est pas pertinent de discuter du Big-O, car vous n'êtes pas intéressé par la croissance (ce qui ne se produit pas).

Autrement dit, si vous parcourez une distance très courte dans la rue, il peut être tout aussi rapide de marcher, d'utiliser un vélo ou de conduire. Il peut même être plus rapide de marcher s'il vous faudra du temps pour trouver vos clés de voiture, ou si votre voiture a besoin d'essence, etc.

Pour les petits n , utilisez ce qui vous convient.

Si vous faites un voyage à travers le pays, vous devez chercher des moyens d'optimiser votre conduite, votre consommation d'essence, etc.

La citation est plutôt vague et imprécise. Il y a au moins trois façons connexes d'interpréter ce texte.

Le point mathématique littéral derrière cela est que, si vous n'êtes intéressé que par des instances de taille jusqu'à une certaine limite, il n'y a qu'un nombre fini d'instances possibles. Par exemple, il n'y a qu'un nombre fini de graphiques sur une centaine de sommets. S'il n'y a qu'un nombre fini d'instances, vous pouvez, en principe, résoudre le problème en construisant simplement une table de recherche de toutes les réponses à toutes les instances possibles. Maintenant, vous pouvez trouver la réponse en vérifiant d'abord que l'entrée n'est pas trop grande (ce qui prend un temps constant: si l'entrée est plus longue que  $k$, il n'est pas valide), puis recherchez la réponse dans le tableau (ce qui prend un temps constant: il y a un nombre fixe d'entrées dans le tableau). Notez, cependant, que la taille réelle de la table est probablement incroyablement grande. J'ai dit qu'il n'y a qu'un nombre fini de graphes sur cent sommets et c'est vrai. C'est juste que le nombre fini est plus grand que le nombre d'atomes dans l'univers observable.

Un point plus pratique est que, lorsque nous disons que le temps d' exécution d'un algorithme est , cela signifie seulement qu'il est asymptotiquement c n 2  étapes, pour une constante  C . Autrement dit, il y a une constante n 0 telle que, pour tout n ≥ n 0 , l'algorithme prend environ c n 2 étapes. Mais peut-être que n 0 = 100 , 000 , $\Theta(n^2)$ $cn^2$$C$$n_0$$n\geq n_0$$cn^2$$n_0=100,000,000$et vous n'êtes intéressé que par des instances de taille beaucoup plus petite que cela. La limite quadratique asymptotique pourrait même ne pas s'appliquer à vos petites instances. Vous pourriez être chanceux et cela pourrait être plus rapide sur de petites entrées (ou vous pourriez ne pas être chanceux et le faire ralentir). Par exemple, pour les petits  , n 2 < 1000 n , vous préférez exécuter un algorithme quadratique avec de bonnes constantes qu'un algorithme linéaire avec de mauvaises constantes. Un exemple concret de ceci est que les algorithmes de multiplication matricielle asymptotiquement les plus efficaces (variantes de Coppersmith – Winograd , fonctionnant dans le temps O ( n 2.3729 ) ) sont rarement utilisés dans la pratique parce que Strassen$n$$n^2 < 1000n$$O(n^{2.3729})$ algorithme est plus rapide à moins que vos matrices ne soient vraiment grandes.$O(n^{2.8074})$

Un troisième point est que, si  est petit, n 2 et même n 3  sont petits. Par exemple, si vous avez besoin de trier quelques milliers d'éléments de données et que vous ne devez les trier qu'une seule fois, tout algorithme de tri est assez bon: a Θ ( n 2$n$$n^2$$n^3$$\Theta(n^2)$l'algorithme n'aura encore besoin que de quelques dizaines de millions d'instructions pour trier vos données, ce qui ne prend pas beaucoup de temps sur un processeur capable d'exécuter des milliards d'instructions par seconde. OK, il y a aussi des accès à la mémoire, mais même un algorithme lent prendra moins d'une seconde, il est probablement préférable d'utiliser un algorithme simple et lent et de bien faire les choses plutôt que d'utiliser un algorithme complexe et rapide et de constater qu'il est ultra-rapide mais bogué et ne trie pas correctement les données.

La notation Big-O ne dit vraiment que le comportement du grand arbitraire n. Par exemple, signifie qu'il existe une constante c> 0 et un entier n 0 tel que f ( n ) < c n 2 pour chaque n > n 0 .$f (n) = O (n^2)$$n_0$$f (n) < c n^2$$n > n_0$

Dans de nombreux cas, vous pouvez trouver une constante c et dire "Pour chaque n> 0, f (n) est approximativement ". Ce sont des informations utiles à avoir. Mais dans certains cas, ce n'est pas vrai. Si f (n) = n 2 + 10 18 , cela est totalement trompeur. Donc, ce n'est pas parce que quelque chose est O (n ^ 2) que vous pouvez éteindre votre cerveau et ignorer la fonction réelle.$c n^2$$n^2 + 10^{18}$

D'un autre côté, si vous ne rencontrez que les valeurs n = 1, 2 et 3, alors dans la pratique, cela ne fait aucune différence ce que f (n) fait pour n ≥ 4, vous devriez donc aussi considérer que f ( n) = O (1), avec c = max (f (1), f (2), f (3)). Et c'est ce que signifie suffisamment petit: si l'affirmation que f (n) = O (1) ne vous induit pas en erreur si les seules valeurs de f (n) que vous rencontrez sont "suffisamment petites".

Si ça ne pousse pas, c'est O (1)

La déclaration de l'auteur est un peu axiomatique.

Les ordres de croissance décrivent ce qui arrive à la quantité de travail que vous devez faire en Naugmentant. Si vous savez que cela Nn'augmente pas, votre problème est efficace O(1).

N'oubliez pas que O(1)cela ne signifie pas «rapide». Un algorithme qui nécessite toujours 1 trillion d'étapes pour terminer est O(1). Un algorithme qui prend de 1 à 200 étapes, mais jamais plus, l'est O(1). [1]

Si votre algorithme prend exactement des N ^ 3étapes et que vous savez que Ncela ne peut pas dépasser 5, il ne peut jamais dépasser 125 étapes, c'est donc efficace O(1).

Mais encore une fois, O(1)ne signifie pas nécessairement «assez vite». C'est une question distincte qui dépend de votre contexte. Si cela prend une semaine pour terminer quelque chose, vous ne vous souciez probablement pas si c'est techniquement O(1).

[1] Par exemple, la recherche dans un hachage est O(1), même si les collisions de hachage signifient que vous devrez peut-être parcourir plusieurs éléments dans un même compartiment, tant qu'il existe une limite stricte sur le nombre d'éléments pouvant être dans ce compartiment.

Maintenant, je peux utiliser une table de hachage et avoir des recherches O (1) (en laissant de côté l'implémentation spécifique de la table de hachage), mais si j'avais par exemple une liste, j'aurais des recherches O (n). Compte tenu de cet axiome, ces deux sont les mêmes si les collections sont suffisamment petites. Mais à un moment donné, ils divergent ... quel est ce point?

En pratique, c'est le point où la construction de la table de hachage prend plus que l'avantage que vous retirez des recherches améliorées. Cela variera beaucoup en fonction de la fréquence à laquelle vous effectuez la recherche, par rapport à la fréquence à laquelle vous effectuez d'autres choses. O (1) vs O (10) n'est pas un gros problème si vous le faites une fois. Si vous le faites des milliers de fois par seconde, même cela compte (bien qu'au moins, cela compte à un rythme croissant de façon linéaire).

Bien que la citation soit vraie (mais vague), elle comporte également des dangers. Imo, vous devriez regarder la complexité à n'importe quelle étape de votre application.

C'est trop facile à dire: hé, je n'ai qu'une petite liste, si je veux vérifier si l'élément A est dans la liste, je vais simplement écrire une boucle facile pour parcourir la liste et comparer les éléments.

Ensuite, votre copain programmeur doit utiliser la liste, voit votre fonction et est comme: hé je ne veux pas de doublons dans la liste, donc il utilise la fonction pour chaque élément ajouté à la liste.

(attention, c'est toujours un petit scénario de liste.)

3 ans plus tard, j'arrive et mon patron vient de faire une grosse vente: notre logiciel va être utilisé par un grand détaillant national. Avant, nous ne desservions que les petits magasins. Et maintenant, mon patron vient à moi en jurant et en criant, pourquoi le logiciel, qui a toujours "bien fonctionné" maintenant est terriblement lent.

Il s'avère que cette liste était une liste de clients, et nos clients n'avaient que peut-être 100 clients, donc personne ne l'a remarqué. L'opération de remplissage de la liste était essentiellement une opération O (1), car elle prenait moins d'une milliseconde. Eh bien, pas tant quand il y a 10 000 clients à ajouter.

Et des années après la mauvaise décision initiale O (1), l'entreprise a presque perdu un gros client. Tout cela à cause d'une petite erreur de conception / hypothèse des années auparavant.

La motivation pour le faire est basée sur l'idée incorrecte que O (1) est toujours meilleur que O (lg n), est toujours meilleur que O (n). L'ordre asymptotique d'une opération n'est pertinent que si, dans des conditions réalistes, la taille du problème devient réellement importante.

Si j'ai deux algorithmes avec ces temps:

• log (n) +10000
• n + 1

Il existe alors un point où ils se croisent. Pour nplus petit que cela, l'algorithme "linéaire" est plus rapide, et pour nplus grand que cela, l'algorithme "logarithmique" est plus rapide. Beaucoup de gens font l'erreur de supposer que l'algorithme logarithmique est plus rapide, mais pour les petits n, ce n'est pas le cas.

Si n reste petit, alors chaque problème est O (1)!

Je suppose que ce que l'on veut dire ici est que si nest limité, alors chaque problème est O (1). Par exemple, si nous trions des entiers, nous pouvons choisir d'utiliser le tri rapide. O(n*log(n))évidemment. Mais si nous décidons qu'il ne peut jamais y avoir plus que des 2^64=1.8446744e+19entiers, alors nous savons que n*log(n)<= 1.8446744e+19*log(1.8446744e+19)<= 1.1805916e+21. Par conséquent, l'algorithme prendra toujours moins de 1.1805916e+21"unités de temps". Comme c'est un temps constant, nous pouvons dire que l'algorithme peut toujours être fait dans ce temps constant -> O(1). (Notez que même si ces unités de temps sont des nanosecondes, cela représente un grand total de plus de 37411 ans). Mais quand même O(1).

Je soupçonne que bon nombre de ces réponses manquent d'un concept fondamental. O (1): O (n) n'est pas identique à f (1): f (n) où f est la même fonction, car O ne représente pas une seule fonction. Même le joli graphique de Schwern n'est pas valide car il a le même axe Y pour toutes les lignes. Pour utiliser tous le même axe, les lignes devraient être fn1, fn2 et fn3, où chacune était une fonction dont les performances pouvaient être directement comparées aux autres.

J'ai entendu plusieurs fois que pour des valeurs suffisamment petites de n, O (n) peut être pensé / traité comme si c'était O (1)

Eh bien, si n = 1 sont-ils exactement les mêmes? Non. Une fonction permettant un nombre variable d'itérations n'a rien de commun avec une qui ne le fait pas, la notation big-O s'en fout, et nous non plus.

La notation Big-O est simplement là pour exprimer ce qui se passe lorsque nous avons un processus itératif, et comment les performances (temps ou ressources) se dégradent à mesure que 'n' augmente.

Donc, pour répondre à la vraie question ... Je dirais que ceux qui font cette affirmation ne comprennent pas correctement la notation Big-O, car c'est une comparaison illogique.

Voici une question similaire: si je boucle une chaîne de caractères et que je sais qu'en général mes chaînes seront inférieures à 10 caractères, puis-je dire que c'est l'équivalent de O (1), mais si mes chaînes étaient plus longues, alors je dirais que c'était O (n)?

Non, car une chaîne de 10 caractères prend 10 fois plus de temps qu'une chaîne de 1 caractère, mais 100 fois moins qu'une chaîne de 1000 caractères! C'est en marche).

Je pense que le texte que vous avez cité est assez imprécis (utiliser le mot "mieux" n'a généralement aucun sens à moins que vous ne fournissiez le contexte: en termes de temps, d'espace, etc.) Quoi qu'il en soit, je pense que l'explication la plus simple serait:

Si le temps d'exécution augmente avec la taille d'une entrée, ce n'est certainement pas $O(1)$ et cela devrait être clair. $O(1)$ne veut pas dire rapide . Cela signifie simplement (en termes de complexité temporelle) que le temps d'exécution a une borne supérieure constante .

Maintenant, prenons un ensemble relativement petit de 10 éléments et avons quelques algorithmes pour le trier (juste un exemple). Supposons que nous conservions les éléments dans une structure qui nous fournit également un algorithme capable de trier les éléments en temps constant. Disons que nos algorithmes de tri peuvent avoir les complexités suivantes (avec une notation big-O):

1. $O(1)$
2. $O(n)$
3. $O(nlog(n))$
4. $O(n^2)$

Quel algorithme choisiriez-vous? La première réponse qui me vient à l’esprit peut être «bien sûr, j’utiliserai le$O(1)$one! ", mais ce n'est pas nécessairement correct. Ce que vous oubliez en pensant ainsi, c'est que la notation big-O cache le facteur constant . Et si vous savez que votre ensemble est assez petit, alors ce facteur constant peut être beaucoup plus important que la complexité asympthotique.

Maintenant, «révélons» la véritable complexité de ces algorithmes de tri mentionnés ci-dessus (où «vrai» signifie ne pas cacher la constante), représentés par le nombre d'étapes nécessaires pour terminer (et supposons que toutes les étapes prennent le même temps):

1. $200$ pas
2. $11n$ pas
3. $4nlog(n)$ étapes (journal avec base 2)
4. $1n^2$ pas

Si notre entrée est de taille 10, alors ce sont des quantités exactes d'étapes pour chaque algorithme mentionné ci-dessus:

1. $200$ pas
2. $11 \times 10 = 110$ pas
3. $4 \times 10 \times 3.32 \approx 134$ pas
4. $1 \times 100 = 100$ pas

Comme vous le voyez, dans ce cas, l'algorithme apparemment pire avec une complexité asympthotique $O(n^2)$ est le plus rapide, battant les algorithmes avec $O(1), O(n)$ et $O(nlog(n))$complexités asympthotiques. Le facteur constant caché par la notation big-O importe ici. À mon avis, cela ne signifie pas que nous pouvons traiter$O(n^2)$ mieux que $O(1)$ (qu'est-ce que cela signifierait de toute façon?) Cela signifie que pour une entrée suffisamment petite (comme vous l'avez vu dans l'exemple), le $O(n^2)$ peut encore être plus rapide que $O(1)$à cause de la constante cachée. Et si la constante est relativement grande par rapport à la taille de l'entrée, elle peut avoir plus d'importance que la complexité asympthotique.