resueltos - notacion big o en java
Tarea de notación Big O-¿Algoritmo de Fragmentos de Código? (5)
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)
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
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.
El fragmento 7 es O (n ^ 5), no O (n ^ 4) como afirma el comentario actualmente aceptado. De lo contrario, es correcto.
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:
- El for-loop externo que va desde 0-n
- Otro for-loop que va de 0 a 100
- 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!
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.