Notion Asymptotique

[Manaus]

Bonsoir!!

Pour les fonctions suivante je cherche une fonction aussi simple que possible qui est l'estimé grand-O le plus précis possible.

f1(x) = 8^(log base 2 (n))
f2(x) = 32
f3(x) = ( n^3 log base 2(n) ) / (n²)
f4(x) = f1(n) + f2(n) + f3(n)

A chaque fois que j'ai posté un problème sur ce forum vos commentaires m'ont été d'une grande aide. Merci d'avance! :we: :we:

[Frede]

C'est quoi le grand O ?

[Ben314]

Pour deux fonction f et g définies au voisinage d'un réel (ou de ), on dit que f est O(g) lorsque f/g reste borné au voisinage de .

Par exemple, pour f2, le plus simple est sans doute de dire que f2 est O(1)

[Manaus]

Pour deux fonction f et g définies au voisinage d'un réel (ou de ), on dit que f est O(g) lorsque f/g reste borné au voisinage de .

Par exemple, pour f2, le plus simple est sans doute de dire que f2 est O(1)

Merci ta réponse!
Mais pour les fonctions 1 et 3 je dois les modifier pour essayer d'arriver au plus petit possible? par exemple on pourrait dire que f1 est O(n^n) mais ce n'est pas assez précis j'imagine.

[Ben314]

Effectivement, vu la définition du O, on peut prendre au pif une fonction g qui est extraordinairement grande et affirmer que f est O(g), mais normalement, on essaye de trouver une fonction g qui approxime assez bien f, c'est à dire que le rapport f/g soit borné, mais ne tende pas vers 0 à toute vitesse (ce qui signifie qu'on aurait pu prendre g "un peu plus petite")
Pour la fonction f1, sauf erreur elle vaut en fait n^3 et je vois pas trop comment trouver un truc plus simple que n^3 pour la majorer.
Pour f3, il me semble qu'elle vaut n.log[base2](n) et on peut par exemple dire qu'elle est O(n^2) voire qu'elle est O(n^alpha) pour tout alpha>1.
Aprés, pour la dernière question, quand tu somme un nombre fini de fonction le résultat est du O de la plus grande des fonctions donc ici, la somme est O(n^3)


P.S.
1) Il y a un sousic dans tes notations où tu écrit des f(x) puis des formules en n.
2) J'ai supposé que c'était des des O au voisinage de +oo vu la tête des fonctions.

[Manaus]

Effectivement, vu la définition du O, on peut prendre au pif une fonction g qui est extraordinairement grande et affirmer que f est O(g), mais normalement, on essaye de trouver une fonction g qui approxime assez bien f, c'est à dire que le rapport f/g soit borné, mais ne tende pas vers 0 à toute vitesse (ce qui signifie qu'on aurait pu prendre g "un peu plus petite")
Pour la fonction f1, sauf erreur elle vaut en fait n^3 et je vois pas trop comment trouver un truc plus simple que n^3 pour la majorer.
Pour f3, il me semble qu'elle vaut n.log[base2](n) et on peut par exemple dire qu'elle est O(n^2) voire qu'elle est O(n^alpha) pour tout alpha>1.
Aprés, pour la dernière question, quand tu somme un nombre fini de fonction le résultat est du O de la plus grande des fonctions donc ici, la somme est O(n^3)


P.S.
1) Il y a un sousic dans tes notations où tu écrit des f(x) puis des formules en n.
2) J'ai supposé que c'était des des O au voisinage de +oo vu la tête des fonctions.

Merci pour ta réponse!! Ca m'aide beaucoup!!

Que dois je écrire pour justifier cela?

1) Désolé les fonction sont bien F(n)
2) Je pense aussi que c'est ça

[Frede]

Il n'est peut-être pas trop tard pour que je remercie Ben314 pour la définition de la fonction O. Je n'en avais jamais entendu parler.

[Ben314]

Que dois je écrire pour justifier cela?

Ben a chaque fois tu vérifie que ta fonction f divisée par ce que tu as mis dans le O c'est effectivement borné.
A part pour la fonction f3 c'est a chaque fois évident.

Il n'est peut-être pas trop tard pour que je remercie Ben314 pour la définition de la fonction O. Je n'en avais jamais entendu parler.

Y'a pas de quoi.
De mémoire il me semble qu'on apelle ça les "notation de landau".