Discussion :

[neeoo11]

bonjour,
en essayant de refaire mon TD sur la complexité algorithmique,
j'ai eu deux problème :

1-trouver la complexité de l'algo :
for(i=n; i>1; i=i/2)
for( j=0; j<i; j++)
x := x+a

2- on a le code suivant :
si a>b alors
pour i = 1 à n faire
x := x+a
sinon x := x+b

Question : trouver une instance du code de coût t(indice avg)


Merci pour votre aide !!

[lcfseth]

1- Pour la premiere, c'est assez simple à priori :

for(i=n; i>1; i=i/2)
for( j=0; j<i; j++)

On pose la suite Un. U(0) = n; U(k+1)=U(k)/2.

Il est claire que K varie entre 0 et E(Log2(n)) : Partie entiere de Log2 de n.
Pour chaque valeur de k on a U(k) iteration pour la deuxieme boucle. Donc la complexité devrait etre
Somme( k=0..E(Log2(n)), U(k)) < U(0)*Log2(n). (U est decroissante.)
=> o(nLog(n))

2- Je sais pas trop ce que tu veux dire par "instance du code de coût t(indice avg)" mais j'imagine que tu recherche le cout en moyenne de cet algorithm.

Commencons par le cout dans le cas optimal : b>=a, c'est 1.
Cout dans le pire des cas : b<a, c'est n.
N'ayant aucune informations sur a ou b , je suppose equiprobable les cas a>b et a<b + le cas a=b qu'on peut negliger. donc cela donne
n+1/2 => O(n/2)

Ps: je suis moi meme qu'un etudiant, donc je suis pas à 100% sur de la veracite, particulierement pour le second algo dont la solution me parait trop simpliste. Je profite simplement de ton post pour m'exercer