• Author / Uploaded
• Juan

Citation preview

ANÁLISIS DE ALGORÍTMOS PRESIMIG15146 Grupo: PREPRO20020050005 --- 005 Docente: Silvana L. Vallejo Córdoba [email protected]

NOTACIÓN ASINTÓTICA Eficiencia de un algoritmo *Notación asintótica *T(n): funciones de tiempo de ejecución (tasa de crecimiento) *BIG-O • Generalidades del planteamiento (Ejemplos)

Eficiencia • Medida del uso de los recursos computacionales requeridos por la ejecución de un algoritmo en función del tamaño de las entradas. • T(n) Tiempo empleado para ejecutar el algoritmo con una entrada de tamaño n Tipos de análisis ¿Cómo medimos el tiempo de ejecución de un algoritmo?

¿Qué es un función asintótica? Función g(x) tal que converge asintóticamente (se aproxima pero no llega a igualarse) a una función dada f(x) (T(n)_ en análisis de algoritmos) para todo x>x0.

Orden de eficiencia NOTACIÓN O (Big –O): • Decimos que una función T(n) es O(g(n)) si existen constantes n0 y c tales que T(n) n0. • Delimita el peor de los casos: tiempo máximo que puede llegar a tomar una ejecución.

NOTACIÓN Ω (Big –Ω ): • Decimos que una función T(n) es Ω(g(n)) si existen constantes n0 y c tales que T(n) >= cg(n) para todo n > n0. • Delimita el mejor de los casos: tiempo mínimo que puede llegar a tomar una ejecución.

NOTACIÓN Ꝋ (Big –Ꝋ): • Decimos que una función T(n) es Ꝋ(g(n)) si existen constantes n0, c1 y c2 tales que c1 3 de números enteros en el rango de 0 a255.