Home Algoritmos y Estructuras de Datos (VJ1215)

Curso 2023/2024

Ejercicio sobre costes temporales de bucles

En cada uno de los siguientes 25 apartados, analiza el coste temporal del fragmento de código que se proporciona en función de N, y elige una solución correcta entre las seis siguientes (no hace falta que lo demuestres):

  1. O(N)

    O(<var>N</var>)

  2. O(N2)

    O(<var>N</var><sup>2</sup>)

  3. O(N3)

    O(<var>N</var><sup>3</sup>)

  4. O(log N)

    O(log <var>N</var>)

  5. O(N log N)

    O(<var>N</var> log <var>N</var>)

  6. O(log2 N)

O(log<sup>2</sup> <var>N</var>)

Las gráficas anteriores se han obtenido con Gnuplot online modificando su Plot script. Por ejemplo: 

# Scale font and line width (dpi) by changing the size! It will always display stretched.
set terminal svg size 400,300 enhanced fname 'arial'  fsize 10 butt solid
set output 'out.svg'

# Key means label...
set key inside bottom right
set xlabel 'n'
set ylabel 'Tiempo'
plot [0:100] x * log(x) title 'O(n log n)'

Si quieres ver dos o más gráficas juntas, puedes hacer algo así: 

plot [0:100] x title 'n', log(x) * log(x) title 'log² n', log(x) title 'log n'

Apartado 1 

int pasos = 0;
for (int i = 0; i < N; i = i + 1)
   pasos++;

Solución

O(N)

Apartado 2 

int pasos = 0;
for (int i = 0; i < N; i = i + 2)
   pasos++;

Solución

O(N)

Apartado 3 

int pasos = 0;
for (int i = 1; i <= N; i = i * 2)
   pasos++;

Solución

O(log N)

Apartado 4 

int pasos = 0;
for (int i = N; i > 0; i = i - 1)
   pasos++;

Solución

O(N)

Apartado 5 

int pasos = 0;
for (int i = N; i > 0; i = i - 2)
   pasos++;

Solución

O(N)

Apartado 6 

int pasos = 0;
for (int i = N; i > 0; i = i / 2)
   pasos++;

Solución

O(log N)

Apartado 7 

int pasos = 0;
for (int i = 0; i < N * N; i = i + 1)
   pasos++;

Solución

O(N2)

Apartado 8 

int pasos = 0;
for (int i = 0; i < N * N; i = i + N)
   pasos++;

Solución

O(N)

Apartado 9 

int pasos = 0;
for (int i = 1; i <= N * N; i = i * 2)
   pasos++;

Solución

O(log N2) = O(2 log N) = O(log N), aplicando esa propiedad matemática de los logaritmos.

Apartado 10 

int pasos = 0;
for (int i = 1; i <= N * N * N; i = i * 2)
   pasos++;

Solución

O(log N3) = O(3 log N) = O(log N), aplicando esa propiedad matemática de los logaritmos.

Apartado 11 

int pasos = 0;
for (int i = 0; i < N; i = i + 1)
   pasos++;
for (int j = 0; j < N; j = j + 1)
   pasos++;
for (int k = 0; k < N; k = k + 1)
   pasos++;

Solución

O(N)

Apartado 12 

int pasos = 0;
for (int i = 1; i <= N;     i = i + 1)
   pasos++;
for (int j = 1; j <= N * N; j = j + 1)
   pasos++;
for (int k = 1; k <= N;     k = k * 2)
   pasos++;

Solución

O(N2)

Apartado 13 

int pasos = 0;
for (int i = 0; i < N; i = i + 1)
   for (int j = 0; j < N; j = j + 1)
      pasos++;

Solución

O(N2)

Apartado 14 

int pasos = 0;
for (int i = 0; i < N; i = i + 1)
   for (int j = i; j < N; j = j + 1)
      pasos++;

Solución

O(N2)

Apartado 15 

int pasos = 0;
for (int i = 0; i < N; i = i + 1)
   for (int j = 1; j <= N; j = j * 2)
      pasos++;

Solución

O(N log N)

Apartado 16 

int pasos = 0;
for (int i = 1; i <= N; i = i * 2)
   for (int j = 1; j <= N; j = j * 2)
      pasos++;

Solución

O(log2 N)

Apartado 17 

int pasos = 0;
for (int i = 0; i < N; i = i + 1)
   for (int j = 0; j < N * N; j = j + 1)
      pasos++;

Solución

O(N3)

Apartado 18 

int pasos = 0;
for (int i = 0; i < N; i = i + 1)
   for (int j = 1; j <= N; j = j * 2)
      pasos++;
for (int k = 0; k < N * N; k = k + 1)
   pasos++;

Solución

O(N2)

Apartado 19 

int pasos = 0;
for (int i = 0; i < N; i = i + 1)
   for (int j = 0; j < N; j = j + 1)
      for (int k = 0; k < N; k = k + 1)
         pasos++;

Solución

O(N3)

Apartado 20 

int pasos = 0;
for (int i = 0; i < N; i = i + 1)
   for (int j = i; j < N; j = j + 1)
      for (int k = j; k < N; k = k + 1)
         pasos++;

Solución

O(N3)

Apartado 21 

int pasos = 0;
for (int i = 0; i < N; i = i + 1)
   for (int j = 0; j < 10; j = j + 1)
      for (int k = 0; k < 10; k = k + 1)
         pasos++;

Solución

O(N)

Apartado 22 

int pasos = 0;
for (int i = 0; i < N; i = i + 1)
   for (int j = 0; j < 10; j = j + 1)
      for (int k = j; k < 10; k = k + 1)
         pasos++;

Solución

O(N)

Apartado 23 

int pasos = 0;
for (int i = 1; i < N * N * N; i = i * 2)
   for (int j = 0; j < 1000; j = j + 1)
      for (int k = 0; k < 1000; k = k + 1)
         pasos++;

Solución

O(log N)

Apartado 24 

int pasos = 0;
for (int i = 1; i < N * N * N; i = i * 2)
   for (int j = 0; j < 1000; j = j + 1)
      for (int k = 0; k < 1000; k = k + 1)
         for (int m = 0; m < 1000; m = m + 1)
            pasos++;

Solución

O(log N)

Apartado 25 

int pasos = 0;

for (int i = 0; i < N; i = i + 1)
   pasos++;

for (int j = 1; j <= N * N * N; j = j * 2)
   pasos++;

for (int k = 0; k < N; k = k + 1)
   for (int m = 0; m < N; m = m + 1)
      pasos++;

Solución

O(N2)