Forum de Mathématiques: Maths-Forum

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

personne pour m'aider svp ?...

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

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

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 ...

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

Pour la question 1, j'ai utilisé le theoreme general des equations de recurence, qui pose T(n)=a*T(n/b) + f(n) avec a le nb de sous probleme et n/b la taille, et f(n) le cout de la fusion ... et je me trouve ici dans le cas 3 du theoreme, qui, une fois verifier, dit que T(n)=(~)(f(n)). Ici f(n)=n² d...

Bonsoir, merci pour votre réponse, je vais regardais ça . Sinon je suis en licence d'informatique, et c'est une matiere appelé mathematiques discrete, d'ou un melange un peu des 2. Sinon mon exercice se partage en 4 parties : - trouver l'ordre de grandeur asymptotique de T(n) - Uk=T(2^k) : montrez q...

ok super j'ai capté ! merci beaucoup !!!

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 ...

woahh lol ok .... ^^ comment on arrive a ce résultat en fait svp ?
merci beaucoup de m'aider!
cdt

Bonjour, je cherche a calculet la complexite f(n) de l'algorithme suivant : pour i de 1 a n-1 faire pour j de i+1 a n faire pour k de 1 a j faire {instruction} Je suppose que Instruction a un temps constant c. Et je voudrais aussi en deduire l'ordre de grandeur asymptotique ... j'avoue que je bloque...

ok donc j'ai reussi a montrer que l'ordre de grandeur de T(n) est n2 . Mais maintenant je bloque sur cette question : On pose Uk=T(2^k) . Montrez que Uk vérifie la récurence (2) : Uk - 7U(k-1) + 12U(k-2) pour k>=2 et reolvez l'equation. Mais je ne trouve pas que c'est une équation !! enfin c'est ega...

Comment ça c'est quoi ? je ne sais pas en fait ... mon énoncé n'est pas trés claire : voila precisement ce qu'il dit : Soit l'equation de récurence (1) : T(1)=1 T(n)=3T(n/2)+n² Trouvez l'ordre de grandeur asymptotique de T(n). Et je vois pas comment faire ... surtout que le suite de l'exo est encore...

un ptit coup de pouce svp ?...

svp un peu d'aide ...

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

re bonjour ! alors voila clairement ce que je cherche maintenant : j'ai toujous mon equation de recurence suivante (1) : T(1)=1 T(n)=3T(n/2)+n² et je voudrais juste trouver l'ordre de grandeur asymptotique de T(n), sans utiliser n=2^k, parcque ça m'est demandé que aprés ... comment je peux faire ? m...

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 !

ah ok merci beaucoup j'avais pas bien compris en fait merci bien ! donc ça c'est T(n) en fonction de n lorsque n=2^k Je voudrais aussi trouver l'odre de grandeur asymptotique de T(n) sans passer par n=2^k, juste avec l'equation de recurrence de mon premier post ... commetn je peux faire alors ? pars...