java - Gran análisis de O para este ciclo

for-loop big-o

Question

 sum = 0;
for (i = 1; i <= n; i++) { //#1
for (j = 1; j <= i * i; j++) { //#2
if (j % i == 0) { //#3
for (k = 1; k <= j; k++) { //#4
sum++;
}
}
} 

}

Lo anterior me confundió

Suppose #1 runs for N times
#2 runs for N^2 times
#3 runs for N/c since for N inputs N/c could be true conditions
#4 runs for N times

Por lo tanto, aproximadamente podría estar mirando a O (N ^ 5). No estoy seguro. Por favor ayuda a aclarar

EDITAR Me estaba preguntando el tiempo de ejecución en el if(j%i==0) . Como toma N^2 entradas de su bucle principal, podría estar haciendo (N^2)/c ejecuciones en lugar de N/c

Answer 1

@PeterLawrey hizo los cálculos, aquí hay puntos de referencia trazados en el gráfico ( mi conjunto de datos - n frente al tiempo de ejecución en microsegundos).

Básicamente, ejecuto el código en cuestión varias veces con diferente n entrada (eje X). Luego dividí el tiempo promedio de ejecución entre n^5 , n^4 y n^3 funciones y tracé eso:

^{Imagen de tamaño completo}

Tenga en cuenta que esta es una escala logarítmica y que todas las funciones se escalaron para estar más o menos en el mismo rango.

Adivina qué, el tiempo de ejecución de avergae t(n) dividido por n^5 sigue disminuyendo, mientras que t(n)/n^3 sigue creciendo. Solo t(n)/n^4 se estabiliza cuando se aproxima al infinito, lo que demuestra que el tiempo de ejecución promedio es de hecho O(n^4) .

Answer 2

Yo diría que es O (N ^ 4) ya que es lo mismo que.

 for (int i = 1; i <= n; i++) //#1 O(n ...
for (int j = i; j <= i * i; j+=i) //#2 ... * n ...
for (int k = 1; k <= j; k++) //#4 ... * n^2) as j ~= i^2
sum++;

o

public static void main(String... args) {
int n = 9000;
System.out.println((double) f(n * 10) / f(n));
}
private static long f(long n) {
long sum = 0;
for (long i = 1; i <= n; i++) //#1
for (long j = 1; j <= i; j++) //#2
sum += i * j; // # 4
return sum;
}

huellas dactilares

9996.667534360826

que está muy cerca de 10 ^ 4

Answer 3

Creo que la respuesta, usando la notación Sigma, sería como la siguiente: