Justification de la négligence des facteurs constants dans Big O

Souvent, si les complexités ont des constantes telles que 3n, nous négligeons cette constante et disons O (n) et non O (3n). Je n'arrive pas à comprendre comment pouvons-nous négliger ce triple changement? Une chose varie 3 fois plus rapidement qu'une autre! Pourquoi négligeons-nous ce fait?

Pour rationaliser la façon dont les notations asymptotiques ignorent les facteurs constants, je pense généralement à ceci: la complexité asymptotique n'est pas pour comparer les performances de différents algorithmes, c'est pour comprendre comment les performances des algorithmes individuels évoluent en fonction de la taille d'entrée.

Par exemple, nous disons qu'une fonction qui prend pas est , car, en gros, pour des entrées suffisamment grandes, doubler la taille d'entrée ne fera que doubler le nombre de pas effectués. De même, signifie que doubler la taille d'entrée quadruplera au plus le nombre d'étapes, et signifie que doubler la taille d'entrée augmentera le nombre d'étapes d'au plus une certaine constante.O ( n ) O ( n 2 ) O ( log n $3n$$O(n)$$O(n^2)$$O(\log n)$

C'est un outil pour dire quels algorithmes évoluent mieux, pas lesquels sont absolument plus rapides.

Premièrement, comme d'autres réponses l'ont déjà expliqué, , ou pour le dire, une fonction est O ( 3 n ) si et seulement si c'est O ( n ) . f = O ( 3 n ) signifie qu'il existe un point N et un facteur C 3 tels que pour tout n ≥ N , f ( n ) ≤ C 3 ⋅ $O(3n) = O(n)$$O(3n)$$O(n)$$f = O(3n)$$N$$C_3$$n \ge N$ . Maintenant, choisissez C 1 = 3 C 3 : pour tout n ≥ N , f ( n ) ≤ C 1 ⋅ n , donc f = O ( n ) . La preuve de l'inverse est similaire.$f(n) \le C_3 \cdot 3n$$C_1 = 3 C_3$$n \ge N$$f(n) \le C_1 \cdot n$$f = O(n)$

Passons maintenant à la raison pour laquelle c'est le bon outil. Remarquez que lorsque nous mesurons la complexité d'un algorithme, nous ne donnons pas d'unité. Nous ne comptons pas les secondes, ni les instructions machine: nous comptons quelques étapes élémentaires non spécifiées qui prennent chacune un temps limité. Nous le faisons parce que l'exécution du même algorithme sur une machine différente changerait le temps nécessaire par instruction - multipliez la fréquence d'horloge par et le temps d'exécution passe de f ( n ) à f ( n ) /$3$$f(n)$$f(n)/3$. Si nous implémentons le même algorithme dans un langage différent, ou sur un système différent, le temps pris par chaque étape élémentaire peut être différent, mais là encore c'est trop de détails: nous ne nous soucions presque jamais de ces différences.

Lorsque vous vous souciez de délais précis, la complexité asymptotique n'est pas pertinente: la complexité asymptotique vous indique ce qui se passe pour les très grandes tailles d'entrée, qui peuvent ou non être les tailles d'entrée réelles auxquelles vous avez affaire.

Rappelez-vous la définition de Big-O:

il existe c > 0 tel que f ( n ) ≤ c g ( n ) pour tout n .$f(n)\in O(g(n))$$c>0$$f(n)\le cg(n)$$n$

Sous cette définition, nous avons que pour chaque constante d . Le but de la notation O est exactement de simplifier les expressions de cette manière. En effet, 3 n croît 3 fois plus vite que n , mais ils sont tous les deux linéaires. Que cela soit justifié ou non - cela dépend du contexte. Mais si vous acceptez d'utiliser la notation O , alors par définition, cela est vrai.$dn\in O(n)$$d$$O$$3n$$n$$O$

La notation Big O est un moyen sans unité de mesure de la variation des performances, donc insensible aux coûts relatifs des primitives de calcul.

En résumé: la notation Big O est un type de mesure relatif sans unité (par opposition à la mesure absolue). Il ne peut mesurer que les variations de performances, pas les performances absolues, pour lesquelles les constantes comptent beaucoup. L'avantage est que cela le rend largement indépendant de l'implémentation, en permettant une analyse plus simple qui peut ignorer les coûts relatifs des opérations élémentaires, tant que ces coûts ont des limites supérieures et inférieures fixes positives. Mais la conséquence est que les facteurs constants n'ont pas de sens . Pourtant, même pour son objectif, l' analyse de la complexité asymptotique peut être remise en question pour d'autres motifs et doit être considérée avec prudence. Par exemple, la taille d'entrée brute peut ne pas être le bon paramètre à considérer.

Une première remarque est que votre question n'est pas formulée avec précision. Lorsque vous négligez la constante sur 3 n , il y a en effet un "triple changement", mais les deux varient au même rythme, et vous ne pouvez pas affirmer que "[une] chose varie 3 fois plus rapidement que les autres".$3$$3n$

Une bonne raison d'ignorer la constante de la notation Landau est que nous n'avons aucune unité sur laquelle nous pouvons compter. Quand quelqu'un déclare que A vit deux fois plus loin de vous que B, cela a un sens indépendamment de toute unité. Nous pouvons nous mettre d'accord sur ce point même si vous mesurez des distances en pouces alors que je le fais en années-lumière. Mais la mesure de distance absolue nécessite de spécifier des unités, et sa formulation numérique dépend de l'unité choisie.

