Quelle est la méthode appropriée pour rechercher l’ordre de croissance de cette fonction?

Question

2 ^ n + 6n ^ 2 + 3n

Je suppose que c'est juste O (2 ^ n), en utilisant le terme d'ordre le plus élevé, mais quelle est l'approche formelle pour s'y prendre pour prouver cela?

Answer 1

Vous pouvez prouver que 2 ^ n + n ^ 2 + n = 0 (2 ^ n) en utilisant des limites à l'infini. Plus précisément, f (n) est O (g (n)) si lim (n- > inf.) F (n) / g (n) est fini.

lim (n->inf.) ((2^n + n^2 + n) / 2^n)

Puisque vous avez inf / inf, un formulaire indéterminé , vous pouvez utiliser La règle de l'Hopital et différenciez le numérateur et le dénominateur jusqu'à obtenir quelque chose vous pouvez travailler avec:

lim (n->inf.) ((ln(2)*2^n + 2n + 1) / (ln(2)*2^n))
lim (n->inf.) ((ln(2)*ln(2)*2^n + 2) / (ln(2)*ln(2)*2^n))
lim (n->inf.) ((ln(2)*ln(2)*ln(2)*2^n) / (ln(2)*ln(2)*ln(2)*2^n))

La limite est 1, donc 2 ^ n + n ^ 2 + n est bien O (2 ^ n) .

Answer 2

Veuillez consulter:

Big O Notation Devoir - Analyse d'algorithme de fragment de code?

Big O, comment calculez-vous / approximez-vous?

Peut Quelqu'un peut-il expliquer la différence entre les notations Big-O et Little-O?

Big-O pour les huit ans? (non destiné à être insultant)