Bonsoir,
je recherche un coup de main.  
Je révise mes partiels d'algo. avancée et je voudrais savoir si mes évaluations de complexité sont correctes et si non j'aimerais si possible que l'on m'explique pourquoi.  
Ces morceaux d'algo me posent problème, du moins je ne suis pas certain du résultat.
 

 
Ca vous semble correct ?
Merci d'avance

pour la 2ème complexité, on peut améliorer l'estimation à O(ln(ln(n))).

la 3ème complexité est bien O(n)

pour la 1ere complexité, en déroulant l'aglorithme, on sent que O(n) n'est pas la bonne réponse. Ca serait plutôt O(n.ln(n))

Je te remercie de ton aide
J'ai bien vu tes édits.  
Pour le 1er, je suis finalement d'accord pour du n.log(n).  
Pour ce qui est du second je suis pas contre du log(log(n)), mais je vois pas bien comment le sentir. Simplement parce que c'est plus petit que du log(n) ?

pour la 2ème complexité, il faut partir de l'inégalité j<k dans la boucle tantque.
Si on pose i comme l'indice d'itération, on a j=2^(2^(i-1)) et k=n^i
En approximant j à 2^(2^i), il s'agit donc de résoudre 2^(2^i)/n^i < 1
Ce qui en faisant quelques transformations et approximations nous amène à i < log2(log2(n))

Merci, je vois comment tu fais. En cours on n'est pas aussi précis, on ne précise même pas la base du log.

 
Pour celui là, si je me suis pas planté, on devrait trouver log3(log2(n)) ?

non, tout simplement O(log2(n))
ou plus simplement O(ln(n))

Bonjour,
 
Moi aussi je révise les partiels.
J'avoue que je ne comprend pas grand choses à la complexité.
 
Quelle est la méthode pour résoudre cela ??
 
Beaucoup d'instinct je sais mais tout de meme ^^
 
Merci

Euh, l'instinct pour calculer les complexité ???
Plutôt des maths oui !

Pour cet algo, je trouve : nlog(n)
Je sais que c'est pas ça
Je ne sais pas comment faire !

hmmm, imagine que tu a à la ligne 2, j:=n au lieu de j:=i.
tu obtiens donc une boucle tantque qui s'exécute en O(n).
Comme la boucle pour a n itération, on aurait une complexité de O(n²).
 
La question qu'on doit se poser maintenant c'est : "est-ce que le fait d'avoir j:=i au lieu de j:=n change quelque chose à la complexité de l'algo ?" => réponse non car on se rend compte que la complexité de cet algo revient à calculer somme(de 1 à n/2) = n(n/2+1)/4 qui implique donc une complexité de O(n²), CQFD

C'est n'est pas plutot log2(n) dans le Tant Que, etant donné qu'on ne fais pas ca pour toutes les valeurs de n à 1 ??

En regardant mon calcul, j'ai fait une erreur.
Dans tantque, si on pose k comme indice d'itération on doit résoudre j/2^k>1 <=> k < log2(j) donc une complexité en O(log2(n)).
Quand ensuite on passe avec la boucle pour, on observe un comportement amusant : Complexité = somme(log2(i), i=1..n) = somme(log2(n!))
La formule de stirling doit ensuite pouvoir donner une complexité de l'algo de l'ordre de O(ln(n))

Merci beaucoup ^^
 
Il y a une question sur laquelle je seche fortement :
 

 
En posant comme indice k, on doit résoudre dans le tant que k<i*(n-i)  
Puis en passant de le pour on doit faire somme(i*(n-i) , i=1..n)...
Mais je suis vraiment pas sur. C'est comme ca qu'il faut proceder??

Non, car ici j n'est initialisé qu'au début, à l'extérieur de la boucle pour.
Une petite simulation s'impose pour voir ce qu'il se passe.
Tu en induit une règle que tu dois en principe --- si on veut être rigoureux --- démontrer, le plus souvent par réccurence.

Raahh minceeeee
Je comprend plus rien ^^

