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

Eu não entendo como quando j = i, 2i, 3i ... o último forloop é executado n vezes. Acho que simplesmente não entendo como chegamos a essa conclusão com base na ifdeclaração.

Edit: Eu sei como calcular a complexidade de todos os loops, exceto por que o último loop é executado i vezes com base no operador mod ... Eu simplesmente não vejo como é eu. Basicamente, por que não posso subir até i * i em vez de eu?

Vamos rotular os loops A, B e 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++;
            }
        }
    }
}

• O loop A itera O ( n ) vezes.
• Laço B itera O ( i ² ) vezes por iteração de um . Para cada uma dessas iterações:
  • j % i == 0 é avaliado, o que leva tempo O (1).
  • Em 1 / i dessas iterações, o loop C itera j vezes, realizando O (1) trabalho por iteração. Uma vez que j é O ( i ² ) em média, e este só é feito por 1 / i iterações do ciclo B, o custo médio é O ( i ²  /  i ) = O ( i ).

Multiplicando tudo isso juntos, obtemos O ( n  ×  i ²  × (1 +  i )) = O ( n  ×  i ³ ). Como i é, em média, O ( n ), este é O ( n ⁴ ).

A parte complicada disso é dizer que a ifcondição é verdadeira apenas 1 / i do tempo:

Basicamente, por que não posso subir até i * i em vez de eu?

De fato, jsobe j < i * i, não apenas j < i. Mas a condição j % i == 0é verdadeira se e somente se jfor um múltiplo de i.

Os múltiplos de identro do intervalo são i, 2*i, 3*i, ..., (i-1) * i. Existem i - 1esses, portanto, o loop C é atingido i - 1vezes apesar dos i * i - 1tempos de iteração do loop B.

• O primeiro loop consome niterações.
• O segundo loop consome n*niterações. Imagine o caso quando i=n, então j=n*n.
• O terceiro loop consome niterações porque é executado apenas algumas ivezes, onde ié limitado nno pior dos casos.

Assim, a complexidade do código é O (n × n × n × n).

Espero que isso ajude você a entender.

Todas as outras respostas estão corretas, só quero alterar o seguinte. Eu queria ver se a redução de execuções do k-loop interno era suficiente para reduzir a complexidade real abaixo. O(n⁴).Então, escrevi o seguinte:

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

Depois de executar isso, torna-se óbvio que a complexidade é de fato n⁴. As últimas linhas de saída são assim:

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

O que isso mostra é que a diferença relativa real entre o valor real n⁴ e a complexidade desse segmento de código é um fator assintótico em relação a um valor próximo 0.124...(na verdade, 0,125). Embora não nos dê o valor exato, podemos deduzir o seguinte:

A complexidade do tempo é n⁴/8 ~ f(n)ondef está sua função / método.

• A página da wikipedia na notação Big O indica nas tabelas das 'notações Família de Bachmann – Landau' que a ~ definição do limite dos dois lados do operando é igual. Ou:

  f é igual a assintoticamente

(Escolhi 363 como limite superior excluído, porque n = 362 é o último valor para o qual obtemos um resultado razoável. Depois disso, excedemos o espaço longo e o valor relativo se torna negativo.)

O usuário kaya3 descobriu o seguinte:

A constante assintótica é exatamente 1/8 = 0,125, a propósito; aqui está a fórmula exata via Wolfram Alpha .

Retirar if e module sem alterar a complexidade

Aqui está o método original:

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

Se você está confuso com o ifmódulo e, basta refatorá-lo, jsaltando diretamente de ipara 2*ipara 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;
}

Para facilitar ainda mais o cálculo da complexidade, é possível introduzir uma j2variável intermediária , para que cada variável de loop seja incrementada em 1 a cada iteração:

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

Você pode usar a depuração ou a velha escola System.out.printlnpara verificar se o i, j, ktrigêmeo é sempre o mesmo em cada método.

Expressão de formulário fechado

Conforme mencionado por outros, você pode usar o fato de que a soma dos primeiros n números inteiros é igual a n * (n+1) / 2(consulte números triangulares ). Se você usar essa simplificação para cada loop, obterá:

public static long f4(int n) {
    return (n - 1) * n * (n - 2) * (3 * n - 1) / 24;
}

Obviamente, não é a mesma complexidade que o código original, mas retorna os mesmos valores.

Se você pesquisar os primeiros termos no Google, poderá notar que eles 0 0 0 2 11 35 85 175 322 546 870 1320 1925 2717 3731aparecem em "Números Stirling do primeiro tipo: s (n + 2, n)". , com dois 0s adicionados no início. Isso significa que sumé o número de Stirling do primeiro tipo s(n, n-2) .

Vamos dar uma olhada nos dois primeiros loops.

O primeiro é simples, está repetindo de 1 a n. O segundo é mais interessante. Vai de 1 a i ao quadrado. Vamos ver alguns exemplos:

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  

No total, o i and j loopscombinado tem 1^2 + 2^2 + 3^2.
Existe uma fórmula para a soma dos primeiros n quadrados n * (n+1) * (2n + 1) / 6, que é aproximadamenteO(n^3) .

Você tem um último k loopque executa um loop de 0 a jse e somente se j % i == 0. Desde jvai de 1 a i^2, j % i == 0é verdade por ivezes. Como a i loopiteração termina n, você tem um extra O(n).

Então você tem O(n^3)a partir i and j loopse outra O(n)a partir k loopde um total deO(n^4)