"java int soma = 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++) { soma++; } } } }
Não compreendo como quando j = i, 2i, 3i... o último laço "para" corre n vezes. Acho que simplesmente não compreendo'não compreendo como chegámos a essa conclusão com base na declaração 'se'.
Editar: Sei como calcular a complexidade de todos os loops excepto porque é que o último loop executa i vezes com base no operador mod... Apenas não't vejo como's i. Basicamente, porque é que't j % eu subo para i * i em vez de i?
Let's rotulam os loops A, B e C:
"java int soma = 0; // laço 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++) { soma++; } } } }
- Loop A itera O(*n*) vezes.
- Loop B itera O(*i*<sup>2</sup>) vezes **por iteração de A***. Para cada uma destas iterações:
- `j % i == 0` é avaliado, o que demora O(1) tempo.
- Em 1/*i* destas iterações, o loop C itera *j* vezes, realizando O(1) trabalho por iteração. Como *j* é O(*i*<sup>2</sup>) em média, e isto só é feito para as iterações de 1/*i* do laço B, o custo médio é O(*i*<sup>2</sup> / *i*) = O(*i*).
Multiplicando tudo isto em conjunto, obtemos O(*n* × *i*<sup>2</sup> × (1 + *i*)) = O(*n* × *i*<sup>3</sup>). Uma vez que *i* é em média O(*n*), isto é O(*n*<sup>4</sup>).
---
A parte complicada disto é dizer que a condição "se" é apenas verdadeira 1/*i* do tempo:
> Basicamente, por que é que o can't j % i vai até i * i em vez de i?
De facto, `j` vai até `j < i * i`, não apenas até `j < i`. Mas a condição `j % i == 0` é verdadeira se e só se `j` for um múltiplo de `i`.
Os múltiplos de `i` dentro do intervalo são `i`, `2*i`, `3*i`, ..., `(i-1) * i`. Existem `i - 1` destes, por isso o loop C é atingido `i - 1` vezes apesar do loop B iterating `i * i - 1` vezes.
n
iterações.n*n
. Imagine o caso quando i=n
, depois j=n*n
.n' iterações, porque só é executado
i' vezes, onde i' está limitado a
n' no pior dos casos.Assim, a complexidade do código é O(n×n×n×n).
Espero que isto o ajude a compreender.
Todas as outras respostas estão correctas, quero apenas emendar o seguinte. Queria ver, se a redução das execuções do k-loop interno era suficiente para reduzir a complexidade real abaixo de 'O(n⁴).`Então escrevi o seguinte:
``java para (int n = 1; n < 363; ++n) { int soma = 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) { soma++; } } } }
long cubic = (longo) Math.pow(n, 3);
hipCúbico longo = (comprido) Math.pow(n, 4);
parente duplo = (duplo) (soma / (duplo) hipCúbico);
System.out.println("n = " + n + ": iterações = " + soma +
", n³ = " + cúbico + ", n⁴ = " + hipCúbico + ", rel = " + relativo);
}
Depois de executar isto, torna-se óbvio, que a complexidade é de facto `n⁴`. As últimas linhas de saída parecem-se com isto:
n = 356: iterações = 1989000035, n³ = 45118016, n⁴ = 16062013696, rel = 0,12383254507467704 n = 357: iterações = 2011495675, n³ = 45499293, n⁴ = 16243247601, rel = 0,12383580700180696 n = 358: iterações = 2034181597, n³ = 45882712, n⁴ = 16426010896, rel = 0,1238390505075183874 n = 359: iterações = 2057058871, n³ = 46268279, n⁴ = 16610312161, rel = 0,1238422764747628734 n = 360: iterações = 2080128570, n³ = 46656000, n⁴ = 16796160000, rel = 0,12384548432498857 n = 361: iterações = 2103391770, n³ = 47045881, n⁴ = 16983563041, rel = 0,12384867444612208 n = 362: iterações = 2126849550, n³ = 47437928, n⁴ = 17172529936, rel = 0,1238518469862343
O que isto mostra é que a diferença relativa real entre a `n⁴' real e a complexidade deste segmento de código é um factor assimptótico para um valor em torno de `0,124...` (na realidade 0,125). Embora não nos dê o valor exacto, podemos deduzir, o seguinte:
A complexidade temporal é `n⁴/8 ~ f(n)` onde `f` é a sua função/método.
* A página wikipedia na notação Big O declara nas tabelas de 'Notações da Família de Bachmann-Landau' que o `~` define o limite dos dois lados do operando é igual. Ou:
> f é igual a g assimptóticamente
(Escolhi 363 como limite superior excluído, porque `n = 362` é o último valor para o qual obtemos um resultado sensato. Depois disso, excedemos o espaço longo e o valor relativo torna-se negativo).
O utilizador kaya3 descobriu o seguinte:
> A constante assimptótica é exactamente 1/8 = 0,125, a propósito; [aqui está a fórmula exacta 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
*** ***
Deixemos's dar uma vista de olhos aos dois primeiros loops.
A primeira é simples, it's looping de 1 a n. A segunda é mais interessante. Passa de 1 para i ao quadrado. Vamos's 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, os loops i e j combinados têm
1^2 + 2^2 + 3^2. Existe uma fórmula para a soma dos primeiros n quadrados,
n (n+1) (2n + 1) / 6, que é aproximadamente
O(n^3)`.
Tem um último k loop
que faz loops de 0 a j
se e só se j % i == 0
. Uma vez que j
vai de 1 a i^2
, j % i == 0
é verdadeiro para i
vezes. Uma vez que o i loop
itera sobre n
, tem um O(n)
adicional.
Então tem O(n^3)
de i e j loops
e outro O(n)
de k loop
para um total de O(n^4)
if
e modulo sem alterar a complexidadeAqui 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 estiver confuso com o "se" e o módulo, pode simplesmente refactorizê-los, com o "j" saltando directamente de "i" para "2i" para "3i"... ... :
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, pode introduzir uma variável intermediária j2
, de modo a que cada variável de laço 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;
}
Pode utilizar o System.out.println
debugging ou old-school para verificar que i, j, k
triplet é sempre o mesmo em cada método.
Como mencionado por outros, pode utilizar o facto de que a soma dos primeiros inteiros n
é igual a n * (n+1) / 2
(ver números triangulares). Se utilizar esta simplificação para cada laço, obtém :
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 devolve os mesmos valores.
Se pesquisar no Google os primeiros termos, pode notar que 0 0 0 2 11 35 85 175 322 546 870 1320 1925 2717 3731
aparecem em "Stirling numbers of the first kind: s(n+2, n)", com dois 0
s adicionados no início. Isto significa que o sum
é o número Stirling do primeiro tipo s(n, n-2)
.