Preguntas de práctica sobre el análisis de la complejidad del tiempo

Prerrequisito: Análisis de Algoritmos
1. ¿Cuál es la complejidad de tiempo y espacio del siguiente código: 
 

int a = 0, b = 0;
for (i = 0; i < N; i++) {
    a = a + rand();
}
for (j = 0; j < M; j++) {
    b = b + rand();
}

a = 0
b = 0
for i in range(N):
  a = a + random()
 
for i in range(M):
  b= b + random()

Opciones: 
 

1. O(N * M) tiempo, O(1) espacio
2. O(N + M) tiempo, O(N + M) espacio
3. O(N + M) tiempo, O(1) espacio
4. O(N * M) tiempo, O(N + M) espacio

Producción: 

3. O(N + M) time, O(1) space

Explicación: El primer bucle es O(N) y el segundo bucle es O(M). Dado que N y M son variables independientes , no podemos decir cuál es el término principal. Por lo tanto , la complejidad temporal del problema dado será O(N+M).
Dado que el tamaño de las variables no depende del tamaño de la entrada,   la Complejidad del Espacio será constante o O(1)
2. ¿Cuál es la complejidad del tiempo del siguiente código: 
 

int a = 0;
for (i = 0; i < N; i++) {
    for (j = N; j > i; j--) {
        a = a + i + j;
    }
}

a = 0;
for i in range(N):
  for j in reversed(range(i,N)):
    a = a + i + j;

Opciones: 
 

1. EN)
2. O(N*log(N))
3. O(N * Raíz cuadrada(N))
4. O(N*N)

Producción: 

4. O(N*N)

Explicación: 
El código anterior ejecuta el número total de veces 
= N + (N – 1) + (N – 2) + … 1 + 0 
= N * (N + 1) / 2 
= 1/2 * N^2 + 1/ 2 * 
NO(N^2) veces.
3. ¿Cuál es la complejidad temporal del siguiente código: 
 

int i, j, k = 0;
for (i = n / 2; i <= n; i++) {
    for (j = 2; j <= n; j = j * 2) {
        k = k + n / 2;
    }
}

k = 0;
for i in range(n//2,n):
  for j in range(2,n,pow(2,j)):
        k = k + n / 2;

Opciones: 
 

1. En)
2. O(N registro N)
3. O(n^2)
4. O(n^2Iniciar sesión)

Producción: 

2. O(nLogn)

Explicación: Si te fijas, j sigue duplicándose hasta que es menor o igual que n. Varias veces, podemos duplicar un número hasta que sea menor que n sería log(n). 
Tomemos los ejemplos aquí. 
para n = 16, j = 2, 4, 8, 16 
para n = 32, j = 2, 4, 8, 16, 32 
Entonces, j correría por O(log n) pasos. 
corro por n/2 pasos. 
Entonces, pasos totales = O(n/ 2 * log (n)) = O(n*logn)
4. ¿Qué significa cuando decimos que un algoritmo X es asintóticamente más eficiente que Y?  
Opciones: 
 

1. X siempre será una mejor opción para entradas pequeñas
2. X siempre será una mejor opción para entradas grandes
3. Y siempre será una mejor opción para entradas pequeñas
4. X siempre será una mejor opción para todas las entradas

 Producción: 

2. X will always be a better choice for large inputs

Explicación: En el análisis asintótico, consideramos el crecimiento del algoritmo en términos del tamaño de entrada. Se dice que un algoritmo X es asintóticamente mejor que Y si X toma menos tiempo que y para todos los tamaños de entrada n mayores que un valor n0 donde n0 > 0.
 

5. ¿Cuál es la complejidad temporal del siguiente código:

int a = 0, i = N;
while (i > 0) {
    a += i;
    i /= 2;
}

a = 0
i = N
while (i > 0):
  a += i
  i //= 2

Opciones: 
 

1. EN)
2. O(Sqrt(N))
3. EN 2)
4. O (registro N)

Producción: 
 

4. O(log N)

Explicación: Tenemos que encontrar la x más pequeña tal que N / 2^x N 
x = log(N)

6. ¿Cuál de los siguientes describe mejor el criterio útil para comparar la eficiencia de los algoritmos?

1. Tiempo
2. Memoria
3. Los dos anteriores
4. Ninguna de las anteriores

3. Both of the above

Explicación: la comparación de la eficiencia de un algoritmo depende del tiempo y la memoria que ocupa un algoritmo. El algoritmo que se ejecuta en menos tiempo y ocupa menos memoria, incluso para un tamaño de entrada grande, se considera un algoritmo más eficiente.

7. ¿Cómo se mide la complejidad del tiempo?

1. Contando el número de algoritmos en un algoritmo.
2. Contando el número de operaciones primitivas realizadas por el algoritmo en un tamaño de entrada dado.
3. Contando el tamaño de la entrada de datos al algoritmo.
4. Ninguna de las anteriores

2. By counting the number of primitive operations performed by the algorithm on a given input size.

8. ¿Cuál será la complejidad temporal del siguiente código?

for(var i=0;i<n;i++)
    i*=k

for(int i=0;i<n;i++){
  i*=k;
}

# code
for i in range(n):
  i=i*k

1. En)
2. OK)
3. O(log _kn )
4. O(registro _n k)

Producción:

3. O(logkn)

Explicación: Debido a que los bucles k ^n-1 veces, después de tomar log, se convierte en log _k n.

9. ¿Cuál será la complejidad temporal del siguiente código?

var value = 0;
for(var i=0;i<n;i++)
    for(var j=0;j<i;j++)
    value += 1;

int value = 0;
for(int i=0;i<n;i++)
    for(int j=0;j<i;j++)
      value += 1;

value = 0;
for i in range(n):
  for j in rnage(i):
    value=value+1

1. norte
2. (n+1)
3. n(n-1)
4. n(n+1)

Producción:

3. n(n-1)

Explicación: El primer bucle for se ejecutará (n) veces y otro bucle for se ejecutará (n-1) veces, por lo que el tiempo total será n(n-1).

10. Los algoritmos A y B tienen un tiempo de ejecución en el peor de los casos de O(n) y O(logn), respectivamente. Por lo tanto, el algoritmo B siempre se ejecuta más rápido que el algoritmo A.

1. Verdadero
2. Falso

False

Explicación: la notación Big-O proporciona una comparación asintótica en el tiempo de ejecución de los algoritmos. Para n < n ⁰ , el algoritmo A podría ejecutarse más rápido que el algoritmo B, por ejemplo.