La notation Big Oh ne mentionne pas la valeur constante

Je suis programmeur et je viens de commencer à lire des algorithmes. Je ne suis pas complètement convaincu des notations à savoir Bog Oh, Big Omega et Big Theta. La raison en est par définition de Big Oh, elle précise qu'il devrait y avoir une fonction g (x) telle qu'elle soit toujours supérieure ou égale à f (x). Ou f (x) <= cn pour toutes les valeurs de n> n0.

Pourquoi ne mentionnons-nous pas la valeur constante dans la définition? Par exemple, disons une fonction 6n + 4, nous la désignons comme O (n). Mais ce n'est pas vrai que la définition est valable pour toute valeur constante. Cela n'est valable que lorsque c> = 10 et n> = 1. Pour des valeurs inférieures à c supérieures à 6, la valeur de n0 augmente. Alors pourquoi ne mentionnons-nous pas la valeur constante dans la définition?

Il y a plusieurs raisons, mais la plus importante est probablement que les constantes sont fonction de la mise en œuvre de l'algorithme, pas de l'algorithme lui-même. L'ordre d'un algorithme est utile pour comparer des algorithmes quelle que soit leur implémentation.

Le temps d'exécution réel d'un tri rapide changera généralement s'il est implémenté en C ou Python ou Scala ou Postscript. Il en va de même pour le tri à bulles - le temps d'exécution variera considérablement en fonction de la mise en œuvre.

Cependant, ce qui ne changera pas, c'est le fait que, toutes choses étant égales par ailleurs, à mesure que l'ensemble de données augmente, le temps nécessaire pour exécuter un tri à bulles augmentera plus rapidement que le temps nécessaire pour exécuter le tri rapide dans le cas typique, quelle que soit la langue ou la machine ils sont implémentés avec, en supposant une implémentation raisonnablement correcte. Ce simple fait vous permet de faire des déductions intelligentes sur les algorithmes eux-mêmes lorsque des détails concrets ne sont pas disponibles.

L' ordre d'un algorithme filtre les facteurs qui, bien qu'importants dans les mesures réelles, tendent à n'être que du bruit lors de la comparaison des algorithmes dans l'abstrait.

O (n) et les autres notations d'ordre ne sont (généralement) pas concernées par le comportement des fonctions pour les petites valeurs. Elle concerne le comportement des fonctions pour les très grandes valeurs, à savoir les limites lorsque n se déplace vers l'infini.

Les constantes importent techniquement mais elles sont généralement abstraites car une fois que n devient suffisamment grand, la valeur de c est totalement hors de propos. Si la valeur de c est importante, nous pouvons l'inclure dans l'analyse, mais à moins que les fonctions comparées aient des facteurs constants très importants ou si l'efficacité est une préoccupation particulièrement importante, elles ne le sont généralement pas.

La notation Big O selon la définition stipule que: La notation Big O est basée sur l'intuition que pour toutes les valeurs n à et à droite de n ', la valeur de f (n) est égale ou inférieure à cg (n). Les constantes n'ont pas non plus d'importance lorsque vous passez à des facteurs (variables) de grande valeur (comme n-carré ou n-cube) car ce ne sont que les constantes et non les quantités variables qui peuvent devenir aussi grandes que ces facteurs. Ci-dessous, le graphique de la notation Big-O.
For a given function g(n), we denote by O(g(n)) the set of functions:
O(g(n)) = {f(n): there exist positive constants c and n' such that 0<=f(n)<=c.g(n) for all n > n'}

L'essence de cette notation est dans le fait " how lower is f(n) from c.g(n) and not when it starts becoming lower".

Dans l'analyse d'algorithme, l' Ordre de Croissance est l'abstraction clé et il donne la vitesse à laquelle le temps d'exécution change à mesure que la taille d'entrée change. Disons qu'un algorithme a un temps d'exécution f(n) = 2n + 3. Maintenant, nous branchons une taille d'entrée,

n = 10: 2 * 10 + 3 = 23

n = 100: 2 * 100 + 3 = 203

n = 10000: 2 * 10000 + 3 = 20003

n = 1000000: 2 * 1000000 + 3 = 2000003

n = 100000000 : 2 * 100000000 + 3 = 200000003

Comme on peut le voir, l'ordre de croissance est principalement déterminé par la variable n; les constantes 2 et 3 sont moins importantes et à mesure que la taille d'entrée augmente, elles deviennent encore moins importantes pour la déterminer. C'est pourquoi dans l'analyse des algorithmes, les constantes sont atténuées au profit de la variable déterminant l'ordre de croissance d'une fonction.

Toute la notion de notation Big-Oh consiste spécifiquement à ignorer les constantes et à présenter la partie la plus importante de la fonction décrivant le temps d'exécution d'un algorithme.

Oubliez la définition formelle un instant. Quelle est la pire fonction (croissance plus rapide), n^2 - 5000ou 5000 n + 60000? Pour nmoins d'environ 5000, la fonction linéaire est plus grande (et donc pire). Au-delà de cela (valeur exacte 5013?), L'équation quadratique est plus grande.

Puisqu'il y a plus (pas mal plus) de nombres positifs supérieurs à 5000 que moins, nous considérons que le quadratique est la fonction «plus grande» (pire) en général. La notation d'ordre (Big-Oh, etc.) impose cela (vous pouvez toujours éliminer un additif et une constante multiplicative en utilisant ces définitions).

Bien sûr, les choses ne sont pas toujours simples. Parfois , vous ne voulez connaître ces constantes. Quel est le meilleur tri par insertion ou tri par bulles? Les deux le sont O(n^2). Mais l'un est vraiment meilleur que l'autre. Avec une analyse plus élaborée, on peut obtenir des constantes comme vous vous interrogez. Il est généralement beaucoup plus facile de calculer la fonction Big-Oh qu'une fonction plus exacte.

