Discussion :

[fasyr]

Bonjour,
Je m'entraine actuellement sur des exo d'algo et plus précisement sur la complexité et je voudrais avoir vos lumière sur mes réponses.

Voici mon exo:

Soit T_Test(n), T_A1(n) et T_A2(n) les temps d'exécutions des procédures Test, A1, A2 ou:
T_Test(n) E O(f(n)), T_A1(n) E O(g(n)) et T_A2 E O(h(n)) pour une entrée x de taille n.

Donnée une borne superieure de complexité pour le fragment de code suivant:
If Test(x)
then A1(x)
else A2(x)

Ma réponse est O(g(n))+1 ou O(h(n))+1

Vous en pensez quoi?

[PRomu@ld]

Je suppose que E signifie "appartient".

Je dirait simplement qu'il te manque le coût de la procédure test.

La complexité doit être alors :

O( f(n) + Max( g(n) , h(n) ) )

Sans plus d'informations sur f,g et h je doute qu'on puisse faire mieux.

[The-msx]

Je dirait simplement qu'il te manque le coût de la procédure test.

La complexité doit être alors :

O( f(n) + Max( g(n) , h(n) ) )

Sans plus d'informations sur f,g et h je doute qu'on puisse faire mieux.

Je pense que :
O( f(n) ) + Max( O(g(n)),O(h(n)) )

est plus correcte

[PRomu@ld]

En fait, ça n'est pas tout à fait la même chose. Et j'ai un doute sur ce qui est plus correct de ce qui ne l'est pas. D'ailleurs à bien y réfléchir le plus correct est semble t'il :

O( Max(f(n),g(n),h(n)) )

J'utilse pour ça le théorème de la somme :

Si f1(x) est dans O(g1(x)) et f2(x) est dans O(g2(x)) alors (f1+f2)(x) est dans Max(g1(x),g2(x))

[Furikawari]

En fait, ça n'est pas tout à fait la même chose. Et j'ai un doute sur ce qui est plus correct de ce qui ne l'est pas. D'ailleurs à bien y réfléchir le plus correct est semble t'il :

O( Max(f(n),g(n),h(n)) )

J'utilse pour ça le théorème de la somme :

Si f1(x) est dans O(g1(x)) et f2(x) est dans O(g2(x)) alors (f1+f2)(x) est dans Max(g1(x)+g2(x))

Il doit y avoir une typo à la fin, il faut lire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
Max(g1(x),g2(x))

[PRomu@ld]

Oui, effectivement.