[L2] Complexité algorithmique (Java)

[Deluxor]

Bonjour à tous!

Pouvez-vous m'indiquer quelle méthode suivre pour résoudre cet exercice?


public static int algo(int m, int n){
[INDENT]for (int i=0; i<n; i++)[/INDENT]
[INDENT][INDENT]for (int j=i; j<n; j++)[/INDENT][/INDENT]
[INDENT][INDENT][INDENT]m++;[/INDENT][/INDENT][/INDENT]
[INDENT]return m;[/INDENT]
}

0) Donnez la valeur renvoyée par algo(0, 4). (Je pense à 12 ?)
1) Donnez la valeur renvoyée par algo(0, 199). (Faut-il conjecturer quelque chose par rapport à la question 0?)
2) Donnez la complexité de algo(0, n).
3) Donnez la complexité de algo(m, 199).


Je vous remercie,

Deluxor.

[mrif]

Bonjour à tous!

Pouvez-vous m'indiquer quelle méthode suivre pour résoudre cet exercice?


public static int algo(int m, int n){
[INDENT]for (int i=0; i<n; i++)[/INDENT]
[INDENT][INDENT]for (int j=i; j<n; j++)[/INDENT][/INDENT]
[INDENT][INDENT][INDENT]m++;[/INDENT][/INDENT][/INDENT]
[INDENT]return m;[/INDENT]
}

0) Donnez la valeur renvoyée par algo(0, 4). (Je pense à 12 ?)
1) Donnez la valeur renvoyée par algo(0, 199). (Faut-il conjecturer quelque chose par rapport à la question 0?)
2) Donnez la complexité de algo(0, n).
3) Donnez la complexité de algo(m, 199).


Je vous remercie,

Deluxor.

Regarde ce que fait la boucle interne. Elle ajoute (n-i) fois 1 à m puisqu'on commence à j=i et on s'arrête à j = n-1. La boucle externe commence à i = 0 et s'arrête à i = n-1 et ajoute à m la somme n +(n-1) + (n-2) + .... + 2 + 1, ce qui donne m+[n(n+1)]/2.

0) on trouve 0 + (4*5)/2 = 10
1) 0 + 199*200/2 = 19900
3) n(n+1)/2
4) n(n+1)/2 indépendant de m

Modif: Dans 4) remplacer n par 199

[fatal_error]

lol

je me disais quel est le boulet qui met un static.

Puis apres j'ai lu java :ptdr:

[Deluxor]

Merci beaucoup!

Je vais y songer! Ces programmes me sont tellement pas familiers... ^^