Big-Oh ignore ces constantes pour simplifier et faciliter les comparaisons les plus importantes. Nous aimons la notation parce que généralement nous ne voulons pas connaître les constantes (pour la plupart non pertinentes).

(puisque c'est une réponse plus longue, lisez les caractères gras pour un résumé )

Prenons votre exemple et parcourons-le étape par étape, en comprenant le but derrière ce que nous faisons. Nous commençons par votre fonction et le but de trouver sa notation Big Oh:

f(n) = 6n+4

Tout d'abord, soyons O(g(n))la notation Big Oh que nous essayons de trouver f(n). A partir de la définition de Big Oh, nous devons trouver une simplifiée g(n) où il existe des constantes cet n0où c*g(n) >= f(n)est vrai pour tous nest supérieur à n0.

Tout d'abord, choisissons g(n) = 6n + 4(ce qui donnerait O(6n+4)en Big Oh). Dans ce cas, nous voyons que c = 1et toute valeur de n0répondra aux exigences mathématiques de notre définition de Big Oh, car g(n)toujours égale à f(n):

c*g(n)      >=  f(n)    
1*(6n + 4)  >=  6n + 4    //True for all n's, so we don't need to pick an n0

À ce stade, nous avons satisfait aux exigences mathématiques. Si nous nous arrêtions àO(6n+4) , il est clair que ce n'est pas plus utile que d'écrire f(n), donc cela manquerait le vrai but de la notation Big Oh: comprendre la complexité temporelle générale d'un algorithme! Passons donc à l'étape suivante: la simplification.

Tout d'abord, pouvons-nous simplifier 6nle Big Oh O(4)? Non! (Faites de l'exercice pour le lecteur s'il ne comprend pas pourquoi)

Deuxièmement, pouvons-nous simplifier le 4pour que le Big Oh soit O(6n)? Oui! Dans ce cas g(n) = 6n, alors:

c*g(n)    >=  f(n)
c*6n      >=  6n + 4     

À ce stade, choisissons c = 2car le côté gauche augmentera plus rapidement (de 12) que le côté droit (de 6) pour chaque incrément de n.

2*6n      >=  6n + 4

Maintenant, nous devons trouver un positif n0où l'équation ci-dessus est vraie pour tous nsupérieure à cette valeur. Comme nous savons déjà que le côté gauche augmente plus vite que le droit, tout ce que nous avons à faire est de trouver une solution positive. Ainsi, puisque n0 = 2rend ce qui précède vrai, nous savons que g(n)=6n, ou O(6n)est une notation Big Oh potentielle pour f(n).

Maintenant, pouvons-nous simplifier le 6pour que le Big Oh soit O(n)? Oui! Dans ce cas g(n) = n, alors:

c*g(n)      >=  f(n)    
c*n         >=  6n + 4    

Choisissons c = 7car la gauche augmenterait plus vite que la droite.

7*n         >=  6n + 4

Nous voyons que ce qui précède sera vrai pour tous nsupérieurs ou égaux à n0 = 4. Ainsi, O(n)est une notation Big Oh potentielle pour f(n). Pouvons-nous encore simplifier g(n)? Nan!

Enfin, nous avons constaté que la notation Big Oh la plus simple pour f(n)est O(n). Pourquoi avons-nous traversé tout cela? Parce que maintenant nous savons que f(n)c'est linéaire , car c'est la notation Big Oh qui est de complexité linéaire O(n). La bonne chose est que nous pouvons maintenant comparer la complexité temporelle de f(n)à d'autres algorithmes! Par exemple, nous savons maintenant que f(n)est de temps complexité comparable aux fonctions h(n) = 123n + 72, i(n) = n, j(n) = .0002n + 1234, etc; car en utilisant le même processus de simplification décrit ci-dessus, ils ont tous une complexité temporelle linéaire de O(n).

Sucré!!!

Si vous avez une fonction de performance de 6n + 4, la question pertinente est "6 quoi?". Comme l'a demandé un commentaire: que représente votre constante? En termes de physique, quelles sont les unités de votre facteur constant?

La raison pour laquelle la notation O () est si largement utilisée pour décrire les performances de l'algorithme est qu'il n'existe aucun moyen portable de répondre à cette question. Différents processeurs prendront un nombre différent de cycles d'horloge et différentes quantités de temps pour effectuer le même calcul élémentaire, ou ils peuvent regrouper différemment les calculs élémentaires pertinents. Différents langages informatiques, ou différentes descriptions formelles et informelles comme le pseudocode, représenteront des algorithmes d'une manière difficile à comparer directement. Même les implémentations dans le même langage peuvent représenter le même algorithme de différentes manières - des détails de mise en forme triviaux comme le nombre de lignes de côté, vous aurez généralement une grande variété de choix structurels arbitraires pour implémenter un algorithme donné.

Regardez-le d'une autre manière: nous utilisons «algorithme» non pas pour décrire une implémentation particulière, mais pour décrire une classe entière d'implémentations potentielles de la même procédure générale. Cette abstraction ignore les détails de l'implémentation en faveur de la documentation de quelque chose de valeur générale, et le facteur de performance constant est l'un de ces détails.

Cela dit, les descriptions d'algorithmes sont souvent accompagnées de folklore, de notes ou même de repères réels qui décrivent les performances d'implémentations réelles sur du matériel réel. Cela vous donne une idée approximative du type de facteur constant à attendre, mais il doit également être pris avec un grain de sel car les performances réelles dépendent de choses comme la quantité de travail consacrée à l'optimisation d'une implémentation donnée. De plus, à long terme, les performances relatives d'algorithmes comparables ont tendance à dériver à mesure que l'architecture des processeurs les plus récents et les plus performants change ...