NotacionA

Análisis y Diseño de Algoritmos
Notación Asintótica
DR. JESÚS A. GONZÁLEZ BERNAL
CIENCIAS COMPUTACIONALES
INAOE

Introducción
2

—  ¿Por qué el análisis de algoritmos?
¡  Determinar tiempos de respuesta (runtime)
¡  Determinar recursos computacionales
—  Aproximación teórica
¡  Generaliza el número de operaciones que requiere un
algoritmo para encontrar la solución a un problemaIntroducción
3

—  Ventajas
¡  Elección de algoritmos eficientes para resolver problemas
específicos
¡  No depende de lenguajes de programación ni de hardware
—  Desventajas
¡  Para muchos casos, en análisis no es trivial

Introducción
4

—  Para realizar el análisis de un algoritmo, es necesario:
¡  Conocer la complejidad del problema que resuelve el algoritmo
¡  Conocer la dimensión de laentrada (número de elementos)
¡  Determinar el número de operaciones a realizar
—  La complejidad de un algoritmo se representa a través

de una función matemática
Polinomios
¡  Logaritmos
¡  Exponentes…
¡ 

Introducción
5

—  Funciones
¡  f(n) = cn (algoritmos lineales)
¡  f(n) = cn2 (algoritmos cuadráticos)
¡  f(n) = cn3 (algoritmos cúbicos)
—  Un algoritmo puede estar compuesto de dos omás

operaciones, por lo que determinar la complejidad
depende de identificar la operación más costosa en el
algoritmo
¡ 

Por ejemplo, sume 2 matrices e imprima el resultado. ¿de que
orden es el problema?

Principio de Invarianza
6

—  A través de un análisis teórico, se pueden obtener

funciones que representen el número de
operaciones, independientemente de cómo se
implementaron
—  Análisis“Principio de la Invarianza”
¡ 

Dos implementaciones distintas de un mismo algoritmo no
van a diferir en su eficiencia en más de una constante
multiplicativa “c”

Análisis Peor Caso – Caso Promedio - Mejor Caso
7

—  El tiempo que requiere un algoritmo para dar una

respuesta, se divide generalmente en 3 casos
Peor Caso: caso más extremo, donde se considera el tiempo
máximo para solucionar unproblema
¡  Caso promedio: caso en el cual, bajo ciertas restricciones, se
realiza un análisis del algoritmo
¡  Mejor caso: caso ideal en el cual el algoritmo tomará el menor
tiempo para dar una respuesta
¡ 

—  Por ejemplo, ¿Cuál es el peor y mejor caso de el

algoritmo de ordenamiento “burbuja”?

Operación Elemental (OE)
8

—  Es aquella operación cuyo tiempo de ejecución se

puede acotarsuperiormente por una constante que
solamente dependerá de la implementación
particular usada
No depende de parámetros
¡  No depende de la dimensión de los datos de entrada
¡ 

Crecimiento de Funciones
9

—  Orden de crecimiento de funciones
¡  Caracteriza eficiencia de algoritmos
¡  Permite comparar performance relativo de algoritmos
—  Es posible en ocasiones calcular el tiempo de

ejecuciónexacto
No siempre vale la pena el esfuerzo
¡  Las constantes y términos de orden más bajo son dominados
por los efectos del tamaño de la entrada
¡ 

Crecimiento de Funciones
10

—  Diccionario de la Real Academia Española
¡  Asintótico, ca (De asíntota).
÷  Adj.

Geom. Dicho de una curva: Que se acerca de continuo a una
recta o a otra curva sin llegar nunca a encontrarla.

Crecimiento deFunciones
11

•  Eficiencia Asintótica de Algoritmos
•  Cuando el tamaño de la entrada es suficientemente grande que
sólo el orden de crecimiento del tiempo de ejecución es
relevante.
•  Sólo importa cómo incrementa el tiempo de ejecución con el
tamaño de la entrada en el límite
• 

El tamaño de la entrada incrementa sin frontera

•  Usualmente el algoritmo asintóticamente más

eficiente es la mejoropción, excepto para entradas
muy pequeñas

Notación Asintótica
12

—  Eficiencia Asintótica
¡  Orden de crecimiento del algoritmo conforme el tamaño de
la entrada se acerca al límite (incrementa sin frontera)
—  Para determinar la complejidad de un algoritmo, se

siguen los siguientes pasos:
Se analiza el algoritmo para determinar una función que
represente el número de operaciones a...