SandovalPadillaReporteActividad 2 - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

UNIVERSIDAD DE GUADALAJARA
Centro Universitario de Ciencias Exactas e Ingenierías
Algoritmia
Actividad 2: introducción a eficiencia y complejidad 
Alumno: Sandoval Padilla Fernando Cesar
Docente: Ibarra Chávez Salomón Eduardo
Código: 215685409
Sección: D02
	
12 de Febrero de 2020
Actividad: Investiga, enlista y explica cuáles son los factores que determinan el tiempo de ejecución de un programa en la computadora.
Se denomina tiempo de ejecución (runtime en inglés) al intervalo de tiempo en el que un programa de computadora se ejecuta en un sistema operativo. Este tiempo se inicia con la puesta en memoria principal del programa, por lo que el sistema operativo comienza a ejecutar sus instrucciones.
Factores que determinan el tiempo de ejecución:
1.- Los datos de entrada. 
2.- Calidad del código generado por el compilador. 
3.- La naturaleza y rapidez de las instrucciones en la máquina utilizada para ejecutar el programa.
4.- Complejidad temporal del algoritmo usado en el programa.
El hecho que el tiempo de ejecución dependa de la entrada indica que el tiempo de ejecución de un programa debe estar definido como una función de los datos de entrada, que puede especificarse con el “tamaño” de la entrada. Así, por ejemplo, en un programa de ordenamiento el tamaño natural de medida para la entrada es el número de elementos a ordenar. Es usual indicar con T(n) el tiempo de ejecución de un programa para una entrada de tamaño n. Las unidades de T(n) pueden dejarse sin especificar, pero puede pensarse que es el número de instrucciones ejecutadas en un ordenador ideal. Los factores 2 y 3 implican que T(n) no puede expresarse en unidades estándar de tiempo real tal como segundos. En su lugar, se hará referencia a que “un algoritmo es proporcional a n 2”, por ejemplo. La constante de proporcionalidad se deja sin especificar.
Notación Ο-grande y Ω-grande 
Para hacer referencia a la tasa de crecimiento de funciones usa una notación especial. Decimos que T(n) es Ο(f(n)) si hay constantes c y n0 tales que T(n) ≤ c f(n) para todo n ≥ n0. Un programa cuyo tiempo de ejecución es Ο(f(n)) se dice que tiene una tasa de crecimiento de f(n). En esta notación f(n) es una cota superior de la tasa de crecimiento de T(n). 
Ejemplo: La función T(n) = 3 n3 + 2 n2 es Ο(n 3 ), ya que para n0=0 y c=5 se obtiene: 3 n 3 + 2 n 2 ≤ 5 n 3 para todo n ≥ 0. 
Para especificar una cota inferior en la tasa de crecimiento de T(n) se usa la notación Ω(g(n)). En este caso, T(n) es Ω(g(n)) si existe una constante c (positiva) tal que T(n) ≥ c g(n). 
Ejemplo: La función T(n) = n 3 + 2 n 2 es Ω( n 3), ya que para c=1 se obtiene: n 3 + 2 n 2 ≥ n 3 para todo n ≥ 0. 
Para comparar programas pueden usarse sus funciones de crecimiento despreciando las constantes de proporcionalidad. Por tanto, un programa Ο(n 2 ) es mejor que uno con complejidad Ο(n 3 ).
Complejidad de los algoritmos de ordenación 
Haciendo un análisis comparativo de los diferentes métodos de ordenación encontramos que: 
En un cajón hay 22 guantes: 5 pares de guantes son rojos, 4 pares son amarillos y 2 pares son verdes. Puedes tomar los guantes de uno en uno en la oscuridad y solo puedes saber el color una vez que estén fuera de la caja. ¿Cuál es la menor cantidad de guantes que debes elegir para tener al menos un par del mismo color en el mejor caso? Y ¿En el peor caso?
Mejor caso:
Al parecer puede que el mejor de los casos sea en el que los 2 primeros guantes que saquemos de la caja sean pares y del mismo color
Peor caso:
El peor caso es en el que un guante de cada color estuviera fuera de la caja y no se formara un par completo o del mismo color, algo así como sacar todos los pares izquierdos o todos los pares derechos, llegando al final; es decir, al guante número 12 completando así el primer par.
Considere el siguiente algoritmo:
Entradas: M y N = Matrices cuadradas de tamaño n x n 
¿Cuál es la salida? 
La salida es otra matriz del mismo tamaño pues eso genera una multiplicación de dos matrices con el mismo numero de filas y columnas, o mejor dicho matrices cuadradas.
1 Desde i=0 hasta i=n
2 Desde j=0 hasta j=n
3 R(i, j)=M( i, j)+N(i, j)
4 Fin Desde
5 Fin Desde
a) Mencione qué hace el algoritmo.
Este algoritmo hace una suma de dos matrices del mismo tamaño y para poderlas sumar utiliza dos iteradores que suman componente o numero por numero en la matriz, en el cual uno se encarga de las filas y otro de las columnas para finalmente asignar el resultado y formar una matriz del mismo tamaño, según la tabla investigada tiene una complejidad de O(n²).
b) Calcule cuántas veces se ejecutará la instrucción 3
Depende del número a elegir pues se trata de una matriz cuadrada; es decir una matriz de n*n en donde n puede ser cualquier número, por ejemplo 4*4 en el que se va ejecutar 16 veces.
Considere el siguiente algoritmo:
Entradas: lista: arreglo de valores enteros
Salida: ¿?
1 para i=1 hasta n-1
2 mínimo = i;
3 para j=i+1 hasta n
4 si lista[j] < lista[mínimo] entonces
5 mínimo = j
6 fin si
7 fin para
8 intercambiar(lista[i], lista[mínimo])
9 fin para
a) Mencione qué hace el algoritmo
Es un algoritmo de ordenamiento que se encarga precisamente de ordenar una lista con valores enteros de menor a mayor empezando desde el valor más pequeño.
b) Calcule cuántas veces se ejecutará la instrucción 5
Mejor caso:
Si la lista ya está ordenada de menor a mayor la instrucción no se va ejecutar y no va entrar en el if.
Peor caso:
La instrucción se ejecutara (n-1)*2, lo cual es n²-n veces.
c) ¿Cuál es la instrucción que ejecuta el mayor número de veces?
La instrucción que más se ejecuta es la número 3 donde se encuentra la declaración del segundo for, se ejecutará una vez más que la instrucción 4 ya que debe validar que la condición ya no se cumpla para no entrar al bucle nuevamente.
La número 3 ( 3 para j=i+1 hasta n ) esta instrucción se ejecutara una vez más que la instrucción 4 pues es la que valida la última condición (la que no se cumple y sale del bucle).
Referencias:
https://personales.unican.es/corcuerp/progcomp/slides/Tiempo_ejec_prog.pdf
https://es.wikipedia.org/wiki/Tiempo_de_ejecuci%C3%B3n