introcuccion libre

Páginas: 8 (1892 palabras) Publicado: 3 de marzo de 2014
Metodología y Tecnología de la
Programación
Curso 2008/09
Tema 5
Introducción a la Complejidad Algorítmica

Temario
Tema 5. Introducción a la Complejidad Algorítmica

5.1 Algoritmos sencillos y complejos
5.1.1 Factores del Tiempo de Ejecución

5.2 Casos Peor y Promedio
5.3 Notaciones Asintóticas
5.3.1 Notaciones O y Ω
5.3.2 La Velocidad de Crecimiento
5.3.3 Funciones deComplejidad más Usuales

5.4 Cálculo del Tiempo de Ejecución de un Algoritmo
5.4.1
5.4.2
5.4.3
5.4.4
5.4.5

Operaciones en Notación Asintótica
Series
Cálculo del Tiempo de Ejecución
Reglas Generales para Análisis de Algoritmos
Propiedades de la Notación
Metodología y Tecnología de la Programación
Tema 5. Introducción a la Complejidad Algorítmica

2

1

Temario
Tema 5. Complejidad deAlgoritmos

5.1 Algoritmos sencillos y complejos
5.1.1 Factores del Tiempo de Ejecución

5.2 Casos Peor y Promedio
5.3 Notaciones Asintóticas
5.3.1 Notaciones O y Ω
5.3.2 La Velocidad de Crecimiento
5.3.3 Funciones de Complejidad más Usuales

5.4 Cálculo del Tiempo de Ejecución de un Algoritmo
5.4.1
5.4.2
5.4.3
5.4.4
5.4.5

Operaciones en Notación Asintótica
Series
Cálculo delTiempo de Ejecución
Reglas Generales para Análisis de Algoritmos
Propiedades de la Notación
Metodología y Tecnología de la Programación
Tema 5. Introducción a la Complejidad Algorítmica

3

5.1 Algoritmos sencillos y complejos
Cuando hay necesidad de elegir entre varios algoritmos, ¿cómo se debe elegir?
Hay tres objetivos que suelen contradecirse:
1. Que el algoritmo sea fácil deentender, codificar y depurar.
2. Que el algoritmo se ejecute con la mayor rapidez posible.
3. Que el algoritmo utilice de forma óptima la memoria disponible.
Lo que suele ocurrir frecuentemente:
Se implanta primero un algoritmo sencillo
Se efectúan simulaciones y mediciones antes de dedicarse al diseño
definitivo
Se determina el beneficio real que se obtendría escribiendo un
algoritmo máscomplejo.

Metodología y Tecnología de la Programación
Tema 5. Introducción a la Complejidad Algorítmica

4

2

5.1.1 Factores del Tiempo de Ejecución
El tiempo de ejecución de un programa depende de factores como:
1. Los datos de entrada al programa.
2. La calidad del código generado por el compilador utilizado para crear el
programa objeto.
3. La naturaleza y rapidez de lasinstrucciones de máquina empleadas en la
ejecución del programa, y
4. La complejidad de tiempo del algoritmo base del programa.
Con frecuencia, el tiempo de ejecución no depende de la entrada exacta, sino
sólo de su tamaño. Un buen ejemplo de esto es el proceso conocido como
clasificación u ordenación.
La medida natural del tamaño de la entrada a un programa de clasificación es
el número de elementos aordenar o, en otras palabras, la longitud de la lista de
entrada.
En general, la longitud de entrada es una medida apropiada de tamaño, y
se supondrá que tal es la medida utilizada.
Metodología y Tecnología de la Programación
Tema 5. Introducción a la Complejidad Algorítmica

5

5.2 Casos Peor y Promedio
T(n): tiempo de ejecución de un programa con una entrada de tamaño n.
Ejemplo: unprograma pueden tener un tiempo de ejecución T(n) = cn2,
donde c es una constante.
Las unidades de T(n) se dejan sin especificar. Se puede considerar a T(n)
como el número de instrucciones ejecutadas en un ordenador idealizado.
El tiempo de ejecución es en realidad una función de la entrada específica y
no sólo del tamaño de ella. En este caso se define T(n) como el tiempo de
ejecución delpeor caso, es decir, el máximo valor del tiempo de ejecución
para entradas de tamaño n
También se considera Tprom(n), el valor medio del tiempo de ejecución de
todas las entradas de tamaño n. Aunque Tprom(n) parece una medida más
razonable, es engañoso suponer que las entradas son igualmente probables.

Metodología y Tecnología de la Programación
Tema 5. Introducción a la Complejidad...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • Introcuccion Endodoncia
  • Introcuccion A Dfd
  • Introcuccion a la contabilidad
  • Introcuccion al derecho
  • Introcuccion al derecho
  • No logo introcuccion
  • Introcuccion a la biblia
  • Introcuccion de procedimientos de almacenamientos

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS