Exemples d'analyse asymptotique

Question

Ici, je donnerai deux fonctions f (n) et g (n) et mon but est de décider si le f (n) est en thêta, oméga, grand o, petit o ou petit oméga. Veuillez fournir une preuve détaillée si vous êtes confiant avec de tels problèmes.

Problème 1: f (n) = (1/2) n^2 - 3n, g (n) = n^2

Problème 2: f (n) = 6n^3, g (n) = n^2

problème 3: f (n) = 3n + 5, g (n) = n^2

problème 4: f (n) = n plafond (lg n^2), g (n) = n^2 log n

Problème 5: f (n) = [10^(n + 4) (n)] + 6, g (n) = 10^(n + 3)

Answer 1

Les fonctions polynomiales sont faciles. Comparez simplement l'ordre le plus élevé de chacun.

1. f (n) est n^2 et g (n) est n^2, donc f (n) est thêta g (n)
2. f (n) est le n^3 et g (n) est n^2, donc f (n) est O (g (n))
3. f (n) est n et g (n) est n^2, donc f (n) est W (g (n))

Une démonstration impliquerait le calcul des limites.