Estructura De Datos
Páginas: 11 (2531 palabras)
Publicado: 5 de junio de 2012
5/12/2011
|CHRISTIAN RENE AVIÑA MEDINA |
|LUIS ANGEL ALCALA GALLARDO |
|EDUARDO IVAN SANCHEZ DE LA CRUZ|
|IVAN SORIA ALVARADO |
Análisis de Algoritmos
Tiempo de Ejecución
Una medida que suele ser útil conocer es el tiempo de ejecución de un programa en función de N, lo que denominaremos T(N). Esta función se puede medir físicamente (ejecutando elprograma, reloj en mano), o calcularse sobre el código contando instrucciones a ejecutar y multiplicando por el tiempo requerido por cada instrucción. Así, un trozo sencillo de programa como
S1; for (int i= 0; i < N; i++) S2;
Requiere
T(N)= t1 + t2*N
Siendo t1 el tiempo que lleve ejecutar la serie "S1" de sentencias, y t2 el que lleve la serie "S2".
Prácticamente todos los programasreales incluyen alguna sentencia condicional, haciendo que las sentencias efectivamente ejecutadas dependan de los datos concretos que se le presenten. Esto hace que más que un valor T(N) debamos hablar de un rango de valores
Tmin(N) 100.
Si nuestro problema no va a tratar jamás problemas de tamaño mayor que 100, es mejor solución usar el algoritmo "g".
El ejemplo anterior muestraque las constantes que aparecen en las fórmulas para T(n), y que desaparecen al calcular las funciones de complejidad, pueden ser decisivas desde el punto de vista de ingeniería. Pueden darse incluso ejemplos más dramáticos:
|algoritmo |tiempo |complejidad |
|f |n |O(n) |
|g |100 n |O(n) |Aún siendo dos algoritmos con idéntico comportamiento asintótico, es obvio que el algoritmo "f" es siempre 100 veces más rápido que el "g" y candidato primero a ser utilizado.
• ... usualmente un programa de baja complejidad en cuanto a tiempo de ejecución, suele conllevar un alto consumo de memoria; y viceversa. A veces hay que sopesar ambos factores, quedándonos en algún punto decompromiso.
• ... en problemas de cálculo numérico hay que tener en cuenta más factores que su complejidad pura y dura, o incluso que su tiempo de ejecución: queda por considerar la precisión del cálculo, el máximo error introducido en cálculos intermedios, la estabilidad del algoritmo, etc. etc.
Reglas Prácticas
Aunque no existe una receta que siempre funcione para calcular la complejidadde un algoritmo, si es posible tratar sistemáticamente una gran cantidad de ellos, basándonos en que suelen estar bien estructurados y siguen pautas uniformes.
Loa algoritmos bien estructurados combinan las sentencias de alguna de las formas siguientes
1. sentencias sencillas
2. secuencia (;)
3. decisión (if)
4. bucles
5. llamadas a procedimientos
4.0. Sentenciassencillas
Nos referimos a las sentencias de asignación, entrada/salida, etc. siempre y cuando no trabajen sobre variables estructuradas cuyo tamaño este relacionado con el tamaño N del problema. La inmensa mayoría de las sentencias de un algoritmo requieren un tiempo constante de ejecución, siendo su complejidad O(1).
4.1. Secuencia (;)
La complejidad de una serie de elementos de un programaes del orden de la suma de las complejidades individuales, aplicándose las operaciones arriba expuestas.
4.2. Decisión (if)
La condición suele ser de O(1), complejidad a sumar con la peor posible, bien en la rama THEN, o bien en la rama ELSE. En decisiones múltiples (ELSE IF, SWITCH CASE), se tomara la peor de las ramas.
4.3. Bucles
En los bucles con contador explícito, podemos...
|CHRISTIAN RENE AVIÑA MEDINA |
|LUIS ANGEL ALCALA GALLARDO |
|EDUARDO IVAN SANCHEZ DE LA CRUZ|
|IVAN SORIA ALVARADO |
Análisis de Algoritmos
Tiempo de Ejecución
Una medida que suele ser útil conocer es el tiempo de ejecución de un programa en función de N, lo que denominaremos T(N). Esta función se puede medir físicamente (ejecutando elprograma, reloj en mano), o calcularse sobre el código contando instrucciones a ejecutar y multiplicando por el tiempo requerido por cada instrucción. Así, un trozo sencillo de programa como
S1; for (int i= 0; i < N; i++) S2;
Requiere
T(N)= t1 + t2*N
Siendo t1 el tiempo que lleve ejecutar la serie "S1" de sentencias, y t2 el que lleve la serie "S2".
Prácticamente todos los programasreales incluyen alguna sentencia condicional, haciendo que las sentencias efectivamente ejecutadas dependan de los datos concretos que se le presenten. Esto hace que más que un valor T(N) debamos hablar de un rango de valores
Tmin(N) 100.
Si nuestro problema no va a tratar jamás problemas de tamaño mayor que 100, es mejor solución usar el algoritmo "g".
El ejemplo anterior muestraque las constantes que aparecen en las fórmulas para T(n), y que desaparecen al calcular las funciones de complejidad, pueden ser decisivas desde el punto de vista de ingeniería. Pueden darse incluso ejemplos más dramáticos:
|algoritmo |tiempo |complejidad |
|f |n |O(n) |
|g |100 n |O(n) |Aún siendo dos algoritmos con idéntico comportamiento asintótico, es obvio que el algoritmo "f" es siempre 100 veces más rápido que el "g" y candidato primero a ser utilizado.
• ... usualmente un programa de baja complejidad en cuanto a tiempo de ejecución, suele conllevar un alto consumo de memoria; y viceversa. A veces hay que sopesar ambos factores, quedándonos en algún punto decompromiso.
• ... en problemas de cálculo numérico hay que tener en cuenta más factores que su complejidad pura y dura, o incluso que su tiempo de ejecución: queda por considerar la precisión del cálculo, el máximo error introducido en cálculos intermedios, la estabilidad del algoritmo, etc. etc.
Reglas Prácticas
Aunque no existe una receta que siempre funcione para calcular la complejidadde un algoritmo, si es posible tratar sistemáticamente una gran cantidad de ellos, basándonos en que suelen estar bien estructurados y siguen pautas uniformes.
Loa algoritmos bien estructurados combinan las sentencias de alguna de las formas siguientes
1. sentencias sencillas
2. secuencia (;)
3. decisión (if)
4. bucles
5. llamadas a procedimientos
4.0. Sentenciassencillas
Nos referimos a las sentencias de asignación, entrada/salida, etc. siempre y cuando no trabajen sobre variables estructuradas cuyo tamaño este relacionado con el tamaño N del problema. La inmensa mayoría de las sentencias de un algoritmo requieren un tiempo constante de ejecución, siendo su complejidad O(1).
4.1. Secuencia (;)
La complejidad de una serie de elementos de un programaes del orden de la suma de las complejidades individuales, aplicándose las operaciones arriba expuestas.
4.2. Decisión (if)
La condición suele ser de O(1), complejidad a sumar con la peor posible, bien en la rama THEN, o bien en la rama ELSE. En decisiones múltiples (ELSE IF, SWITCH CASE), se tomara la peor de las ramas.
4.3. Bucles
En los bucles con contador explícito, podemos...
Leer documento completo
Regístrate para leer el documento completo.