Complejidad de un doble para el bucle

Question

Estoy tratando de averiguar la complejidad de un bucle for utilizando la notación Big O. He hecho esto antes en mis otras clases, pero este es más riguroso que los otros porque está basado en el algoritmo real. El código es el siguiente:

for(cnt = 0, i=1; i<=n; i++) //for any size n 
{ 
    for(j = 1; j <= i; j++) 
    { 
     cnt++; 
    } 
} 

Y

for(cnt = 0, i=1; i<=n; i*=2) //for any size n 
{ 
    for(j = 1; j <= i; j++) 
    { 
     cnt++; 
    } 
} 

me han llegado que el primer bucle es de O (n) la complejidad, ya que va a través de la lista de n veces. En cuanto al segundo ciclo, estoy un poco perdido. Creo que está pasando por el ciclo i veces por cada n que se prueba. He asumido (incorrectamente) que esto significa que el ciclo es O (n * i) cada vez que se evalúa. ¿Hay algo que me falta en mi suposición? Sé que cnt ++ es un tiempo constante.

Gracias por la ayuda en el análisis. Cada bucle está en su propio espacio, no están juntos.

Answer 1

El bucle externo del primer ejemplo ejecuta n veces. Para cada iteración del bucle externo, el bucle interno se ejecuta i veces, por lo que la complejidad general se puede calcular de la siguiente manera: uno para la primera iteración más dos para la segunda iteración más tres para la tercera iteración y más, n para el n -ésimo iteración.

1+2+3+4+5+...+n = (n*(n-1))/2 --> O(n^2) 

El segundo ejemplo es más complicado: desde i duplica cada iteración, el bucle exterior ejecuta sólo Log2(n) veces. Suponiendo que n es una potencia de 2, el total para el bucle interior es

1+2+4+8+16+...+n 

que es 2^Log2(n)-1 = n-1 para la complejidad O(n).

Para n s que no son potencias de dos el número exacto de iteraciones es (2^(Log2(n)+1))-1, que todavía O(n) es:

1  -> 1 
2..3 -> 3 
4..7 -> 7 
8..15 -> 15 
16..31 -> 31 
32..63 -> 63 

y así sucesivamente.

Answer 2

Esperemos que esta no es la tarea, pero veo que al menos hace un intento aquí, así que aquí está mi opinión sobre esto:

cnt se incrementa n * (n + 1)/2 veces, lo cual hace que el conjunto completo de ambos bucles O (n^2). El segundo ciclo es O (n/2) en promedio, que es O (n).

Answer 3

El primer ejemplo es O (N^2) y What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop? sería la pregunta que responde que donde la clave es notar que el número de rondas del ciclo interno depende de n.

El segundo ejemplo es probable O (n log n) ya que el bucle externo se está incrementando en una escala diferente a la lineal. Mire la búsqueda binaria para ver un ejemplo de un caso de complejidad logarítmica. En el segundo ejemplo, el bucle externo es O (log n) y el bucle interno es O (n) que se combina para dar una complejidad O (n log n).