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++;
            }
        }
    }
}

Je ne comprends pas comment quand j = i, 2i, 3i ... la dernière forboucle s'exécute n fois. Je suppose que je ne comprends tout simplement pas comment nous sommes arrivés à cette conclusion sur la base de la ifdéclaration.

Edit: je sais comment calculer la complexité de toutes les boucles, sauf pourquoi la dernière boucle exécute i fois en fonction de l'opérateur de mod ... Je ne vois tout simplement pas comment c'est i. Fondamentalement, pourquoi j% i ne peut-il pas aller jusqu'à i * i plutôt que i?

Étiquetons les boucles A, B et C:

int sum = 0;
// loop A
for(int i = 1; i < n; i++) {
    // loop B
    for(int j = 1; j < i * i; j++) {
        if(j % i == 0) {
            // loop C
            for(int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
}

• La boucle A itère O ( n ) fois.
• Boucle B itère O ( i ² ) fois par itération d'une . Pour chacune de ces itérations:
  • j % i == 0 est évalué, ce qui prend du temps O (1).
  • Sur 1 / i de ces itérations, la boucle C itère j fois, faisant O (1) travail par itération. Puisque j est O ( i ² ) en moyenne, et cela n'est fait que pour 1 / i itérations de la boucle B, le coût moyen est O ( i ²  /  i ) = O ( i ).

En multipliant tout cela ensemble, nous obtenons O ( n  ×  i ²  × (1 +  i )) = O ( n  ×  i ³ ). Puisque i est en moyenne O ( n ), c'est O ( n ⁴ ).

La partie délicate de cela est de dire que la ifcondition n'est vraie que 1 / i du temps:

Fondamentalement, pourquoi j% i ne peut-il pas aller jusqu'à i * i plutôt que i?

En fait, jne monte pas j < i * i, pas seulement j < i. Mais la condition j % i == 0est vraie si et seulement si jest un multiple de i.

Les multiples de l' iintérieur de la gamme sont i, 2*i, 3*i, ..., (i-1) * i. Il y en a i - 1, donc la boucle C est atteinte i - 1fois malgré les i * i - 1temps d' itération de la boucle B.

• La première boucle consomme des nitérations.
• La deuxième boucle consomme des n*nitérations. Imaginez le cas quand i=n, alors j=n*n.
• La troisième boucle consomme des nitérations car elle n'est exécutée que des ifois, où elle iest limitée ndans le pire des cas.

Ainsi, la complexité du code est O (n × n × n × n).

J'espère que cela vous aide à 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 ci-dessous. O(n⁴).J'ai donc écrit ce qui suit:

for (int n = 1; n < 363; ++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++;
                }
            }
        }
    }

    long cubic = (long) Math.pow(n, 3);
    long hypCubic = (long) Math.pow(n, 4);
    double relative = (double) (sum / (double) hypCubic);
    System.out.println("n = " + n + ": iterations = " + sum +
            ", n³ = " + cubic + ", n⁴ = " + hypCubic + ", rel = " + relative);
}

Après avoir exécuté cela, il devient évident que la complexité est en fait n⁴. Les dernières lignes de sortie ressemblent à ceci:

n = 356: iterations = 1989000035, n³ = 45118016, n⁴ = 16062013696, rel = 0.12383254507467704
n = 357: iterations = 2011495675, n³ = 45499293, n⁴ = 16243247601, rel = 0.12383580700180696
n = 358: iterations = 2034181597, n³ = 45882712, n⁴ = 16426010896, rel = 0.12383905075183874
n = 359: iterations = 2057058871, n³ = 46268279, n⁴ = 16610312161, rel = 0.12384227647628734
n = 360: iterations = 2080128570, n³ = 46656000, n⁴ = 16796160000, rel = 0.12384548432498857
n = 361: iterations = 2103391770, n³ = 47045881, n⁴ = 16983563041, rel = 0.12384867444612208
n = 362: iterations = 2126849550, n³ = 47437928, n⁴ = 17172529936, rel = 0.1238518469862343

Ce que cela montre, c'est que la différence relative réelle entre le réel n⁴et la complexité de ce segment de code est un facteur asymptotique vers une valeur autour 0.124...(en fait 0,125). Bien qu'il ne nous donne pas la valeur exacte, nous pouvons en déduire ce qui suit:

La complexité du temps est n⁴/8 ~ f(n)où se ftrouve votre fonction / méthode.

• La page wikipedia sur la notation Big O indique dans les tableaux de la «famille des notations Bachmann – Landau» que la ~définition de la limite des deux côtés de l'opérande est égale. Ou:

  f est égal à g asymptotiquement

(J'ai choisi 363 comme borne supérieure exclue, car n = 362c'est la dernière valeur pour laquelle nous obtenons un résultat sensible. 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, soit dit en passant; voici la formule exacte via Wolfram Alpha .

Supprimer ifet modulo sans changer la complexité

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 ifet modulo, vous pouvez simplement les refactoriser, en jsautant 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 plus le calcul de la complexité, vous pouvez introduire une j2variable intermédiaire , de sorte que chaque variable de boucle est 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 la vieille école System.out.printlnafin de vérifier que le i, j, ktriplet est toujours le même dans chaque méthode.

Expression de forme fermée

Comme mentionné par d'autres, vous pouvez utiliser le fait que la somme des premiers n entiers est égale à n * (n+1) / 2(voir les nombres triangulaires ). 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;
}

Ce n'est évidemment pas la même complexité que le code d'origine mais il renvoie les mêmes valeurs.

Si vous recherchez sur Google les premiers termes, vous pouvez remarquer qu'ils 0 0 0 2 11 35 85 175 322 546 870 1320 1925 2717 3731apparaissent dans "Numéros de Stirling du premier type: s (n + 2, n)". , avec deux 0s ajoutés au début. Cela signifie que sumc'est le nombre de Stirling du premier type s(n, n-2) .

Jetons un coup d'œil aux deux premières boucles.

Le premier est simple, il est en boucle de 1 à n. Le second est plus intéressant. Cela 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 i and j loopscombinés 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 k loopboucle de 0 à jif et seulement if j % i == 0. Depuis jva de 1 à i^2, j % i == 0est vrai pour les itemps. Puisque l' i loopitération est terminée n, vous en avez un de plus O(n).

Vous avez donc O(n^3)de i and j loopset un autre à O(n)partir k looppour un grand total deO(n^4)