Comment discuter des coefficients en notation big-O

Quelle notation est utilisée pour discuter des coefficients des fonctions en notation big-O?

J'ai deux fonctions:

• $f(x) = 7x^2 + 4x +2$
• $g(x) = 3x^2 + 5x +4$

Évidemment, les deux fonctions sont , en effet , mais cela ne permet pas une comparaison plus approfondie. Comment puis-je discuter des coefficients 7 et 3. Réduire le coefficient à 3 ne change pas la complexité asymptotique, mais cela fait quand même une différence significative dans l'utilisation du runtime / de la mémoire.Θ ( x 2$O(x^2)$$\Theta(x^2)$

Est-il faux de dire que est et est ? Y a-t-il une autre notation qui prend en compte les coefficients? Ou quelle serait la meilleure façon d'en discuter?O ( 7 x 2 ) g O ( 3 x 2$f$$O(7x^2)$$g$$O(3x^2)$

notations Big- et big- masquent les coefficients du terme principal, donc si vous avez deux fonctions qui sont toutes les deux vous ne pouvez pas comparer leurs valeurs absolues sans regarder les fonctions elles-mêmes. Ce n'est pas faux en soi de dire que , mais ce n'est pas informatif car est également vrai (et, en fait, c'est pour toute constante positive ).Θ Θ ( n 2 ) 7 x 2 + 4 x + 2 = Θ ( 7 x 2 ) 7 x 2 + 4 x + 2 = Θ ( 3 x 2 ) Θ ( k x 2 ) $O$$\Theta$$\Theta(n^2)$$7x^2 + 4x + 2 = \Theta(7x^2)$$7x^2 + 4x + 2 = \Theta(3x^2)$$\Theta(kx^2)$$k$

Il existe d'autres notations que vous pouvez utiliser à la place. Par exemple, la notation est une revendication beaucoup plus forte que big- :$\sim$$\Theta$

$\qquad \displaystyle f(x) \sim g(x) \iff \lim_{x \to \infty} \frac{f(x)}{g(x)} = 1$

Par exemple, , mais la revendication serait fausse. Vous pouvez considérer la notation tilde comme une notation qui préserve les principaux coefficients, ce qui semble être ce que vous recherchez si vous vous souciez du coefficient principal du terme de croissance dominant. 7 x 2 + 4 x + 2 ∼ 3 x 2$7x^2 + 4x + 2 \sim 7x^2$$7x^2 + 4x + 2 \sim 3x^2$$\Theta$

Le tilde est une approche. Si vous voulez rester avec , vous pourriez dire$O$

$\qquad f(x) = 7x^2 + O(x)$ et

$\qquad g(x) = 3x^2 + O(x)$ .