¿Cuál es el Big-O tiempo de complejidad de los siguientes bucles anidados:¿Cuál es el Big-O de un bucle anidado, donde el número de iteraciones en el bucle interno está determinado por la iteración actual del bucle externo?
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?
Sí, sigue siendo O (n^2), tiene un factor constante más pequeño, pero eso no afecta la notación O.
Sí, sería N al cuadrado. El número real de pasos sería la suma de 1 a N, que es .5 * (N - 1)^2, si no me equivoco. Big O solo tiene en cuenta el exponente más alto y ninguna constante, y por lo tanto, sigue siendo N al cuadrado.
Se aleja un poco - la suma de 1 a n es n * (n + 1)/2, o .5 * n^2 + .5 * n, que es claramente O (n^2). – user57368
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 se reordena a la suma de 0 a n-1; esto es
T (n) = (n-1) ((n-1) +1)/2.
Reorganiza eso y puedes ver que T (n) siempre será ≤ 1/2 (n ²); por la definición, por lo tanto T (n) = O (n ²).
Es N al cuadrado si ignora System.out.println. Si supone que el tiempo empleado en esto será lineal en su producción (que bien puede no ser, por supuesto), sospecho que terminará con O ((N^2) * log N).
Menciono esto 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 - es necesario mirar a la complejidad de lo que se llama así.
Lo dice implícitamente, pero debe señalarse explícitamente que la complejidad depende de lo que usted considera "unidad de trabajo". Si println es una unidad de trabajo, entonces es O (n^2), si la instrucción de la máquina es una unidad de trabajo, entonces es como usted dice. –
Es bastante extraño que la unidad de trabajo dependa de n, o al menos, lo hace menos útil en el mundo real, IMO. –
¿Puede decirme qué es el T (n)? – CodyBugstein
Si tuvieras N = 10, tus iteraciones serían: 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 esta sería la siguiente:
f (n) = n (n/2) + n/2 = (n^2)/2 + n/2 = (n^2 + n)/2 ... esta es exactamente la complejidad de estos bucle anidado.
Pero, considerando el comportamiento asintótico de Big O, podemos deshacernos de los valores menos significativos de f (n), que son el n único y el denominador.
Resultado: O (n^2)
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. 
Consulte también [Complemento de tiempo del ciclo anidado] (http://stackoverflow.com/q/526728/456814). –