Tema 2 - Notación Asintótica

5/9/2018 Tema 2 - Notación Asintótica - slidepdf.com

http://slidepdf.com/reader/full/tema-2-notacion-asintotica 1/37

1

DR. JESÚS A. GONZÁLEZ BERNAL

CIENCIAS COMPUTACIONALES

INAOE

Análisis y Diseño de Algoritmos

Notación Asintótica



2Introducció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

2



3Introducción

Ventajas

Elección de algoritmos eficientes para resolver problemasespecíficos

No depende de lenguajes de programación ni de hardware

Desventajas Para muchos casos, en análisis no es trivial

3



4Introducción

Para realizar el análisis de un algoritmo, es necesario:

Conocer la complejidad del problema que resuelve el algoritmo Conocer la dimensión de la entrada (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…

4



5Introducció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 complejidaddepende de identificar la operación más costosa en elalgoritmo Por ejemplo, sume 2 matrices e imprima el resultado. ¿de que

orden es el problema?

5



6Principio de 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 constantemultiplicativa “c”

6



7 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 elalgoritmo de ordenamiento “burbuja”?

7



8Operación Elemental (OE)

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

puede acotar superiormente por una constante quesolamente dependerá de la implementaciónparticular usada No depende de parámetros

No depende de la dimensión de los datos de entrada

8



9Crecimiento de Funciones

Orden decrecimiento de funciones

Caracteriza eficiencia de algoritmos Permite comparar performance relativo de algoritmos

Es posible en ocasiones calcular el tiempo de

ejecución exacto No siempre vale la pena el esfuerzo

Las constantes y términos de orden más bajo son dominadospor los efectos del tamaño de la entrada

9



10

Crecimiento de Funciones

• Eficiencia Asintótica de Algoritmos

• Cuando el tamaño de la entrada es suficientemente grande quesólo el orden de crecimiento del tiempo de ejecución esrelevante.

• 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 mejor opción, excepto para entradasmuy pequeñas

10



11

Notación Asintótica

Eficiencia Asintótica

Orden de crecimiento del algoritmo conforme el tamaño dela entrara se acerca al límite (incrementa sin frontera)

Para determinar la complejidad de un algoritmo, sesiguen 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 el orden de la función en términos de funcionesmatemáticas,

Se clasifica de acuerdo a su complejidad

11



12

Notación O

f(n) = O(g(n)), g(n) es una cota superior de f(n)

Dada una función g(n), denotamos como O(g(n)) alconjunto de funciones tales que:

O(g(n)) = f:NR + | ∃ c constante positiva y no∈N : f(n) ≤ cg(n),∀ n ≥ n0

12



13

Propiedades de O

1. Para cualquier función de f se tiene que f ∈ O(f ).

2. f ∈

O(g)⇒

O(f )⊂

O(g).3. O(f ) = O(g) ⇔ f ∈ O(g) y g ∈ O(f ).

4. Si f ∈O(g) y g ∈ O(h) ⇒ f ∈ O(h).

5. Si f ∈ O(g) y f ∈ O(h) ⇒ f ∈O(min(g,h)) .

6. Regla de la suma: Si f 1 ∈ O(g) y f 2 ∈ O(h) ⇒ f 1 + f 2 ∈ O(max(g,h)).

7. Regla del producto: Si f 1 ∈ O(g) y f 2 ∈ O(h) ⇒ f 1 • f 2 ∈ O(g • h) .

8. Si existe , dependiendo del valor de k obtenemos:

a) Si k ≠ 0 y k < ∞ entonces O(f ) = O(g).

b) Si k = 0 entonces f ∈O(g), es decir, O(f ) ⊂ O(g), pero sin embargo se

verifica que g ∉ O(f ).

k ng

n f

n=

∞→ )(

)(lim



14

Notación Omega

f(n) = Ω(g(n)), g(n) es una cota asintótica inf. de f(n)

Dada una función g(n), denotamos al conjunto defunciones Ω(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))

14



15

Propiedades de Omega

1. Para cualquier función de f se tiene que f ∈ Ω(f ).

2.f

∈ Ω

(g)⇒ Ω

(f )⊂ Ω

(g).3. Ω(f ) = Ω(g) ⇔ f ∈ Ω(g) y g ∈ Ω(f ).

4. Si f ∈ Ω(g) y g ∈ Ω(h) ⇒ f ∈ Ω(h).

5. Si f ∈ Ω(g) y f ∈ Ω(h) ⇒ f ∈ Ω(max(g,h)) .

6. Regla de la suma: Si f 1 ∈ Ω(g) y f 2 ∈ Ω(h) ⇒ f 1 + f 2 ∈ Ω(g + h).

7. Regla del producto: Si f 1 ∈ Ω(g) y f 2 ∈ Ω(h) ⇒ f 1 • f 2 ∈ Ω(g • h) .


