Considere los algoritmos presentados a continuación:

a) Describa que operación están realizando cada uno de estos algoritmos.

b) Encontrar el orden de complejidad para cada uno de ellos.

c) Realice una conclusión del análisis de estos algoritmos.

a. Los tres algoritmos realizan las tablas de multiplicar, desde el 1 hasta el 10, al mismo

tiempo que visualiza el resultado en pantalla. (1 * 1 = 1, 1 * 2 = 2…).

b. Orden de complejidad:

Algoritmo 1.

For ¿For ¿r=i∗ j ;2OE

printf (“%d∗%d=%d”i , j ,r );3OE

}

system (“PAUSE” ) ;1OE

}

Primer for :2OE

for interno :

1 ° :7OE

2 ° :{ 2OE+1OE¿2OE+3OE

=O (n )=8n+10 ;O (n )=90OE

3 ° :2OE+1OE

Primer for :1OEPrimer for :1OE+2OE

O (n2 )= (8n+10 ) (n )+6

O (n2 )=8n2+10n+6 ;O (n2 )=906OE

R :Complejidad cuadratica [O (n2 )]

Algoritmo 2: Sin contar la primera asignación (i=1)

i=1

while (i≤10 ) { 2OE

j=1 1OE

while ( j≤10 ){ 2OE

r=i∗ j ;2OE

printf (“%d∗%d=%d”i , j ,r );3OE

j++;}2OE

i++;2OE

system(PAUSE);}1OE

Primer while :2OE+1OE

while interno :

1 ° :9OE

+2OEalromper el ciclo=¿O (n )=9n+2;O (n )=92OE

Primer while :2OE+1OE+2OE (al romper el ciclo)

O (n2 )= (9n+2 ) (n )+8

O (n2 )=9n2+2n+8 ;O (n2 )=928OE

R :Complejidad cuadratica [O (n2 )]

Algoritmo 3: Sin contar la primera asignación (i=1)

i=1

do { 1OE

j=1; 1OE

do { 1OE

r=i∗ j ; 2OE

printf (“%d∗%d=%d”i , j ,r ); 3OE

j++; 2OE

}while ( j≤10 ) ; 2OE

i++; 2OE

system(PAUSE); 1OE

}while (i ≤10 ); 2OE

Primer do−while :1OE+1OE do−while interno :

1 ° :8OE

+2OEalromper el ciclo=¿O (n )=8n+2;O (n )=82OE

Primer while :2OE+1OE+2OE (al ropmper el ciclo)

O (n2 )= (8n+2 ) (n )+8

O (n2 )=8n2+2n+8 ;O (n2 )=828OE

R :Complejidad cuadratica [O (n2 )]

Conclusión

De los algoritmos analizados podemos observar que para la tarea seleccionada (tablas de

multiplicar), con un tamaño de datos de entrada (10), el tercer algoritmo que usa la

estructura de control (Do – While) resulta ser más conveniente puesto que realiza menos

operaciones elementales para lograr su objetivo.

Además, al modificar el tamaño de los datos de entrada sigue siendo el que menos

operaciones elementales realiza, es decir, en este caso es el más eficiente.