Big O Notation Homework - ¿Análisis de algoritmo de fragmento de código? [cerrado]

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 en 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á echando 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) también para el fragmento 6

//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, n * n me está echando 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 de manera similar, el fragmento 7 es O (n ^ 5) *. También se ve como O (log (n)) para el fragmento 8.

Para los problemas n * n, tienes que ejecutar el cuerpo del bucle n * n veces, por lo que sería O (n ^ 2), luego lo compones con el orden del otro código. El fragmento 8 en realidad duplica 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))

* edit: El fragmento 7 es O (n ^ 5), no O (n ^ 4) como pensé anteriormente. Esto se debe a que tanto j como k van de 1 a n * n. Lo siento, no pude captar esto antes.

Answer 2

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

Answer 3

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 4

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

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

Answer 5

Está en el camino correcto, pero aquí hay una sugerencia de 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++){....}
}

Correcto, considera el hecho de que tienes código en diferentes niveles. En este ejemplo, solo puedes ver 3 niveles hasta ahora:

1. El for-loop externo que va de 0-n
2. Otro for-loop que va de 0-100
3. Algún código interior, que está marcado como ...

En ningún momento debe intentar calcularlo todo de una vez. 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.

¡Buena suerte!