Big O Notation Homework - ¿Análisis de 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, así

//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á lanzando fuera un poco así que no estoy muy seguro de

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

O (N^2) para el fragmento 6 como así

//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á lanzando fuera

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

O (N) para el fragmento 8

Answer 1

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 n * n problemas, debe ejecutar el cuerpo del ciclo n * n veces, por lo que sería O (n^2) , entonces compones eso con el orden del otro código. Fragmento 8 se duplica el contador en lugar de incrementarlo, por lo que cuanto mayor sea el problema, el trabajo menos adicional que tiene que hacer, por lo que es O (log (n))

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

Answer 2

Parece que está 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 muy rechazada. Ten cuidado. Here es la publicación.

Answer 3

Para el caso 8 intentar escribir el número de iteraciones para algunos valores de N y ver lo que el patrón parece ... no es O (N)

Answer 4

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

Answer 5

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++){....} 
} 

Derecho, considere el hecho de que tiene código en diferentes niveles.En este ejemplo, sólo se puede ver 3 niveles hasta ahora:

1. El exterior de bucle que va desde 0-n
2. Otra para-bucle que va de 0-100
3. Algunos código dentro, que está marcado como ...

En ningún momento debe intentar calcularlo todo en 1 tiempo. 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!