Discussion :

[baobab95]

bonjour,
voila dans mon exam de java il y avait cette question, mais je n'ai pas compris la réponse !!

Code:

Code :

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

1
2
3
4
5
Class D {
public int x;
public D() { x = 3;}
public D (int a) {this(); x=x+a;}
public D (int a, int b){ this(b); x=x-a;}

Qu'afficheras le code suivant ?

Code:

Code :

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

1
2
D a = nex D(5,6);
System.out.println(a.x);

la réponse est 4..Pourquoi ?

[michel.di]

D(5,6) fait appel a D(6) qui initialise x à 3 et D(6) fait x+=6 soit 9 et D(5,6) fait 9-5 soit 4
j'espère avoir été clair!

[baobab95]

[QUOTE=michel.di
j'espère avoir été clair! [/QUOTE]

Oui ! Merci beaucoup !!

[michel.di]

ravi de t'avoir aidé!

[baobab95]

je vais en profiter car j'ai encore des doutes au sujet d'une chose !
la compléxité !! (c'est ce qui me fais me planter à chaque fois !)
voila l'énoncé :
on considère la boucle suivante (n > 0) :
for (int i = 0 ; i < n; i+=1) for (int j = 1; j < n; j=2*j) f(i);

1) Le nombre d'apels de f est un O(n)
2) Le nombre d'apels de f est un O(n²)
3) Le nombre d'apels de f est un O(log(n))
4) Le nombre d'apels de f est un O(nlog(n))

au passage si quelqu'un à un bon cours sur la compléxité je prends car je suis vraiment nul !
pour moi la bonne réponse été la 2 (car il y a deux boucle imbriquée) mais apparament c'est la 4...

[michel.di]

il s'agit bien de la 4 car pour ta première boucle tu fais bien n parcours mais pour la seconde tu divises par deux à chaque tour et il s'agit alors de log n !
J'ai eu des cours cette année en Master mais les exemples du pdf ne sont pas corrigés, ça ne t'aidera pas!

[baobab95]

j'ai vraiment pas tout saisi sur la complexité !
alors d'aprés ce que j'ai lu dans ta réponse, cela dépend aussi de ce qu'il y a comme condition dans la boucle, et pas uniquement la boucle...
pour moi jusqu'ici c'était une boucle for est de compléxité n si on imbrique une boucle dans une autre on passe a n² et ainsi de suite, en revanche si les boucle ne sont pas imbriquée cela fait 2n...

alors comment reconnaitre réellement lorsque c'est n ou log(n) ?
si tu as eu des cours tu peux peut-etre m'aider ! moi je suis en 1iere année de licence...Désolé si tu n'as pas le temps ce n'est pas grave !

Merci pour tout

[Astartee]

on considère la boucle suivante (n > 0) :

Code :

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

1
2
3
for (int i = 0 ; i < n; i+=1)
   for (int j = 1; j < n; j=2*j)
      f(i);

pour moi la bonne réponse été [Le nombre d'apels de f est un O(n²)] (car il y a deux boucle imbriquée) mais apparament c'est [Le nombre d'apels de f est un O(nlog(n))]

Il y a certes 2 boucles, mais ce ne sont pas les mêmes !

Première boucle : for (int i = 0 ; i < n; i+=1)
A chaque passage dans la boucle, on incrémente i de 1. Donc au k-ième passage dans la boucle i=k.
On sort de la boucle dès que i>=n, c'est à dire dès que k>=n.
On va donc passer environ n fois dans la boucle.

Deuxième boucle : for (int j = 1; j < n; j=2*j)
A chaque passage dans la boucle, on multiplie j par 2. Donc au k-ième passage dans la boucle j=2^k.
On sort de la boucle dès que j>=n, c'est à dire dès que 2^k>=n.
On va donc passer environ log2(n) fois dans la boucle.

pour moi jusqu'ici c'était une boucle for est de compléxité n si on imbrique une boucle dans une autre on passe a n² et ainsi de suite, en revanche si les boucle ne sont pas imbriquée cela fait 2n...

Ce n'est pas parce qu'il y a une condition de sortie de la forme "indice < n" qu'on va passer n fois dans la boucle. Il faut aussi regarder ce qu'on fait de l'indice : sa valeur initiale, son évolution... L'indice est-il également modifié à l'intérieur de la boucle ? Peut-on sortir de la boucle sans respecter la condition de sortie (avec un break) ? etc

[baobab95]

ok je comprend deja un peu mieux...

Mais lorsqu'une boucle fais
for (int i =0; i < n; i+=3)

elle est de complexité O(n)...
C'est parcequ'on considére qu'on fais environ n fois la chose ?
Enfaite on est dans le cas log(n) que lorsqu'on s'éloigne assez des "environs n fois"
comme par exemple dans le cas d'une multiplication ou d'une division.

Cela est correct ??