Cuestionario para empleados
Páginas: 5 (1030 palabras)
Publicado: 24 de abril de 2010
Complejidad temporal: hacia una aproximación teórica
Hemos visto, de momento, como efectuar experimentos para medir el tiempo. ¿Podemos prescindir de estos experimentos y seguir obteniendo resultados que nos permitan comparar dos (o más) programas o, mejor, dos (o más) algoritmos? Es decir, ¿es posible ((calcular)) o ((estimar)) el tiempo de ejecución a partir del código fuente, sin necesidadde implementar y ejecutar los programas?
Dependencia del tiempo con el coste de las operaciones elementales
Vamos a estudiar esta posibilidad considerando tres formas diferentes de solucionar un mismo problema en C: el cálculo del cuadrado del número 10 (aunque, ciertamente, no parece necesario programar un computador para ello). El primer programa sigue una aproximación directa y usa laoperación
Producto para resolver el problema:
[pic]
El segundo programa suma 10 veces el valor 10:
[pic]
Y el tercero repite 10 veces 10 incrementos unitarios de un contador:
[pic]
¿Cuál de los tres programas se ejecutara mas rápidamente? A simple vista diríamos que el primero, pues ocupa menos líneas y resuelve ((directamente)) el problema. Pero hemos de pensar un poco larespuesta: eso será cierto si cuesta menos tiempo efectuar una multiplicación que 10 sumas o 100
Incrementos. Normalmente, el producto es una operación más lenta que la suma, y ´esta es más costosa que el incremento. Supón que en nuestro ordenador cada operación básica tarda lo que se indica en esta tabla (1 μs es una millonésima de segundo).
[pic]
(No tendremos en cuenta el tiempo de impresión deresultados en aras de simplificar la exposición.) Cada programa efectúa un número diferente de productos, sumas e incrementos:
[pic]
Quizá necesitemos justificar algunos de estos valores. El número de incrementos en sumas.c, por ejemplo, es de 10 por que el bucle for hace que i pase de 0 a 10 con el operador de post incremento. Las 12 asignaciones del mismo programa corresponde a lassentencias ((m = 0)) y ((m = m + 10)) (esta última se ejecuta 10 veces) y a la inicialización del bucle for. El número de comparaciones es de 11 porque el bucle for efectúa una comparación para cada valor de i entre 0 y 10. Nos precipitamos al juzgar como mejor a uno de ellos. Los tres son igual de rápidos.
Nos precipitamos al juzgar como mejor a uno de ellos. Los tres son igual de rápidos.
Notenemos en cuenta el coste de printf o return porque solo estamos interesados en estudiar el coste temporal del Método de cálculo del producto de 10 por 10.
[pic]
Bien. ¿Y si el coste de cada operación fuera diferente? Por ejemplo, el que se indica en esta tabla:
[pic]
¿Qué programa sería más rápido en este otro escenario? En ese caso, producto.c sería el más rápido e incremento el máslento.
[pic]
¿Y si sumar fuese más rápido? Pongamos por caso que los tiempos de ejecución de cada operación fueran éstos:
[pic]
Entonces resultaría ((vencedor)) el programa que calcula 102 sumando (tardaría 83 μs):
[pic]
No es tan fácil, pues, decidir que programa es mas rapido, al menos no si queremos tener en cuenta el coste de cada instruccion ya que ´este depende del ordenador.Los programas estudiados presentan una aplicación muy pobre: se limitan a resolver el problema del cálculo de 10 al cuadrado. Generalicémoslos para resolver el problema de calcular n2, siendo n un entero cualquiera:
[pic]
[pic]
[pic]
[pic]
El cálculo de 102 es un caso particular del cálculo de n2. Decimos que el caso n = 10 es una instancia del problema de calcular n2. Enprincipio, cuanto mayor es el valor de n, más costoso es resolver el problema. Por ejemplo, la instancia n = 100 es mas difícil de resolver que la instancia n = 10. En este caso decimos, además, que n es el tamaño o talla del problema.
Podemos expresar el tiempo de ejecución de los tres programas como una función del valor de n, es decir, de la talla. Anotaremos al margen el número de operaciones...
Hemos visto, de momento, como efectuar experimentos para medir el tiempo. ¿Podemos prescindir de estos experimentos y seguir obteniendo resultados que nos permitan comparar dos (o más) programas o, mejor, dos (o más) algoritmos? Es decir, ¿es posible ((calcular)) o ((estimar)) el tiempo de ejecución a partir del código fuente, sin necesidadde implementar y ejecutar los programas?
Dependencia del tiempo con el coste de las operaciones elementales
Vamos a estudiar esta posibilidad considerando tres formas diferentes de solucionar un mismo problema en C: el cálculo del cuadrado del número 10 (aunque, ciertamente, no parece necesario programar un computador para ello). El primer programa sigue una aproximación directa y usa laoperación
Producto para resolver el problema:
[pic]
El segundo programa suma 10 veces el valor 10:
[pic]
Y el tercero repite 10 veces 10 incrementos unitarios de un contador:
[pic]
¿Cuál de los tres programas se ejecutara mas rápidamente? A simple vista diríamos que el primero, pues ocupa menos líneas y resuelve ((directamente)) el problema. Pero hemos de pensar un poco larespuesta: eso será cierto si cuesta menos tiempo efectuar una multiplicación que 10 sumas o 100
Incrementos. Normalmente, el producto es una operación más lenta que la suma, y ´esta es más costosa que el incremento. Supón que en nuestro ordenador cada operación básica tarda lo que se indica en esta tabla (1 μs es una millonésima de segundo).
[pic]
(No tendremos en cuenta el tiempo de impresión deresultados en aras de simplificar la exposición.) Cada programa efectúa un número diferente de productos, sumas e incrementos:
[pic]
Quizá necesitemos justificar algunos de estos valores. El número de incrementos en sumas.c, por ejemplo, es de 10 por que el bucle for hace que i pase de 0 a 10 con el operador de post incremento. Las 12 asignaciones del mismo programa corresponde a lassentencias ((m = 0)) y ((m = m + 10)) (esta última se ejecuta 10 veces) y a la inicialización del bucle for. El número de comparaciones es de 11 porque el bucle for efectúa una comparación para cada valor de i entre 0 y 10. Nos precipitamos al juzgar como mejor a uno de ellos. Los tres son igual de rápidos.
Nos precipitamos al juzgar como mejor a uno de ellos. Los tres son igual de rápidos.
Notenemos en cuenta el coste de printf o return porque solo estamos interesados en estudiar el coste temporal del Método de cálculo del producto de 10 por 10.
[pic]
Bien. ¿Y si el coste de cada operación fuera diferente? Por ejemplo, el que se indica en esta tabla:
[pic]
¿Qué programa sería más rápido en este otro escenario? En ese caso, producto.c sería el más rápido e incremento el máslento.
[pic]
¿Y si sumar fuese más rápido? Pongamos por caso que los tiempos de ejecución de cada operación fueran éstos:
[pic]
Entonces resultaría ((vencedor)) el programa que calcula 102 sumando (tardaría 83 μs):
[pic]
No es tan fácil, pues, decidir que programa es mas rapido, al menos no si queremos tener en cuenta el coste de cada instruccion ya que ´este depende del ordenador.Los programas estudiados presentan una aplicación muy pobre: se limitan a resolver el problema del cálculo de 10 al cuadrado. Generalicémoslos para resolver el problema de calcular n2, siendo n un entero cualquiera:
[pic]
[pic]
[pic]
[pic]
El cálculo de 102 es un caso particular del cálculo de n2. Decimos que el caso n = 10 es una instancia del problema de calcular n2. Enprincipio, cuanto mayor es el valor de n, más costoso es resolver el problema. Por ejemplo, la instancia n = 100 es mas difícil de resolver que la instancia n = 10. En este caso decimos, además, que n es el tamaño o talla del problema.
Podemos expresar el tiempo de ejecución de los tres programas como una función del valor de n, es decir, de la talla. Anotaremos al margen el número de operaciones...
Leer documento completo
Regístrate para leer el documento completo.