``java int sum = 0 ; for(int i = 1 ; i < n ; i++) { for(int j = 1 ; j < i * i ; j++) { si(j % i == 0) { for(int k = 0 ; k < j ; k++) { somme++ ; } } } }
Je ne comprends pas comment lorsque j = i, 2i, 3i... la dernière boucle `for` s'exécute n fois. Je suppose que je ne comprends pas comment on est arrivé à cette conclusion en se basant sur l'instruction `if`.
Edit : Je sais comment calculer la complexité pour toutes les boucles sauf pour savoir pourquoi la dernière boucle s'exécute i fois en se basant sur l'opérateur mod... Je ne vois pas pourquoi c’est i. En fait, pourquoi j % i ne peut pas aller jusqu’à i * i plutôt que i ?
Étiquettons les boucles A, B et C :
"java int somme = 0 ; // boucle A for(int i = 1 ; i < n ; i++) { // boucle B for(int j = 1 ; j < i * i ; j++) { if(j % i == 0) { // boucle C for(int k = 0 ; k < j ; k++) { somme++ ; } } } }
- La boucle A itére O(*n*) fois.
- La boucle B itére O(*i*<sup>2</sup>) fois **par itération de A**. Pour chacune de ces itérations :
- `j % i == 0` est évalué, ce qui prend O(1) fois.
- Sur 1/*i* de ces itérations, la boucle C itére *j* fois, en faisant O(1) fois le travail par itération. Puisque *j* est O(*i*<sup>2</sup>) en moyenne, et que cela n'est fait que pour 1/*i* itérations de la boucle B, le coût moyen est O(*i*<sup>2</sup> / *i*) = O(*i*).
En multipliant tout cela ensemble, on obtient O(*n* × *i*<sup>2</sup> × (1 + *i*)) = O(*n* × *i*<sup>3</sup>). Puisque *i* est en moyenne O(*n*), cela donne O(*n*<sup>4</sup>).
---
Le plus difficile est de dire que la condition "si" n'est vraie que 1/*i* de l'époque :
> Fondamentalement, pourquoi j % i ne peut-il pas aller jusqu'à i * i plutôt que i ?
En fait, "j" va jusqu'à "j < i * i", et pas seulement jusqu'à "j < i". Mais la condition "j % i == 0" est vraie si et seulement si "j" est un multiple de "i".
Les multiples de `i` dans la plage sont `i`, `2*i`, `3*i`, ..., `(i-1) * i`. Il y a `i - 1` de ces multiples, donc la boucle C est atteinte `i - 1` fois malgré l'itération de la boucle B `i * i - 1` fois.
n
parce qu'elle n'est exécutée que i
fois, où i
est limité à n
dans le pire des cas.Ainsi, la complexité du code est O(n×n×n×n×n).
J'espère que cela vous aidera à comprendre.
Toutes les autres réponses sont correctes, je veux juste modifier ce qui suit.
Je voulais voir si la réduction des exécutions de la boucle k interne était suffisante pour réduire la complexité réelle en dessous de O(n⁴).
J'ai donc écrit ce qui suit :
"Java pour (int n = 1 ; n < 363 ; ++n) { int somme = 0 ; for(int i = 1 ; i < n ; ++i) { for(int j = 1 ; j < i * i ; ++j) { if(j % i == 0) { for(int k = 0 ; k < j ; ++k) { somme++ ; } } } }
long cubique = (long) Math.pow(n, 3) ;
long hypCubique = (long) Math.pow(n, 4) ;
double relative = (double) (somme / (double) hypCubique) ;
System.out.println("n = " + n + " : itérations = " + somme +
", n³ = " + cubique + ", n⁴ = " + hypCubique + ", rel = " + relatif) ;
}
Une fois cette opération réalisée, il devient évident que la complexité est en fait "n⁴". Les dernières lignes de la sortie ressemblent à ceci :
n = 356 : itérations = 1989000035, n³ = 45118016, n⁴ = 16062013696, rel = 0,12383254507467704 n = 357 : itérations = 2011495675, n³ = 45499293, n⁴ = 16243247601, rel = 0,12383580700180696 n = 358 : itérations = 2034181597, n³ = 45882712, n⁴ = 16426010896, rel = 0,12383905075183874 n = 359 : itérations = 2057058871, n³ = 46268279, n⁴ = 16610312161, rel = 0,12384227647628734 n = 360 : itérations = 2080128570, n³ = 46656000, n⁴ = 16796160000, rel = 0,12384548432498857 n = 361 : itérations = 2103391770, n³ = 47045881, n⁴ = 16983563041, rel = 0,12384867444612208 n = 362 : itérations = 2126849550, n³ = 47437928, n⁴ = 17172529936, rel = 0,1238518469862343
Ce que cela montre, c'est que la différence relative réelle entre le `n⁴` réel et la complexité de ce segment de code est un facteur asymptotique vers une valeur autour de `0.124...` (en fait 0.125). Bien que cela ne nous donne pas la valeur exacte, nous pouvons en déduire ce qui suit :
La complexité temporelle est `n⁴/8 ~ f(n)` où `f` est votre fonction/méthode.
* La page wikipédia sur la notation Big O indique dans les tableaux de la "Famille des notations Bachmann-Landau" que la "~" définit la limite des deux côtés de l'opérande est égale. Ou :
> f est égal à g asymptotiquement
(J'ai choisi 363 comme limite supérieure exclue, car "n = 362" est la dernière valeur pour laquelle nous obtenons un résultat raisonnable. Après cela, nous dépassons l'espace long et la valeur relative devient négative).
L'utilisateur kaya3 a compris ce qui suit :
> La constante asymptotique est exactement 1/8 = 0,125, d'ailleurs ; [voici la formule exacte via Wolfram Alpha][1].
[1]: https://www.wolframalpha.com/input/?i=sum+for+i+%3D+1+to+n-1+of+i+*+i+*+%28i-1%29+%2F+2
*** ***
Examinons les deux premières boucles.
La première est simple, c'est une boucle de 1 à n. La seconde est plus intéressante. Elle va de 1 à i au carré. Voyons quelques exemples :
e.g. n = 4
i = 1
j loops from 1 to 1^2
i = 2
j loops from 1 to 2^2
i = 3
j loops from 1 to 3^2
Au total, les boucles i et j
combinées ont 1^2 + 2^2 + 3^2
.
Il existe une formule pour la somme des n premiers carrés, n * (n+1) * (2n + 1) / 6
, qui est approximativement O(n^3)
.
Vous avez une dernière boucle k
qui passe de 0 à j
si et seulement si j % i == 0
. Puisque j
va de 1 à i^2
, j % i == 0
est vrai pour i
fois. Puisque la boucle i
itére sur n
, vous avez un O(n)
supplémentaire.
Vous avez donc O(n^3)
des boucles i et j
et un autre O(n)
de la boucle k
pour un grand total de O(n^4)
.
Voici la méthode originale :
public static long f(int n) {
int sum = 0;
for (int i = 1; i < n; i++) {
for (int j = 1; j < i * i; j++) {
if (j % i == 0) {
for (int k = 0; k < j; k++) {
sum++;
}
}
}
}
return sum;
}
Si vous êtes confus par le if
et le modulo, vous pouvez simplement les refactoriser, avec j
sautant directement de i
à 2*i
à 3*i
... :
public static long f2(int n) {
int sum = 0;
for (int i = 1; i < n; i++) {
for (int j = i; j < i * i; j = j + i) {
for (int k = 0; k < j; k++) {
sum++;
}
}
}
return sum;
}
Pour faciliter encore le calcul de la complexité, vous pouvez introduire une variable intermédiaire "j2", de sorte que chaque variable de boucle soit incrémentée de 1 à chaque itération :
public static long f3(int n) {
int sum = 0;
for (int i = 1; i < n; i++) {
for (int j2 = 1; j2 < i; j2++) {
int j = j2 * i;
for (int k = 0; k < j; k++) {
sum++;
}
}
}
return sum;
}
Vous pouvez utiliser le débogage ou le System.out.println
de la vieille école pour vérifier que le triplet i, j, k
est toujours le même dans chaque méthode.
Comme mentionné par d'autres, vous pouvez utiliser le fait que la somme des premiers "n" entiers est égale à "n * (n+1) / 2" (voir [nombres triangulaires][1]). Si vous utilisez cette simplification pour chaque boucle, vous obtenez :
public static long f4(int n) {
return (n - 1) * n * (n - 2) * (3 * n - 1) / 24;
}
Il n'est évidemment pas aussi complexe que le code original, mais il renvoie les mêmes valeurs.
Si vous recherchez les premiers termes sur Google, vous pouvez remarquer que 0 0 0 2 11 35 85 175 322 546 870 1320 1925 2717 3731
apparaît dans ["Numéros Stirling du premier type : s(n+2, n)"][2], avec deux 0
ajoutés au début. Cela signifie que "somme" est le [numéro Stirling de la première espèce][3] "s(n, n-2)".
[1] : https://en.wikipedia.org/wiki/Triangular_number [2] : https://oeis.org/A000914 [3] : https://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind