PDF de programación - Notación Asintótica

Notación Asintótica

Análisis de Algoritmos

Temas

Introducción
Notación “O”
Notación “Omega”
Notación “Theta”

1

Introducción

¿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

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

2

Introducción

Para realizar el análisis de un algoritmo, es

necesario:
Conocer la complejidad del problema que resuelve el

Conocer la dimensión de la entrada (número de

algoritmo

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

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
o má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?

3

Principio de la Invarianza

A través de un análisis teórico, se puede

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
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 un problema

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”?

4

Operación Elemental (OE)

Es aquella operación cuyo tiempo de

ejecución se puede acotar superiormente 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

Notación Asintótica

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 realizar por el mismo

Se define en términos de funciones matemáticas,

el orden de la función

Se clasifica de acuerdo a su complejidad

5

Orden O

Dada una función g(n), denotamos como O(g(n)) al

conjunto de funciones tales que:
O(g(n)) = {f:NR+ | ∃ c constante positiva y no∈N : f(n) ≤

cg(n), ∀ n ≥ n0}

Notación Omega

Dada una función g(n), denotamos al conjunto de

funciones Ω(g(n)) de la siguiente forma:
Ω(g(n)) = {f:NR+ | ∃ c constante positiva y n0: 0 < cg(n) ≤

f(n), ∀ n ≥ n0}

NOTA: f(n)∈ Ω(g(n)) si y solo si g(n)∈O(f(n))

6

Notación Theta

Diremos que f(n)∈Θ(g(n)) si f(n) pertenece tanto a

O(g(n)) como a Ω(g(n))

Θ(g(n)) = {f:NR+ | ∃c1,c2 constantes positivas, n0: 0 < c1g(n) ≤

f(n) ≤ c2g(n), ∀ n ≥ n0}

Ejemplo – Theta (1/3)

Considere la función f(n) = ½ n2 – 3n

Debido a que f(n) es un polinomio cuadrático, se
deduce que su estructura general tiene la forma
an2 + bn + c

Para n muy grande, an2 “domina” al resto de la

ecuación

Por tanto, se propone una g(n) = n2 de tal forma

que se demostrará si f(n) ∈ Θ(n2)

7

Ejemplo – Theta (2/3)

Para demostrarlo, se debe apelar a la

definición de Θ:

Θ(n2) = {f(n) | ∃c1,c2 constantes positivas, n0: 0 < c1n2 ≤ f(n)
Se deben encontrar c1, c2 y n0 para los cuales se

≤ c2 n2, ∀ n ≥ n0}, donde f(n) = ½ n2 – 3n

cumple

0 < c1n2 ≤ ½ n2 – 3n ≤ c2 n2

0 < c1 ≤ ½ – 3/n ≤ c2

Esta ecuación se analiza por casos:

c1 ≤ ½ – 3/n
½ – 3/n ≤ c2

Ejemplo – Theta (3/3)

Para el caso c1 ≤ ½ – 3/n

Como c1 es constante positiva, entonces

0 < ½ - 3/n

⇒ n > 6

Por tanto, si n0 = 7, entonces c1 ≤ ½ – 3/7, lo

que es igual a c1 ≤ 1/14. Sea c1 = 1/14

Para el caso ½ – 3/n ≤ c2, cuando n ∞
entonces ½ – 3/n ½. Por tanto, c2 = 1/2
Para c1 = 1/14, c2 = ½ y n0 = 7 se cumple

que f(n) ∈ Θ(n2)

8

Ejemplo O

Considere la función f(n) = 2n2 + 3n + 1

Debido a que f(n) es un polinomio cuadrático, se
deduce que su estructura general tiene la forma
an2 + bn + c

Para n muy grande, an2 “domina” al resto de la

ecuación

Por tanto, se propone una g(n) = n2 de tal forma

que se demostrará si f(n) ∈ O(n2)

Ejemplo O

Para demostrarlo, se debe apelar a la

definición de O:

O(n2) = {f(n) | ∃c constante positiva, n0: 0 < f(n) ≤ c n2, ∀ n

≥ n0}, donde f(n) = 2n2 + 3n + 1

Se deben encontrar c y n0 para los cuales se

cumple

0 < 2n2 + 3n + 1 ≤ c n2
0 < 2 + 3/n + 1/n2 ≤ c
Notemos que si n ∞, 2 + 3/n + 1/n2 2
Si n = 1 entonces 2 + 3/n + 1/n2 = 6
Por tanto, para c = 6 y n0 = 1, se demuestra que f(n) ∈

O(n2)

9

Orden de Complejidad

La familia O(f(n)), Ω(f(n)), Θ(f(n)) define un

orden de complejidad
Se elige como representante del orden de

complejidad a la función f(n) más sencilla de la
familia

Se identifican diferentes familias de orden de

complejidad

Orden de Complejidad

O(c) : Orden constante
O(log n): orden logarítmico
O(n): orden lineal
O(n log n): orden “casi lineal”
O(n2): Orden cuadrático
O(n3): Orden cúbico
O(nc): Orden polinómico de grado “c”
O(2n): Orden exponencial
O(n!): Orden factorial

10

Orden de Complejidad

140

120

100

80

60

40

20

0

1

2

3

4

5

6

7

8

9

10

Constante
Log
Lineal
Casi lineal
Cuadrático
Cúbico
Potencia
Factorial

Consejos para Identificar f(n)
que Represente el Número de
OE de un Algoritmo

11

Consejo 1

Se asume que el tiempo de una OE es de

orden 1
La constante “c” del principio de la invarianza se

asume, por fines prácticos, como 1

El tiempo de ejecución de una secuencia de

instrucciones (elementales o no
elementales), se obtiene sumando los
tiempos de ejecución de cada instrucción

Consejo Instrucción “case”

El tiempo de ejecución de una instrucción
“switch(n) – case 1: S1, …, case k: Sk es:

f(n) = f(c) + max{f(S1), …, f(Sk)}

f(c) considera el tiempo de comparación de “n”

con cada uno de los casos case 1 … case k

12

Consejo Instrucción “if”

El tiempo de ejecución de una instrucción “if

C then S1 else S2” es:

f(n) = f(C) + max{f(S1), f(S2)}

if (n == 0)

for (i = 0; i<n; i++)

r += i;

else

r = 2;

Consejo Instrucción “while”

Tiempo de ejecución de la instrucción:

while (c) {
S
}
es definido por:

f(n) = f(c) + (#iteraciones)*(f(c)+f(s))

Nota: las instrucciones for, repeat, loop son

equivalentes a una instrucción while

13

Consejo Instrucción “while”

for (i = 0; i <= n; i++)
{
S;

}

i = 1;
while (i <= n)
{

S;
i++;

}

Consejo Llamado a Funciones NO
Recursivas
El tiempo de ejecución de una llamada a una

función F(A1, …, As) es:
1, por el llamado a la función, más
Tiempo de evaluación de los parámetros A1, …,

As

Tiempo de ejecución de la función (s)

f(A1, …, As) = 1 + f(A1) + … + f(As) + f(s)

14

Consejo para Funciones Recursivas

El tiempo de ejecución de una función

recursiva se calcula a través de la solución
de funciones de recurrencia (siguiente tema)

15