a) Si k ≠ 0 y k < ∞ entonces Ω(f ) = Ω(g).

b) Si k = 0 entonces g ∈ Ω(f ), es decir, Ω(g) ⊂ Ω(f ), pero sin embargo se

verifica que f ∉ Ω(g).

k ng

n f

n=

∞→ )(

)(lim



16

Notación Theta

f(n) = Θ (g(n)), c2g(n) y c1g(n) son las cotas asintóticas

de f(n) tanto superior como inferior respectivamente 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

16



17

Propiedades de Theta

1. Para cualquier función f se tiene que f ∈ Θ(f ).

2.f

∈ Θ

(g)⇒ Θ

(f )⊂ Θ

(g).3. Θ(f ) = Θ(g) ⇔ f ∈ Θ(g) y g ∈ Θ(f ).

4. Si f ∈ Θ(g) y g ∈ Θ(h) ⇒ f ∈ Θ(h).

5. Regla de la suma: Si f 1 ∈ Θ(g) y f 2 ∈ Θ(h) ⇒ f 1 + f 2 ∈ Θ(max(g,h)).

6. Regla del producto: Si f 1 ∈ Θ(g) y f 2 ∈ Θ(h) ⇒ f 1 • f 2 ∈ Θ(g • h) .


a) Si k ≠ 0 y k < ∞ entonces Θ(f ) = Θ(g).

b) Si k = 0 entonces los órdenes exactos de f y g son distintos.

k ng

n f

n=

∞→ )(

)(lim



18

Notación Theta

Teorema 2.1

f(n) = Θ(g(n)) si y sólo sí f(n) = O(g(n)) y f(n) = Ω(g(n)).



19

Ejemplo – Theta (1/3)

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

Debido a que f(n) es un polinomio cuadrático, se deduce quesu 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)

19



20


Para demostrarlo, se debe apelar a la definición de Θ:Θ(n2) = f(n) | ∃c1,c2 constantes positivas, n0: 0 < c1n

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

Se deben encontrar c1, c2 y n0 para los cuales se 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

20



21


Para el caso c1 ≤ ½ – 3/n Como c

1es constante positiva, entonces

0 < ½ - 3/n

⇒ n > 6

Por tanto, si n0 = 7, entonces c1 ≤ ½ – 3/7, lo que es igual ac

1

≤ 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)

21



22

Ejemplo O (1/2)

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

Debido a que f(n) es un polinomio cuadrático, se deduce quesu 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)

22



23

Ejemplo O (2/2)

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 2Si n = 1 entonces 2 + 3/n + 1/n2 = 6

Por tanto, para c = 6 y n0 = 1, se demuestra que f(n) ∈ O(n2)

23



24

Notación o

f(n) = o(g(n)), g(n) es una cota superior de f(n) que

no es asintóticamente justa (tight)



25

Notación ω

f(n) = ω(g(n)), g(n) es una cota inferior de f(n) que

no es asintóticamente justa (tight)



26

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

26



27

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

27



28

Orden de Complejidad28

0

20

40

60

80

100

120

140

1 2 3 4 5 6 7 8 9 10

Constante

Log

Lineal

Cas i lineal

Cuadrático

Cúbico

Potencia

Factorial



29

Consejos

Consejos para Identificar f(n) que Represente el

Número de Operaciones Elementales (OE) de un Algoritmo

29



30

Consejo 1

Se asume que el tiempo de una OE es de orden 1

La constante “c” del principio de la invarianza se asume, porfines prácticos, como 1

El tiempo de ejecución de una secuencia deinstrucciones (elementales o no elementales), se

obtiene sumando los tiempos de ejecución de cadainstrucción

30



31

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) + maxf(S1), …, f(Sk )

f(c) considera el tiempo de comparación de “n” con cada unode los casos case 1 … case k

31



32

Consejo Instrucción “if”

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

S1 else S2” es: f(n) = f(C) + maxf(S1), f(S2)

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

r += i;

elser = 2;

32



33

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

33



34

Consejo Instrucción “while”34

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

S;

i = 1;

while (i <= n)

S;

i++;



35

Consejo Llamado a Funciones NO Recursivas

El tiempo de ejecución de una llamada a una función

F(A 1, …, A s) es: 1, por el llamado a la función, más

Tiempo de evaluación de los parámetros A 1, …, A s Tiempo de ejecución de la función (s)

f(A 1, …, A s) = 1 + f(A 1) + … + f(A s) + f(s)

35



36

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 derecurrencia (siguiente tema)

36



37

Tarea

Ejercicios 2.1-3, 2.2-2 (del Cormen, Leiserson,Rivest, Stein)

¿Cuáles de las siguientes afirmaciones es cierta?

n2 ∈ O(n3)

2n+1 ∈ O(2n)

n2 ∈ Ω(n3)

Tema 2 - Notación Asintótica

Documents

Transcript of Tema 2 - Notación Asintótica