Comportements asymptotiques

par **black** » 26 Nov 2008, 21:42

bonjour a tous !
j'aimerais avoir un peu d'aider sur cet exercice si c'est possible ! j'ai 12 fonctions :
f1(n)=n
f2(n)=2^n
f3(n)=n lg(n)
f4(n)=n-n^3+7n^5
f5(n)=n²+lg(n)
f6(n)=n²
f7(n)=lg n
f8(n)=n^3
f9(n)=racine(n) + lg(n)
f10(n)=(lg(n))²
f11(n)=n!
f12(n)=ln(n)

Je voudrais trouver en fait tout kes couples possibles (f,g) tels que f et g aient la meme grandeur asymptotique ...
Je suis vraiment perdu la, si vous pouvez m'aider ...
Merci beaucoup
cdt

par **nuage** » 26 Nov 2008, 22:21

Il y en a très peu.
Je suppose que lg désigne le logarithme décimal.
Dans ce cas f7 est un O(f12) et réciproquement.
Pour faire ce genre d'exercice il faut placer les fonctions

dans l'échelle des exponentielles
dans l'échelle des puissances
dans l'échelle des logarithmes itérées

En reprenant les échelles de numéros supérieurs dans chaque échelle.

Pour n! regarder la formule de Stirling pour comparer à 2^n

etc...

par **black** » 26 Nov 2008, 23:07

euh... oui d'accord jvais essayer de comprendre comme ça mais jai beaucoup de mal ... est-ce que vous pourriez me faire queslques exemples svp ?
merci beaucoup

par **nuage** » 26 Nov 2008, 23:25

Pour donner un exemple f1 est négligeable devant f3.
En effet

la limite est infinie en plus l'infini donc f1=o(f3).
Pour un autre exemple f4 est équivalente en l'infini à

, elle est seule dans sa catégorie.

par **black** » 27 Nov 2008, 00:12

pfff jsuis vraiment perdu la ... en gros faut faire f/g pour chaque fonction, a savoir 11*11 division ? :marteau: et regarder si ça tend vers l'infini ?
il n'y a pas un moyen de savoir d'un coup d'oeil (si jpeu dire) quels couples (f,g) existent tels que f et g aient la meme grandeur asymptotique ?

par **nuage** » 27 Nov 2008, 01:23

Si, bien sur,
il suffit de regarder le terme dominant et de les classer avec l'échelle que je t'ai donnée.

par **black** » 27 Nov 2008, 08:24

Ah d'accord ... donc il faut que je repartisse mes 12 fonctions dans les echelles que vous m'avez donné, et apré les couples je les trouves comment ? N'ont le meme comportement que celles qui sont dans la méme echelle ? merci !

par **busard_des_roseaux** » 27 Nov 2008, 09:42

black a écrit:en gros faut faire f/g pour chaque fonction, a savoir 11*11 division ?

ben non, car f R g si f=o(g) est une relation transitive. On les classe selon leur terme dominant, un peu comme on ordonne des nombres. En une seconde, c'est fait !

par **black** » 27 Nov 2008, 17:23

euh désolé ça veut dire quoi f R g ?

par **black** » 27 Nov 2008, 21:48

svp un peu d'aide ...

par **black** » 28 Nov 2008, 00:13

ok donc tout d'abord j'essai de classer mes 12 fonction en 4 classes :

1.classe exponetielles :

2.classe puissances : f2

3.classe logarithmes iterees : f3-f7-f10-f12

4.autres : f1-f4-f5(car n²+lg(n) ~n²)-f6-f8-f9-f11

Voila est-ce juste ?

Aprés j'essai de classes les fonctions par ordre croissant et j'obtiens cela :

f7<
Est-ce juste ?

aprés comment je peux m'en servir pour résoudre mon exercice ?
merci si vous pouvez m'aider !!
cdt

par **busard_des_roseaux** » 28 Nov 2008, 08:32

black a écrit:euh désolé ça veut dire quoi f R g ?

f est en relation avec g

par **black** » 28 Nov 2008, 10:11

ok ...moi je dois trouver tout les couples (f,g) tels que f=(~)(g) , cela revient au méme ? et mon classement peut il m'aider ?
merci

par **mathelot** » 28 Nov 2008, 11:01

Bjr,

j'ai tendance à penser que ta démarche manque de méthode :hum: :

1) apprendre la définition d'une relation d'équivalence (3 propriétés)
et d'une relation d'ordre (3 propriétés)
éventuellement de pré-ordre

2) apprendre la définition des trois relations suivantes:

(équivalence)
f=O(g) "grand o"
f=o(g) "petit o"

3) lesquelles sont des relations d'équivalence ? d'ordre ?
certaines vérifient elles deux propriétés parmi les 3 ?
lesquelles sont transitives ?

par **black** » 28 Nov 2008, 12:21

f~g equivalence
f=O(g) ordre
f=o(g) equivalence

le probleme c'est qu'apparement il existe un moyen rapide de trouver les couples qui m'interessent , d'aprés mes recherches, mais je ne vois pas clairement comment ...

par **black** » 28 Nov 2008, 13:15

bon ben je vois vraiment pas alors tampis c'ets pas grave merci quand meme de votre aide .

par **black** » 28 Nov 2008, 14:43

en fait pour résoudre mon exercice, il faut que je trouve tout les couples (f,g) tels que f=(~)(g).
Or f=(~)(g) si limite de f/g en l'infini =a>0 . Mais je vais pas faire 11*11 calcul de limites si ??? n'y a t il pas un moyen plus rapide et si oui lequel svp ?
merci

par **black** » 29 Nov 2008, 11:54

personne pour m'aider svp ?...

par **black** » 01 Déc 2008, 23:14

toujours personne ? je n'ai vraiment pas d'idée ...

Comportements asymptotiques

comportements asymptotiques

Qui est en ligne