Complejidad de tiempo

Question

Esta pregunta se hace para fines de revisión de un pasado hoja de examen Yo sólo quiero saber si estoy en el camino correcto

1. int i=1; 
2. while (i <= n) { 
3. for (int j=1; j<10; j++) 
4.  sum++; 
5. i++; 
6. } 
7. for(int j = 1; j <= n; j++) 
8. for(int k = 1; k <= n; k=k*2) 
9.  sum++; 

1.) ¿Cuántas veces se ejecuta comunicado 4?
A. O (n)
B. O (n^2)
C. O (log n)
D. O (n log n)
E. ninguno de los anteriormente

Aquí eligió A

2.) ¿Cuántas veces se ejecuta la instrucción 9?
A. O (n)
B. O (n^2)
C. O (log n)
D. O (n log n)
E. Ninguno de los anteriores

Debido línea 8 (k = k * 2) Elegí C

3.) ¿Cuál es el tiempo de ejecución de todo el fragmento de código?
A. O (n)
B. O (n^2)
C. O (log n)
D. O (n log n)

Desde O (n) + O (log n) = O (n) así que elegí A

Answer 1

Su respuesta 1 es correcta, está dentro de un bucle controlado solo por n.

La respuesta 2 es incorrecta. Es sería ser O(log n) si la línea 7 no existía pero, como la línea 7 está forzando a las líneas 8 y 9 a ejecutarse varias veces dependiendo de n, la respuesta es O(n log n).

La respuesta 3 es la correcta razonamiento pero adolece del hecho de que la respuesta 2 era incorrecta. O(n) + O(n log n) se simplifica hasta O(n log n).

Entonces las respuestas son A, D y D.

Answer 2

No sé cómo formularon las preguntas, pero si la redacción es como usted dice, su examinador no conocía la definición correcta de O grande (al menos cuando espera las respuestas "correctas") - como "Funciones de Big O" incluir más pequeño ". Entonces, algo que se ejecuta como una función de n en f (n) = 10 n que es lineal también está en O (n), O (n^2), O (n log n). Si uno se pregunta por el "más pequeño" posible, sus respuestas serían

1. Declaración 4 se ejecuta 10 n veces, los tiempos de modo que A
2. Declaración 9 se ejecuta n * log n, por lo que D
3. Aquí se ejecuta la suma de ambos, n + n * log n por lo que (aquí perdió un * n), entonces D sería el derecho.

Así que si múltiples respuestas eran posibles y que sólo se ha solicitado a la cantidad que se ejecuta, las respuestas correctas serían

1. A, B, D
2. B, D
3. B , D

Answer 3

Ans 1: A ie. O (n) ya que la instrucción 4 se ejecutaría 10 * n veces.

Ans 2: D ie. O (nlog (n)) ya que la instrucción 9 se ejecutará n * log (n) veces.

Resp 3: D como la complejidad general [O (n) + O (nlog (n))] sería n * log (n).