Imaginons, n=100
j=1, i=1, i*(n-i)=99
j=2, i=1, i*(n-i)=99
...
j=99, i=1, i*(n-i)=99
j=99, i=2, i*(n-i)=196
j=100, i=2, i*(n-i)=196
...
j=196, i=2, i*(n-i)=196
j=196, i=3, i*(n-i)=291
...
j=291, i=3, i*(n-i)=291
...

Le maximum de i*(n-i) est atteint pour i=n/2 qui provoque également la fin de l'algorithme.
On constate que j est la variable d'itération et qu'il n'est pas nécessaire d'en introduire une nouvelle.

j a une progression linéaire et est même égal à i*(n-i) quand l'algo s'arrête. On a donc une complexité de O(n/2) soit O(n).

Zut, en fait je me plante sur les exemples de Shynia... et l'exam c'est demain aprem...    
Bon je reprend tout ca...

pwill > quelle école/université ? quelle année ? si ce n'est pas indiscret

 
 
 
Edit: j'ai effacé...  
Si je ne suis pas assez rigoureux pour bien faire tourner l'algo... je ne vais pas aller loin.
En fait j'ai pas détecté que l'arrêt de la boucle tant provoque l'arrêt de la boucle pour  
 
Je suis d'accord que l'algo s'arrête à i = n/2. j est la variable d'itération.  
Du coup ce que je ne saisis pas, c'est pourquoi j ne serait pas la complexité de l'algo ?
A moins que je me trompe à nouveau en faisant tourner l'algo, je trouve j= (n/2)*(n-n/2)= n*n/4.  
On a n/2 passages dans la boucle pour, mais ces passages impliquent n*n/4 passages dans la boucle tant que, ce n'est pas ce qui importe pour la complexité ?    
 
 

Bordeaux 1, 3ème année de licence Info
D'ailleurs tu ne devrais pas avoir de mal à trouver l'origine de ces exemples
 
Pour Shynia, j'imagine qu'il s'agit de la même université et du même cours  

J'ai repris l'avant dernier message où j'avais écrit des bétises. J'ai corrigé mais il reste un point à éclaircir dans ma tête...
 
Bon quoi qu'il en soit, merci pour aide  
Et rien de grave si tu ne réponds pas d'ici demain midi, il est trop tard pour préparer un partiel  

Ahh c'est beau les études d'info, enfin c'est mieux lorsque l'on a finit.
 
Qu'est ce que j'ai pu en bouffer des conneries comme ça...

je serais curieux de savoir le nb d'ingé en infos qui, une fois dans la vie active, calculent encore la complexité de leurs algos...

On est pas nombreux effectivement, mais l'expérience prime sur le calcul.
 
Une fois que tu t'es tappé pendant les études les différents coeff de chaque systèmes de tri, tu sais lesquels sont les plus complexes.

certes, mais ça viendrait à l'idée d'aucun ingé d'utiliser le buble sort pour trier. De suite, il va partir sur le quick sort (même si c'est pas le plus performant) ; en +, on le trouve implémenté de base dans la plupart des langages de dév.

bah, le calcul de la complexité a au moins le mérite de sensibiliser au problème. Et vu le nombre d'appli mal codée, je trouve même qu'une petite révision pour bcp d'ingé ne leur ferait pas de mal

Le quick sort est utilisé par tout le monde même si une dicho pour le fun de temps en temps, ça fait pas de mal hehe !!
 
Sinon, il est clair que cela ne ferait pas de mal à certains mais bon tu saura avec le temps que le problème bien souvent est justement le ....temps.

Merci pour la leçon angelx24, mais disons que je ne suis plus à l'école depuis longtemps

Et bien alors, tu sais que les programmeur sont fainéants de nature et que le temps manque pour la grande majorité des projets, cahiers des charges  etc... donc tu connais la musique du cycle en V.

Si vous avez quelques minutes, vous pensez quoi de ces boucles:
 

Pb à la ligne 2 : pas de borne max dans la boucle pour

Désolé, 2 erreurs en recopiant le sujet   J'ai édité.

 
Normal, elle n'a pas la moindre importance

clair, tu passe d'un log a l'autre par simple multiplication.
 
Si tu voulais preciser a ce point, il faudrait dire precision en a+b*n+c*n*log(n) etc . . .
 
on se contente dans cet exemple de n*log(n) qui est le facteur dominant des que n devient grand.