Comparer théta de n^2 et théta de n^3

par **rvfranck** » 10 Oct 2007, 06:50

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 trouve ça tellement évident que je pense qu'il y'a un piège derrière ce problème. En plus je n'arrive pas à le justifier.

par **rvfranck** » 10 Oct 2007, 06:59

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?

par **AngeBlanc** » 10 Oct 2007, 10:03

D'après mes dernières notions d'infos, si tu dis que l'algo est en THETA(n^2) alors le temps peut s'écrite sous la forme :
TempsA(n) = A*n^2 + o(n^2) avec A une constante positive.

De la même façon :
TempsB(n) = B*n^3 + o(n^3) avec B une constante positive.

Il suffit alors de voir pour quels n B*n^3< A*n^2...

(Donc si A grand et B petit, ce n'est peut-être pas n = 2...)

D'où la discussion, en l'infini, oui A préférable à B, mais pour les premiers termes...

Bon allez, on a :

B*n^3 < A*n^2

<=> B*n < A ( n est positif)
<=> n < A/B

Donc, pour n <= PartieEntière(A/B), B préférable a A...

Voilà ce que j'écrirais. :id:

Bon courage !

par **rvfranck** » 10 Oct 2007, 13:25

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

par **rvfranck** » 11 Oct 2007, 21:22

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 toi?

par **abcd22** » 11 Oct 2007, 21:27

Bonsoir,
Ça dépend surtout de si l'algo polynomial est en

ou en

...

par **AngeBlanc** » 11 Oct 2007, 23:13

A moins d'avoir le temps exact d'éxécution, on ne peut dire grand chose ^^

Maintenant, en +oo, oui on sait ce qu'il se passe, mais çà n'est pas toujours ce qu'il faut en info.

Bon courage.

Comparer théta de n^2 et théta de n^3

comparer théta de n^2 et théta de n^3

Qui est en ligne