Forum de Mathématiques: Maths-Forum

Salut,

Je veux juste avoir vos reponses sur ceci, c'est un QCM.
1) f(n) - o(f(n)) = theta(f(n))

2) si f(n) = o(n), alors f(n) = O(n/log(log n))

3) si f(n) = o(g(n)) alors f(n) = O(c.g(n)) pour chaque c > 0

pour ma part:
1) faux
2) faux
3) vrai

Merci

Salut, A la question de savoir si un algo qui met un temps polynomial est toujours préférable à un algo qui prend un temps exponentiel, je repondrais que ça depend de la taille des entrées. Si la taille est petite l'algo exponentielle est préférable sinon c'est l'algorithme de temps polynomial. Et t...

Merci, je comprends maintenant. Donc cela dépend des constantes multiplicatives positives de chaque temps.
Merci

et si j'utilisais les limites, se serait une demonstration claire?
lim (n^2/n^3) = 0 quand n->infini => theta(n^2) inclus dans theta(n^3)

celà suffit t'il pour dire que A est toujours préférable à B?

Bonjour, Mon exo est peut être trop facile mais je n'arrive pas à y repondre clairement. on a 2 algos A et B: A temps dans théta(n^2) et B temps dans théta(n^3) et on me demande si A est toujours préférable à B. de justifier Je crois que quelque soit n>=2 A est toujours préférable à B, mais je trouv...

Salut, J'ai fait une erreur: je suis arrivé à: 1/2 ln(n - (1/2)) + O(1) http://img146.imageshack.us/img146/2636/sanstitre2tl5.th.gif et on demande de montrer que c'est egal à ln(racine(n)) + O(1). Je ne comprends pas bien ce tu essayes de me dire: on n'a pas précisé n impair dans l'énoncé. C'est une...

Bonsoir, il me faut montrer ceci: http://img405.imageshack.us/img405/7894/img1jj4.th.gif en utilisant la formule Euler je suis arrivé à ceci. http://img259.imageshack.us/img259/2332/img2copietp0.th.gif comment quitter de ln(n - 1/2) à ln (n)? ou alors si vous avez une autre methode pour la demonstra...

toc toc! :triste:

Salut, J'ai fait des algos sur les structures de données (tableau, files, piles, etc...) auparavant, mais on ne s'interessait pas au nom et à leur temps d'execution. Là j'ai changé d'établissement scolaire et on étudie la complexité des algos. Je suis souvent perdu lorsque le prof s'exprime parce qu...

Et pour finir avec ça, il suffit de montrer que la fonction est continue pour dire qu'elle admet un point fixe?

Ok, je crois avoir compris: c'est à cause de la relation f(x)=x des points fixes. U(n) est géométrique et on remplace son terme général dans la relation 2 pour avoir V(n). c'est ça?

J'ai un souci: 1- je trouve les points fixes a et b 2- je pose U(n) = (v(n) - a ) / (v(n) - b) cela doit me donner quelque chose comme U(n) = constante * W(n-1) où W(n-1) est une autre suite 3- Je demontre que W(n) est une suite géométrique on aura donc W(n) = (q exposant n) * w(0) avec q comme la r...

Merci.
Je vais chercher les points fixes. Comment savez vous qu'il y'en 2?

Non, il est juste demandé de resoudre la recurrence, avec v(0)=0 comme condition initiale: V(n) = 1 / (4 - V(n-1))

Qu'est ce qui te faire croire qu'il n'est pas complet?

salut, j'ai un problème avec cette recurrence: V(n) = 1 / (4 - V(n-1)) avec V(0) = 0 Je n'arrive pas à la ramener sous la forme d'une recurrence lineaire. j'ai essayé de faire un changement comme ceci: S(n) = Exp (V(n)) puis S(n) = log (v(n)) mais cela ne m'avance à rien. Je crois qu'il faudrait d'a...