Modelo de Costo

Que es?

Marco matemático que sirve para analizar la complejidad de un algoritmo, puede estar determinado por varios factores: memoria tiempo etc. En general se expresa en términos de una función que describe el numero de operaciones en funcion del tamaño de la entrada

El costo secuencial (W) se refiere al costo de ejecutar un algoritmo con una sola unidad de procesador, a diferencia del costo paralelo (S) donde se pueden usar n procesadores pudiendo en este ultimo caso ser el costo menor ya que si es posible se pueden dividir las operaciones en los distintos procesadores

Notación asintótica

Nos permite tener una idea de el crecimiento de una función a medida que la entrada de este tienda a infinito, estas son O grande, Omega y Theta ademas nos proporciona una forma de comparar la eficiencia de diferentes algortimos

Notación O grande

Dado 2 funciones f(n) y g(n) decimos que f tiene orden de crecimiento O(g) si si existe un numero c real y un numero n0 natural de modo que para todo numero n mayor a n0 sucede que 0 <= f(n) <= c*g(n), es decir la notación O el conjunto de funciones que crecen a lo sumo más tan rápido como g(n) y notamos f pertenece a O(g)

Describe la cota superior o el peor caso del tiempo de ejecución de un algoritmo.

Notación Omega

Dado dos funciones f(n) y g(n) decimoes que f tiene orden de crecimiento Ω(g) si exite un c real y un numero n0 natural de modo que para todo numero n mayor que n0 sucede que 0 <= c*g(n) <= f(n), es decir la notacion Ω es el conjunto de funciones que crecen al menos tan rapido que g(n) y notamos f pertenece Ω(g)

Describe la cota inferior o el mejor caso del tiempo de ejecución de un algoritmo

Notación Theta

Dado dos funciones f(n) y g(n) decimos que f tiene orden de crecimiento Θ(g) si f pertenece a O(g) y g pertenece a O(f) es decir la notación Θ es el conjunto de funciones que tienen la misma tasa de crecimiento asintótico

Theta nos permite describir tanto la cota inferior como la cota superior del tiempo de ejecución de un algoritmo

Ejemplos: O(1) ⊂ O(lg n) ⊂ O(n) ⊂ O(n lg n) ⊂ O(n^2) ⊂ O(n^3 ) ⊂ O(n^n ) ⊂ O(n!)

Análisis de algoritmos

Haciendo uso de un determinado modelo de costo, buscamos estimar una cota asintotica (estimación teórica del comportamiento de una función cuando el tamaño de su entrada tiende a infinito) mas no estimar el tiempo de ejecución de un algoritmo

Para ello definiremos Trabajo y profundidad en función de un lenguaje para luego al intentar calcularlos y obtener recurrencias(funciones recursivas) que luego abalizaremos su crecimiento.

Sea el lenguaje:

• Constantes: 0,1,2,… True, False, []
• Operadores: +,-,*,/,<,>,&&,||, if_then_else,▹
• Pares ordinarios y paralelos (3,4) (3+4 || 5+6)
• Expresiones let (nombres locales) let x = 3+4 in x+x
• Secuencias [ x*2 | x ← xs]

Trabajo

W(c) = 1

W(op e) = 1 + W(e)

W(e1, e2) = 1 + W(e1) + W(e2)

W(e1 || e2) = 1 + W(e1) + W(e2)

W(𝗅𝖾𝗍 x = e1 𝗂𝗇 e2) = 1 + W(e1) + W(e2(x ↦ Eval(e1)))

W([f(x) ∣ x ← xs]) = 1 + ∑_{x∈xs} W(f(x))

Profundidad

S(c) = 1

S(op e) = 1 + S(e)

S(e1, e2) = 1 + S(e1) + S(e2)

S(e1 || e2) = 1 + max(S(e1), S(e2))

S(𝗅𝖾𝗍 x = e1 𝗂𝗇 e2) = 1 + S(e1) + S(e2(x ↦ Eval(e1)))

S([f(x) ∣ x ← xs]) = 1 + max_{x∈xs} S(f(x))

Ejemplo Mergesort

msort : [Int] → [Int]
msort []  = [] 
msort [x] = [x] 
msort xs  = let (ls ,rs ) = split xs
                (ls’,rs’) = msort ls || msort rs 
            in merge (ls’,rs’)


split : [Int] → [Int]✕[Int]
split []  = ([],[]) 
split [x] = ([x],[]) 
split (x:y:zs) = let (xs,ys) = split zs
                 in (x:xs,y:ys)


merge : [Int]✕[Int] → [Int] 
merge ( [], ys)   = ys 
merge ( xs, [])   = xs 
merge (x:xs,y:ys) = if x <= y 
                      then x:merge(xs,y:ys) 
                      else y:merge(x:xs,ys)

Mergesort trabajo

Wmsort (0) = c0

Wmsort (1) = c1

Wmsort (n) = Wsplit (n) + 2Wmsort (n/2) + Wmerge(n) + c2 si n > 1

Wsplit (0) = c3

Wsplit (1) = c4

Wsplit (n) = Wsplit (n − 2) + c5 si n > 1, O(n)

Wmerge(0) = c6

Wmerge(n) = Wmerge(n − 1) + c7 , O(n)

Wmsort (n) = 2Wmsort (n/2) + c3n si n > 1 , O(n lg n)

Mergesort Profundidad

Smsort (0) = k0

Smsort (1) = k1

Smsort (n) = Ssplit (n) + Smsort (n/2) + Smerge(n) + k2 si n > 1

Ssplit (0) = k3

Ssplit (1) = k4

Ssplit (n) = Ssplit (n − 2) + k5 si n > 1, O(n)

Smerge(0) = k6

Smerge(n) = Smerge(n − 1) + k7, O(n)

Smsort (n) = Smsort (n/2) + k3n , O(n)

n es la suma de las longitudes de las listas argumento