resueltos - notacion big o en java

Tarea de notación Big O-¿Algoritmo de Fragmentos de Código?

Question

Para la tarea, me dieron los siguientes 8 fragmentos de código para analizar y dar una notación Big-Oh para el tiempo de ejecución. ¿Alguien puede decirme si estoy en el camino correcto?

//Fragment 1
for(int i = 0; i < n; i++)
    sum++;

Estoy pensando O (N) para el fragmento 1

//Fragment 2
for(int i = 0; i < n; i+=2)
    sum++;

O (N) para el fragmento 2 también

//Fragment 3
for(int i = 0; i < n; i++)
    for( int j = 0; j < n; j++)
        sum++;

O (N ^ 2) para el fragmento 3

//Fragment 4
for(int i = 0; i < n; i+=2)
    sum++;
for(int j = 0; j < n; j++)
    sum++;

O (N) para el fragmento 4

//Fragment 5
for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        sum++;

O (N ^ 2) para el fragmento 5 pero el n * n me está tirando un poco, así que no estoy muy seguro

//Fragment 6
for(int i = 0; i < n; i++)
    for( int j = 0; j < i; j++)
        sum++;

O (N ^ 2) para el fragmento 6 también

//Fragment 7
for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        for(int k = 0; k < j; k++)
            sum++;

O (N ^ 3) para el fragmento 7 pero una vez más el n * n me está tirando

//Fragment 8
for(int i = 1; i < n; i = i * 2)
    sum++;

O (N) para el fragmento 8

Answer 1

Para el caso 8 intente escribir el número de iteraciones para algunos valores de N y vea cómo se ve el patrón ... no es O (N)

Answer 2

Creo que el fragmento 5 es O (n ^ 3), y el fragmento 7 es O (n ^ 5) *. También se ve como O (log (n)) para el fragmento 8.

Para los problemas n * n, tiene que ejecutar el cuerpo del bucle n * n veces, por lo que sería O (n ^ 2), y luego lo compondrá con el orden del otro código. El fragmento 8 en realidad dobla el contador en lugar de incrementarlo, por lo que cuanto mayor sea el problema, menos trabajo adicional tendrá que hacer, por lo que es O (log (n))

* editar: el fragmento 7 es O (n ^ 5), no O (n ^ 4) como pensaba anteriormente. Esto se debe a que j y k van de 1 a n * n. Perdón, no entendí esto antes.

Answer 3

El fragmento 7 es O (n ^ 5), no O (n ^ 4) como afirma el comentario actualmente aceptado. De lo contrario, es correcto.

Answer 4

Estás en el camino correcto, pero aquí hay un consejo sobre cómo las cosas podrían aclararse en el camino. Supongamos que tiene algún código:

for(i = 0; i < n; i++) {
   for(j = 0; j < 100; j++){....}
}

Bien, considere el hecho de que tiene código en diferentes niveles. En este ejemplo, solo puedes ver 3 niveles hasta ahora:

1. El for-loop externo que va desde 0-n
2. Otro for-loop que va de 0 a 100
3. Un código dentro, que está marcado como ...

En ningún momento debería intentar calcularlo todo en 1 intento. Aquí es donde la mayoría de los principiantes cometen algún tipo de error aritmético. Calcúlelo individualmente para cada nivel y luego multiplíquelo todo junto.

¡Buena suerte!

Answer 5

Usted parece estar en el camino correcto. Con respecto al N * N, ¿qué efecto crees que tendría? Es otro factor de N, por lo que probablemente sea un orden superior.

Solo una advertencia, vi otra publicación como esta y fue extremadamente rechazada. Ten cuidado. Aquí está la publicación.