Le temps réel pris par un algorithme dépend du temps d'exécution des opérations élémentaires, qui est très dépendant de la machine. Vous pouvez compter le nombre d'opérations élémentaires, mais il n'y a aucune raison de croire qu'elles prennent toutes le même temps, et il est toujours possible de combiner plusieurs opérations en une seule, ou inversement de décomposer une opération en plus petites, de sorte que le nombre des opérations n'a pas vraiment de sens, sauf si vous êtes d'accord sur une machine virtuelle de référence. Être indépendant de la référence est un avantage.

Une autre vue de l'avantage de l'approche est que tout ce qui vous intéresse dans l'analyse est de compter le nombre d'opérations élémentaires, tant que leur coût a une limite supérieure et une limite inférieure positive. Vous n'avez pas à vous soucier du coût individuel.

Cependant, le prix à payer pour cet avantage est que l'évaluation des coûts de calcul est donnée avec une unité non spécifiée, et le temps de calcul, par exemple, pourrait être des nanosecondes ou des millénaires - nous n'essayons même pas de savoir. En d'autres termes, les facteurs constants n'ont pas de sens, car le changement d'unités est inséparable du changement de facteur constant et aucune unité de référence n'est utilisée.

Comme l'a noté Patrick87 , cela suffit pour comprendre comment un algorithme évolue par rapport à la taille d'entrée, mais il ne donnera pas une mesure absolue des performances, à moins de s'appuyer sur une unité de référence. La suppression d'une machine abstraite de référence commune peut être effectuée lorsque l'on souhaite réellement comparer les performances d'algorithmes distincts, mais il est plus difficile de s'assurer que la comparaison n'est pas biaisée par les détails de réalisation. Dans la complexité asymptotique, ce risque est évité car vous comparez l'algorithme avec lui-même.

Quoi qu'il en soit, seul un programmeur naïf s'appuierait exclusivement sur la complexité asymptotique pour choisir un algorithme. Il existe de nombreux autres critères, y compris la constante incalculable et le coût réel des opérations élémentaires. En outre, la complexité du pire des cas peut être un mauvais indicateur, car la source de la complexité du pire cas peut se produire rarement, et sur des fragments d'entrée suffisamment petits pour avoir un impact limité. Par exemple, les analyseurs syntaxiques généraux pour les grammaires adjacentes aux arbres ont une complexité théorique et sont tout à fait utilisables en pratique. Le pire cas que je connaisse est l' inférence de type polymorphe Damas-Hindley-Milner$O(n^6)$algorithme utilisé pour ML, qui a une complexité exponentielle dans le pire des cas. Mais cela ne semble pas déranger les utilisateurs de ML, ni empêcher l'écriture de très gros programmes en ML. Il y a plus que la constante qui compte. En fait, l'analyse asymptotique relie une mesure du coût d'un calcul à une certaine mesure de la complexité de l'entrée. Mais la taille brute n'est peut-être pas la bonne mesure.

La complexité est comme la décidabilité, elle peut être théoriquement mauvaise, mais cela peut ne pas être pertinent pour la plupart de l'espace de données ... parfois. L'analyse de complexité asymptotique est un bon outil bien conçu, avec ses avantages et ses limites, comme tous les outils. Avec ou sans explicitation de la constante, qui peut être dénuée de sens, le jugement est nécessaire.

Les autres réponses expliquent très bien pourquoi, selon la définition de Big-O, .$O(n)=O(3n)$

Quant à savoir pourquoi nous le faisons réellement dans CS, c'est pour que nous ayons une description compacte de l'efficacité d'un algorithme. Par exemple, il peut y avoir un algorithme qui a une instruction if, où une branche exécute instructions et l'autre exécute 3 n instructions. Cela signifie que le nombre exact change pour chaque entrée, même pour des entrées de même longueur. Nous pourrions trouver un nombre pour chaque entrée, mais l'utilisation de la notation big-O nous donne une mesure de la complexité temporelle qui s'applique à TOUTES les entrées.$n$$3n$

C'est beaucoup plus utile pour deviner la vitesse d'un algorithme. Sinon, il nous faudrait envisager une fonction massive par morceaux, ce qui serait très difficile à comprendre.

L'autre raison principale est que ces mesures sont indépendantes du matériel. Différents compilateurs et architectures transformeront le même code en ensembles d'instructions très différents. Cependant, si nous savons que le nombre d'instructions est linéaire, exponentiel, etc., alors nous avons une idée de la vitesse des algorithmes qui tient, quel que soit l'ordinateur réel que nous compilons ou exécutons.

$f(n)=O(g(n))$$\limsup\limits_{n\to\infty} \frac{f(n)}{g(n)}<+\infty$

$g(n)=n$$g(n)=3n$

$O(n^2)=O(.00005321n^2+1000000000n+10^{46803})$$f$$=$

Laissez-moi vous expliquer simplement. Prenons n = 100000. Maintenant, qu'est-ce que 3n? C'est 300000 ( Ouais, c'est 3 plis de n ) Mais qu'est-ce que n ^ 2 ? 10000000000 . ( c'est 1 lakh plis de n ) .. Comparez n ^ 2 avec n. 3 est négligeable quand on compare avec 1 lakh. nous pouvons donc le supprimer.

Pensez si n est un milliard ou un billion. Dans ce cas, nous allons à nouveau comparer 3 à quelques milliards ou trillions. Maintenant, vous savez pourquoi nous pouvons négliger 3.