¿Cuál es el Big-O de un bucle anidado, donde el número de iteraciones en el bucle interior se determina mediante la iteración actual del bucle externo?

Question

¿Cuál es el Big-O tiempo de complejidad de los siguientes bucles anidados:

for(int i = 0; i < N; i++) 
{
    for(int j = i + 1; j < N; j++)
    {
        System.out.println("i = " + i + " j = " + j);
    }

}

¿Sería O (N ^ 2) todavía?

Answer 1

Sí, es todavía O (n ^ 2), tiene un factor constante más pequeño, pero que no afecta a la notación O.

Answer 2

Sí. Recordemos la definición de Big-O: O (f (n)) por definición dice que el tiempo de ejecución T (n) ≤ kf (n) para alguna constante k . En este caso, el número de pasos será (n-1) + (n-2) + ... + 0 , que reordena a la suma de 0 a n-1; esto es

T (n) = (n-1) ((n-1) 1) / 2 .

Reorganizar y que se puede ver que T (n) será siempre ≤ 1/2 (N ²); por la definición, por lo tanto T (n) = O (N $ ² $) .

Answer 3

Es N al cuadrado si se ignora el System.out.println. Si se estima que el tiempo empleado por que será lineal en su salida (que bien puede no ser, por supuesto), sospecho que usted termina con O ((N ^ 2) * log N).

Lo menciono para no ser exigente, pero sólo para señalar que usted no sólo tiene que tomar los lazos evidentes en cuenta cuando se trabaja fuera complejidad -. Usted tiene que mirar a la complejidad de lo que se llama así

Answer 4

Sí, sería N al cuadrado. El número real de pasos sería la suma de 1 a N, que es 0,5 * (N - 1) ^ 2, si no me equivoco. Big O sólo tiene en cuenta la más alta exponant y no hay constantes, y por lo tanto, esto sigue siendo N al cuadrado.

Answer 5

Si tuviera N = 10, le iteraciones sería: 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1. (Esto es:. Diez iteraciones más nueve iteraciones más ocho iteraciones, etc ...).

Ahora, es necesario encontrar en la adición cuántas veces se puede obtener una N (10 en el ejemplo):

1: (10), 2: (9 + 1), 3: (8 + 2), 4: (7 + 3), 5: (6 + 4). Que es 5 veces ... y descansa 5 iteraciones.

Ahora se sabe que tiene cinco decenas + 5:

10 (5) + 5

En términos de f (n) (o N), podemos ver fácilmente que esto sería:

f (n) = n (n / 2) + n / 2 = (n ^ 2) / 2 + n / 2 = (n ^ 2 + n) / 2 ... esto es exactamente la complejidad de estos bucle anidado.

Sin embargo, teniendo en cuenta el comportamiento asintótico de Big O, podemos deshacernos de los valores menos significativos de f (n), que son la única n y el denominador.

Resultado: O (n ^ 2)

Answer 6

AFAIL, siendo iniciada de bucle interior a través de los exteriores es de forma adecuada para el cálculo de la complejidad de bucle anidado.