Upload
others
View
19
Download
0
Embed Size (px)
Citation preview
Analisis y Diseno de Algoritmos
Ingenierıa Civil Informatica
Gilberto Gutierrez
Universidad del Bıo-BıoDepartamento de Ciencias de la Computacion y TI
Primavera 2021
Analisis de Algoritmos
Indice
1 Analisis de AlgoritmosMotivacionConceptos FundamentalesAnalisis de Algoritmos no recursivosAnalisis de Algoritmos recursivos
2 Tecnicas de Diseno de AlgoritmosDividir para ReinarProgramacion DinamicaAlgoritmos VoracesBacktrackingRamificacion y Poda
Analisis de Algoritmos
Motivacion
PROBLEMA
A1
An
A2
...(Ordenamiento)
Preguntas
Analisis de Algoritmos
Motivacion
PROBLEMA
A1
An
A2
...(Ordenamiento)
Preguntas
1.¿A1 Es mejor que A2?
Analisis de Algoritmos
Motivacion
PROBLEMA
A1
An
A2
...(Ordenamiento)
Preguntas
1.¿A1 Es mejor que A2?
2.¿Cual es el mejor algoritmo?
Analisis de Algoritmos
Motivacion
PROBLEMA
A1
An
A2
...(Ordenamiento)
Preguntas
1.¿A1 Es mejor que A2?
2.¿Cual es el mejor algoritmo?
3.¿En que escenarios A2 es mejorque A1?
Analisis de Algoritmos
Motivacion
PROBLEMA
A1
An
A2
...(Ordenamiento)
Preguntas
1.¿A1 Es mejor que A2?
2.¿Cual es el mejor algoritmo?
3.¿En que escenarios A2 es mejorque A1?
4.¿Habra un algoritmo An+1
mejor que los que se conocen?
Analisis de Algoritmos
Motivacion
PROBLEMA
A1
An
A2
...(Ordenamiento)
Preguntas
1.¿A1 Es mejor que A2?
2.¿Cual es el mejor algoritmo?
3.¿En que escenarios A2 es mejorque A1?
4.¿Habra un algoritmo An+1
mejor que los que se conocen?
5.¿Cual es la cota inerior del prob-lema?
6. ¿...?
Analisis de Algoritmos
Motivacion
Ej. Dado un arreglo A de tamano n, ordenar los elementos de A demenor a mayor
Algorithm 1 SortBasico(A, n)
1: Input: A, n2: Output: A ordenado de menor a mayor3: for i = 1 to n − 1 do4: for j = i + 1 to n do5: if a[i ] > a[j ] then6: Intercambia(A, i , j)7: end if8: end for9: end for
Analisis de Algoritmos
Motivacion
Algorithm 2 InsertSort(A, n)
1: Input: A, n2: Output: A ordenado de menor a mayor3: for j = 1 to n do4: key = a[j ]5: i = j − 16: while i ≥ 0 and a[i ] > key do7: a[i + 1] = a[i ]8: i = i − 19: end while
10: a[i + 1] = key
11: end for
Analisis de Algoritmos
Motivacion
Algorithm 3 HeapSort(A, n)
1: Input: A, n2: Output: A ordenado de menor a mayor3: BuildHeap(A)4: for i = n− 1 to 0 do5: Intercambia(A, 0, i)6: Heapify(A, 0, i − 1)7: end for
Analisis de Algoritmos
Motivacion
Algorithm 4 BuildHeap(A, n)
1: Input: A, n2: Output: Un heap en A
3: for i = n/2; i >= 0; i −− do4: Heapify(A, i , n − 1)5: end for
Analisis de Algoritmos
Motivacion
Algorithm 5 Heapify(A, i , j)
1: Input: A, i , j2: Output: Heapify3: if (2 ∗ i + 1) ≤ j) then4: if (2 ∗ i + 2) ≤ j) then5: if (a[2 ∗ i + 2] ≥ a[2 ∗ i + 1]) then6: k = 2 ∗ i + 27: else8: k = 2 ∗ i + 19: end if
10: else11: k = 2 ∗ i + 112: end if13: if a[i ] < a[k ] then14: Intercambia(A, i , k);15: Heapify(A, k , j)16: end if17: end if
Analisis de Algoritmos
¿ Que medimos ?
Recursos consumidos por el algoritmo
Analisis de Algoritmos
¿ Que medimos ?
Recursos consumidos por el algoritmo
Tiempo
Analisis de Algoritmos
¿ Que medimos ?
Recursos consumidos por el algoritmo
Tiempo
Memoria (Almacenamiento)
Analisis del algoritmo (consumo de recursos)
Analisis de Algoritmos
¿ Que medimos ?
Recursos consumidos por el algoritmo
Tiempo
Memoria (Almacenamiento)
Analisis del algoritmo (consumo de recursos)
Empırico
Analisis de Algoritmos
¿ Que medimos ?
Recursos consumidos por el algoritmo
Tiempo
Memoria (Almacenamiento)
Analisis del algoritmo (consumo de recursos)
Empırico
Teorico
Analisis de Algoritmos
Medidas de la eficienciaUnidades medidas para el tiempo de ejecucion
Factores que interfieren en el tiempo de ejecucion: velocidad delcomputador, calidad de la implementacion del algoritmo(programa), compilador, etc.
Usar una metrica que no dependa de ninguno de esos factores.
Posible metrica, contar el numero de veces que cada operacion seejecuta. Esto es muy difıcil y muchas veces innecesario.
Mejor alternativa es identificar la operacion mas importante del
algoritmo (operacion relevante / basica ).
Analisis de Algoritmos
Medidas de la eficienciaLa operacion relevante
Es aquella que contribuye con la mayor parte del tiempo total deejecucion.
La operacion relevante, en la cual se basa el analisis, de algunaforma esta relacionada con el tipo de problema que se intentaresolver.
El proposito es calcular el numero de veces que se ejecuta laoperacion relevante.
El marco establecido para el analisis de la eficiencia de un algoritmosugiere medirlo contando el numero de veces que se ejecuta laoperacion relevante con entradas de tamano n.
Analisis de Algoritmos
Medidas de la eficienciaMidiendo el tiempo de ejecucion
Sea Cop el tiempo de ejecucion de la operacion relevante de unalgoritmo sobre un computador.
Sea C (n) el numero de veces que la operacion relevante se ejecuta.
El tiempo de ejecucion estimado T (n) de un programa queimplementa el algoritmo es:
T (n) ≈ Cop ∗ C (n)
Cop y C (n) son valores aproximados.
Sin embargo a nosotros nos interesa conocer C (n).
Analisis de Algoritmos
Medidas de la eficienciaOrdenes de crecimiento
Valores de varias funciones importantes usadas en el analisis de algoritmos
n log2 n n n log2 n n2 n3 2n n!
10 3.3 101 3.3× 101 102 103 103 3.6× 106
102 6.6 102 6.6× 102 104 106 1.3 × 1030 9.3× 10157
103 10 103 1.1× 104 106 109
104 13 104 1.3× 105 108 1012
105 17 105 1.7× 106 1010 1015
106 20 106 2.0× 107 1012 1018
Analisis de Algoritmos
Medidas de la eficienciaOrdenes de crecimiento
Es importante conocer el orden de crecimiento de una funcion paravalores grandes de n.
En el caso de las funciones 2n y n!, en ambas sus valores crecen deforma astronomica a medida que el valor de n crece.
Por ejemplo, si un computador moderno es capaz de ejecutar 1012
operaciones (1 billon aproximadamente) por segundo, entoncespodrıa demorar 4∗1010 anos en ejecutar 2100 operaciones (2100 ≈1, 2676506 ∗ 1030 operaciones).
Sin embargo, 100! toma aun mucho mas tiempo que 4,5 mil
millones de anos (100! = 9,332622∗10157, ≈ 2,959355∗10138 anos).
Analisis de Algoritmos
Analisis de la eficiencia de los algoritmosPeor caso, mejor caso, y caso promedio
Algorithm 6 SequentialSearch(int A[], int k)
1: Input: A: arreglo de tamano n; k : clave a buscar.2: Output: retorna posicion de i en A.3: i = 0;4: while (i < n) and (A[i ] 6= k) do5: i = i + 16: end while7: if i < n then8: return i ;9: else
10: return -1;11: end if
Analisis de Algoritmos
Analisis de la eficiencia de los algoritmosAnalisis para el peor caso
El peor caso se da cuando el algoritmo se ejecuta por el tiempo maslargo de entre todas las posibles entradas de tamano n.
Aquı hablamos de la peor entrada posible para el algoritmo.
En el ejemplo de la busqueda secuencial, el peor caso se da cuandoel elemento no existe en el arreglo o cuando este es el ultimo.
En este caso el numero de comparaciones es mayor. Cworst(n) = n.
Cworst(n) = max|A|=n
T (A); A: entrada; T: tiempo.
Esto nos permite encontrar una cota superior para el tiempo de
ejecucion el cual no excedera a Cworst(n), para cualquier entrada de
tamano n.
Analisis de Algoritmos
Analisis de la eficiencia de los algoritmosAnalisis para el mejor caso
El mejor caso se da cuando el algoritmo se ejecuta por el tiempomas pequeno de entre todas las posibles entradas de tamano n.
Aquı hablamos de la mejor entrada posible para el algoritmo.
En el ejemplo de la busqueda secuencial, el mejor caso se da cuandoel elemento buscado es el primero en el arreglo.
En este caso el numero de comparaciones es menor. Cbest(n) = 1.
Cbest(n) = min|A|=n
T (A); A: entrada; T: tiempo
Esto nos permite encontrar una cota inferior para el tiempo de
ejecucion el cual no es menor a Cbest(n), para cualquier entrada de
tamano n.
Analisis de Algoritmos
Analisis de la eficiencia de los algoritmosAnalisis para el caso promedio
Ni el peor caso y tampoco el mejor caso entregan la informacionnecesaria sobre el comportamiento real del algoritmo,
El analisis del caso promedio es recomendado cuando un algoritmotiene diferentes tiempos de ejecucion para el mismo tamano de laentrada.
Se deben construir algunos supuestos sobre las posibles entradas detamano n.
Analisis de Algoritmos
Analisis de la eficiencia de los algoritmosAnalisis para el caso promedio
En el caso de la busqueda secuencial tenemos dos supuestosestandar:
La probabilidad de una busqueda exitosa es igual a p (0 ≤ p ≤1).
La probabilidad de exito del primer acierto en la i-esimaposicion del arreglo es la misma para todo i .
En el caso de la busqueda exitosa la probabilidad del primer aciertoes p
n , mientras que en la busqueda no exitosa la probabilidad es(1− p).
Cavg (n) = [1 pn + 2 p
n + ... + i pn + ...+ n pn ] + n(1-p)
Analisis de Algoritmos
Analisis de la eficiencia de los algoritmosAnalisis para el caso promedio
El numero promedio de comparaciones esta dado por Cavg (n)
Cavg (n) = [1 pn + 2 p
n + ... + i pn + ...+ n pn ] + n(1− p)
= pn [1 + 2 + ... + i + ...+ n] + n(1 − p)
= pn [
n∑
i=1
i ] + n(1 − p)
= p(n+1)2 + n(1 − p)
Analisis de Algoritmos
Analisis de la eficiencia de los algoritmosAnalisis para el caso promedio
Los dos casos estan dados por:
p =
1 busqueda exitosa, numero de comparaciones: (n+1)2
0 busqueda no exitosa, numero de comparaciones: n
El estudio del caso promedio es mucho mas difıcil que el peor y elmejor de los casos.
Distribucion de la probabilidad de las entradas posibles se asumecomo el valor esperado del conteo de la operacion relevante:
Caso promedio =∑
|A|≤n
Pr(A)T (A)
Analisis de Algoritmos
Notaciones asintoticas y Clases de Eficiencia BasicasOrden de crecimiento
El ambito del analisis de la eficiencia se concentra en el orden decrecimiento del conteo de la operacion relevante del algoritmo.
Para comparar y “rankear” tales ordenes de crecimiento, en cienciasde la computacion se usan tres notaciones:
O (o grande).
Ω (omega grande).
Θ (teta grande).
Informalmente, O(g(n)) es el conjunto de todas las funciones conun orden de crecimiento mas bajo o el mismo que g(n).
Por ejemplo: n ∈ O(n2); 100n + 5 ∈ O(n2); n3 /∈ O(n2).
Analisis de Algoritmos
Notaciones Asintoticas y Clases de Eficiencia BasicasO grande
Definicion: una funcion f (n) es O(g(n)), si:
∃ c > 0, n0 > 0, tal que ∀ n ≥ n0, f (n) ≤ cg(n); [f (n) g(n)]
En este caso podemos decir que: f (n) es O(g(n)); o f (n) =O(g(n)); o f (n) ∈ O(g(n)).
Decimos entonces que f (n) esta acotado por arriba (cota superior)por una constante multiplo de g(n), ∀ n grande.
Por ejemplo: sea f(n) = 100n + 5 ∈ O(n2):
100n + 5 ≤ 100n + n (∀ n ≥ 5)
101n ≤ 101n, entonces las constantes c y n0 son: c = 101, n0 = 5.
o, 100n + 5 ≤ 100n + 5n, (∀ n ≥ 1), donde c = 105, n0 = 1.
Analisis de Algoritmos
Notaciones Asintoticas y Clases de Eficiencia BasicasO grande
Curvas de las funciones f(n) ≤ cg(n)
f(n)
c.g(n)
n0 n
Analisis de Algoritmos
Notaciones Asintoticas y Clases de Eficiencia BasicasΩ grande
Definicion: una funcion f (n) es Ω(g(n)), si:
∃ c > 0, n0 > 0, tal que ∀ n ≥ n0, f (n) ≥ cg(n); [f (n) g(n)]
En este caso podemos decir que: f (n) es Ω(g(n)); o f (n) =Ω(g(n)); o f (n) ∈ Ω(g(n)).
Decimos entonces que f (n) esta acotado por abajo (cota inferior)por una constante multiplo de g(n), ∀ n grande.
Por ejemplo: n3 ∈ Ω(n2), n3 ≥ Ω(n2), ∀ n ≥ 0, con c = 1, n0 = 0.
Ω tambien corresponde a la complejidad del problema (ej. elproblema de ordenamiento es Ω(n log2 n)).
Analisis de Algoritmos
Notaciones asintoticas y Clases de Eficiencia BasicasΩ grande
Curvas de las funciones f(n) ≥ cg(n)
n0 n
f(n)
cg(n)
Analisis de Algoritmos
Notaciones Asintoticas y Clases de Eficiencia BasicasΘ grande
Definicion: una funcion f (n) es Θ(g(n)), si es O(g(n)) y Ω(g(n)).
La funcion f (n) esta acotada por arriba y por abajo por algunaconstante positiva multiplo de g(n), ∀ n grande.
Es decir, si existen algunas constantes positivas c1, c2 y n0, tal que:
c2g(n) ≤ f (n) ≤ c1g(n), ∀ n ≥ n0.
Por ejemplo, el algoritmo de sorting MergeSort es Θ(n log2 n).
Analisis de Algoritmos
Notaciones asintoticas y Clases de Eficiencia BasicasΘ grande
Curvas de las funciones c2g(n) ≤ f (n) ≤ c1g(n),
n0 n
f(n)
c1g(n)
c2g(n)
Analisis de Algoritmos
Notaciones Asintoticas y Clases de Eficiencia BasicasΘ grande
Probar que f (n) = 12n(n − 1) es Θ(n2).
f (n) = 12n
2 - 12n ≤ 1
2n2
∀ n ≥ 0
c1 = 12
f (n) = 12n
2 - 12n ≥ 1
2n2 - 1
4n2
f (n) ≥ 14n
2
∀ n ≥ 2
c2 = 14
c1 = 12 , c2 = 1
4 , n0 = 2
Analisis de Algoritmos
Notaciones Asintoticas y Clases de Eficiencia BasicasRegla del maximo
Regla del maximo: Sean f, g: N → R dos funciones arbitrarias delos numeros naturales en los reales.
La regla del maximo dice que si T(n) = t1(n) + t2(n), siendo t1 =O(f(n)) y
t2(n) = O(g(n)),T (n) = O(f (n) + g(n)) = O(max(f (n), g(n)))
Por ejemplo: O(n2 + n3 + nlogn) = O(max(n2, n3, nlogn)) =O(n3)
Analisis de Algoritmos
Notaciones Asintoticas y Clases de Eficiencia BasicasAlgunas propiedades de O
Sean f1(n), f2(n), g1(n) y g2(n) funciones positivas de N → R
1 Si f1(n) = O(g1(n)) y g1(n) = O(g2(n)), entoncesf1(n) = O(g2(n))
2 Si f1(n) = O(g1(n)) y f2(n) = O(g2(n)), entoncesf1(n)f2(n) = O(g1(n)g2(n))
3 f2(n)O(g1(n)) = O(f2(n)g1(n))
4 Si f1(n) = O(g1(n)) y f2(n) = O(g2(n)), entoncesf1(n) + f2(n) = O(g1(n) + g2(n))
5 Si c 6= 0, c un real entonces O(g1(n)) = O(cg1(n))
6 Si f1(n) = O(g1(n)), entonces cf1(n) = O(g1(n)), con c unnumero real
Analisis de Algoritmos
Notaciones Asintoticas y Clases de Eficiencia BasicasOrdenes de magnitud mas comunes (en orden creciente)
Notacion Descripcion
O(1) orden constante
O(log2 log2 n) orden sublogarıtmico
O(log2 n) orden logarıtmico
O(√n) orden sublineal
O(n) orden lineal
O(n log2 n) orden lineal logarıtmico
O(n2) orden cuadratico
O(n3) orden cubico
O(cn), n > 1 y c una cte orden exponencial
O(n!) orden factorial
. . . . . .
Analisis de Algoritmos
Notaciones Asintoticas y Clases de Eficiencia Basicaso chica y ω (omega chica)
Definicion: una funcion f (n) es o(g(n)) (o chica de g(n)), si:
f (n) < cg(n); [f (n) ≺ g(n)], f (n) es menor estricto de g(n).
Definicion: una funcion f (n) es ω(g(n)) (omega chica de g(n)), si:
f (n) > cg(n); [f (n) ≻ g(n)], f (n) es mayor estricto de g(n).
Analisis de Algoritmos
Notaciones Asintoticas y Clases de Eficiencia BasicasUsando lımite para comparar ordenes de crecimiento
¿Como comparar el orden de crecimiento entre dos funciones?
Calculando el lımite de la razon de ambas funciones. Sean f, g: N→ R, entonces podemos distinguir tres casos importantes:
Regla de L’Hopital:f (n)
g(n)= lim
n→∞
f ′(n)
g ′(n)
(1) limn→∞
f (n)
g(n)= 0 ⇒ f(n) = o(g(n)), y f (n) /∈ Θ(g(n)).
(2) limn→∞
f (n)
g(n)= ∞ ⇒ f(n) = ω(g(n)), y f (n) /∈ Θ(g(n)).
(3) limn→∞
f (n)
g(n)= c, donde c ∈ R ⇒ f(n) = Θ(g(n))
Analisis de Algoritmos
Notaciones Asintoticas y Clases de Eficiencia BasicasUsando lımite para comparar ordenes de crecimiento
Ejercicios. Comparar los ordenes de crecimiento de las siguientesfunciones:
(1) f (n) = 12n(n − 1), g(n) = n2
(2) f (n) = log2 n, g(n) =√n
(3) f (n) = n!, g(n) = 2n
De acuerdo con la formula de Stirling: n! =√2πn ( ne )
n
Analisis de Algoritmos
Algoritmos no recursivosBusqueda del mayor elemento de una lista
Ejemplo: busqueda del mayor elemento en una lista de tamano n.
Algorithm 7 maxElement(int A[], int n)
1: Input: A, arreglo de tamano n; n, tamano del arreglo A.2: Output: retorna el maximo valor en A.3: int maxval = A[0];4: for ( i = 1; i < n; i++ ) do5: if ( A[i] > maxval ) then6: maxval = A[i];7: end if8: end for9: return maxval;
Analisis de Algoritmos
Busqueda del mayor elemento de una listaAnalisis previo
Tamano de la entrada: n.
¿Necesita el algoritmo de espacio de almacenamientoadicional? ¡NO!
Operacion basica: la comparacion.
Se debe notar que el numero de comparaciones es igual altamano del arreglo menos 1.
No existe necesidad de distinguir entre el peor, mejor y casopromedio.
Analisis de Algoritmos
Busqueda del mayor elemento de una listaAnalisis matematico
Sea T(n) el numero de veces que se ejecuta la comparacion.
T(n) =
n−1∑
i=1
1 = n − 1 = Θ(n).
Demostracion:
limn→∞
n − 1
n= lim
n→∞n(1− 1
n )
n= lim
n→∞(1− 0
1
n) = 1
Como 1 ∈ R ⇒ f(n) = n-1 ∈ Θ(n)
Analisis de Algoritmos
Problema de la unicidad de los elementosEl algoritmo
Chequear si todos elementos de un arreglo dado de tamano n son
distintos.
Algorithm 8 UniqueElements(int A[], int n)
1: Input: A: arreglo de tamano n.2: Output: retorna true si los elementos son distintos, false en
caso contrario.3: for ( i = 0; i < n-1; i++ ) do4: for ( j = i+1; j < n; j++ ) do5: if ( A[i] == A[j] ) then6: return false;7: end if8: end for9: end for
10: return true;
Analisis de Algoritmos
Problema de la unicidad de los elementosAnalisis previo
Tamano de la entrada: n.
¿Necesita el algoritmo de espacio de almacenamientoadicional? ¡NO!
Operacion basica: la comparacion.
Se debe notar que el numero de comparaciones no solodepende de n sino que tambien si existen elementos iguales enel arreglo, y si existen, en cual posicion, ¿en la segundaposicion encontramos el primer elemento repetido, en lai-esima posicion, en la posicion n?
Realizaremos solo el analisis para el peor caso.
Analisis de Algoritmos
Problema de la unicidad de los elementosAnalisis previo
Por definicion, la entrada para el peor caso es un arreglo parael cual el numero de comparaciones de elementos es Cworst(n)es el mas grande entre todos los arreglos de tamano n.
Si revisamos con atencion el loop mas interno, este nosmuestra que existen dos tipos de entrada para el peor caso:(a) cuando no existen elementos repetidos; (b) cuando sololos dos ultimos elementos son iguales.
Se realiza una comparacion por cada repeticion del loop masinterno, es decir, por cada valor de la variable j entre loslımites i + 1 y n − 1; este se repite por cada valor de i (entre0 y n − 2) del loop mas externo.
Analisis de Algoritmos
Problema de la unicidad de los elementosAnalisis matematico
Revisemos las siguientes reglas de sumatorias:
n∑
i=k
1 = n − k + 1, con k ≤ n.
n∑
i=0
i =
n∑
i=1
i = 1 + 2 + ...+ n = n(n+1)2 ≈ ∈ Θ(n2).
De acuerdo a este analisis previo, tenemos lo siguiente:
T (n) =
n−2∑
i=0
n−1∑
j=i+1
1 =
n−2∑
i=0
[(n − 1)− (i + 1) + 1] =
n−2∑
i=0
(n − 1− i)
Analisis de Algoritmos
Problema de la unicidad de los elementosAnalisis matematico
=
n−2∑
i=0
(n − 1) -
n−2∑
i=0
i
= (n − 1)2 - (n−2)(n−1)2 = n(n−1)
2 ≈ 12n
2
T(n) ∈ O(n2)
Analisis de Algoritmos
Producto de matricesEl algoritmo
Dadas dos matrices A y B de n×n, calcular la complejidad temporal
del producto C = AB.
Algorithm 9 MatrixMultiplication(int A[][], int B[][], int n)
1: Input: A, B: matrices de tamano n×n.2: Output: C: matriz resultante de tamano n×n3: for ( i = 0; i < n; i++ ) do4: for ( j = 0; j < n; j++ ) do5: C [i ][j] = 0.0;6: for ( k = 0; k < n; k++ ) do7: C [i ][j] = C [i ][j] + A[i ][k] ∗ B [k][j];8: end for9: end for
10: end for
Analisis de Algoritmos
Producto de matricesAnalisis previo
Tamano de la entrada: 2n2.
¿Necesita el algoritmo de espacio de almacenamientoadicional? ¡NO!
Operacion basica: el producto (lınea 7).
El conteo de la operacion basica depende solo del tamano delas matrices de entrada, entonces no es necesario analizar porseparado los tres casos.
Existe solo una multiplicacion que se ejecuta en cada iteraciondel loop mas interno (de 0 hasta n-1).
Analisis de Algoritmos
Producto de matricesAnalisis matematico
Para el loop mas interno, el numero de multiplicacionesrealizadas por cada par de valores de las variables i y j :
n−1∑
k=0
1 = n.
El numero total de multiplicaciones T (n) esta dado por lasiguiente expresion:
T(n) =n−1∑
i=0
n−1∑
j=0
n−1∑
k=0
1.
Analisis de Algoritmos
Producto de matricesAnalisis matematico
T(n) =n−1∑
i=0
n−1∑
j=0
n−1∑
k=0
1 =n−1∑
i=0
n−1∑
j=0
n =n−1∑
i=0
n2 = n3
T(n) = n3
∴ T(n) ∈ Θ(n3)
Analisis de Algoritmos
Plan general para analizar algoritmos no recursivos
1 Identificar el parametro que indica el tamano de la entrada.
2 Identificar la operacion basica del algoritmo.
3 Chequear si el numero de veces que se ejecuta la operacionbasica depende solo del tamano de la entrada. Si tambiendepende de alguna propiedad adicional, entonces analizar soloel peor caso.
4 Definir la expresion que refleje la suma del numero de vecesque la operacion basica se ejecuta, a traves de algunasumatoria o una ecuacion de recurrencia.
5 Establecer la complejidad del algoritmo (orden decrecimiento).
Analisis de Algoritmos
Ordenamiento por conteoEl algoritmo
Por cada elemento de una lista contar el numero total de elementos menores y
registrar el resultado en una tabla. Los numeros de esta tabla indicaran las
posiciones de los elementos en la lista ordenada.
Table: Ejemplo de ordenamiento por conteo
A[7] 58 25 74 67 101 89 15count[7] 0 0 0 0 0 0 0
i=0 count[7] 2 0 1 1 1 1 0i=1 count[7] 0 1 2 2 2 2 0i=2 count[7] 0 0 4 2 3 3 0i=3 count[7] 0 0 0 3 4 4 0i=4 count[7] 0 0 0 0 6 4 0i=5 count[7] 0 0 0 0 0 5 0
count[7] 2 1 4 3 6 5 0F[7] count[7] 15 25 58 67 74 89 101
Analisis de Algoritmos
Ordenamiento por conteoEl algoritmo
Algorithm 10 CountingSort(int A[], int n)
1: Input: A: arreglo de elementos entero; n: tamano del arreglo2: Output: arreglo A ordenado ascendentemente.3: for (i=0; i<n; i++) do4: count[i] = 0;5: end for6: for (i=0; i< n-1; i++) do7: for (j=i+1; j<n; j++) do8: if ( A[i] < A[j] ) then9: count[j] = count[j] + 1;10: else11: count[i] = count[i] + 1;12: end if13: end for14: end for15: for (i=0; i<n; i++) do16: F[count[i]] = A[i];17: end for18: return F;
Analisis de Algoritmos
Ordenamiento por conteoAnalisis previo
Tamano de la entrada: n (tamano del arreglo).
¿Necesita el algoritmo de espacio de almacenamientoadicional? Si, arreglos count[] y F.
Operacion basica: la comparacion (lınea 8).
El conteo de la operacion basica depende solo del tamano delarreglo.
Analisis de Algoritmos
Ordenamiento por conteoAnalisis matematico
¿Cual es la eficiencia del algoritmo?. Como en alguno de losejemplos anteriores vistos, este algoritmo deberıa sercuadratico.
T(n) =n−2∑
i=0
n−1∑
j=i+1
1 =n−2∑
i=0
[(n − 1)− (i + 1) + 1] =
n−2∑
i=0
(n − 1− i)
T(n) = n(n−1)2
T(n) = Θ(n2)
Analisis de Algoritmos
Algoritmos recursivos
Ecuaciones de recurrencia
Se pueden considerar como tecnicas avanzadas de conteo
Definition
Una sucesion es una funcion f : N→ A.
Para indicar la imagen en A se emplea an.
Una sucesion se denota por a0, a1, a2, . . .
A los elementos a0, a1, a2, . . . se les llama terminos de lasucesion.
an es el termino general.
Analisis de Algoritmos
Ecuaciones de recurrencia
Example
0, 1, 1, 2, 3, 5, 8, 13, . . .Ecuacion de recurrencia: an = an−1 + an−2, si n > 1.
Una expresion en la que el termino general de la sucesion se escribeen funcion de algunos terminos anteriores se llama ecuacion derecurrencia.
Una ecuacion de recurrencia no determina de manera unica unasucesion. Para ello es necesario conocer algunos terminos de lasucesion, los que se denominan condiciones de borde, defrontera o condiciones iniciales. Por ejemplo, an = an−1 + an−2,si n > 1, a0 = 0 y a1 = 1.
Analisis de Algoritmos
Ecuaciones de recurrencia
Example
an = 2an−1, n ≥ 1,si a0 = 1 tenemos la sucesion: 1, 2, 4, 8, 16 . . .si a0 = 3 tenemos la sucesion: 6, 12, 24, 48 . . .
Para obtener un termino de la sucesion en forma recurrente, esnecesario obtener todos los terminos anteriores. Esto no espractico. Por ejemplo a1000 en la serio de Fibonacci.Interesa obtener una expresion en la que el termino general de lasucesion dependa solo de la posicion que ocupa (n) y no determinos anteriores. A esta expresion se le llama solucion de laecuacion de recurrencia.
Analisis de Algoritmos
Ecuaciones de recurrencia
Example
an = 3an−1, n ≥ 1, a0 = 5a0 = 5a1 = 3a0 = 3.5 = 15a2 = 3a1 = 3.5 = 3.3.5 = 45. . .an = 3n5
En la solucion general hay dependencia solo de n y no de terminosanteriores de la recurrencia.
Analisis de Algoritmos
Calculo del factorial de un numero entero nEl algoritmo
Sea F(n) = n!, para n ≥ 0. Sabemos que:
n! = 1....(n-1)n = (n-1)!n, por definicion 0! = 1.
Podemos calcular F(n) = F(n-1)∗n con el siguiente algoritmo:
Algorithm 11 F(int n)
1: Input: n: entero ≥ 0.2: Output: factorial de n.3: if ( n == 0 ) then4: return 1;5: else6: return F(n-1)∗n;7: end if
Analisis de Algoritmos
Calculo del factorial de un numero entero nAnalisis previo
Tamano de la entrada: numero de bits de n.
¿Necesita el algoritmo de espacio de almacenamientoadicional? ¡SI!, ¿cual? memoria para la pila.
Operacion basica: la multiplicacion.
Para obtener la ecuacion de recurrencia, denotaremos alnumero de multiplicaciones realizadas como T(n).
Analisis de Algoritmos
Calculo del factorial de un numero entero nAnalisis matematico
F(n) es calculada de acuerdo a la formula: F(n) = F(n-1)∗n
El numero de multiplicaciones T(n) para calcular F(n) debesatisfacer la siguiente igualdad:
T(n) = T(n-1) + 1 (n > 0).
T(n-1) representa el calculo de F(n-1) y la constante 1representa el producto entre F(n-1) y n.
Analisis de Algoritmos
Calculo del factorial de un numero entero nAnalisis matematico
La ecuacion de recurrencia necesita una condicion inicial, lacual esta dada por el caso base. Cuando n es igual 0, serealizan cero multiplicaciones (∴ T(0)=0).
De esta forma ahora podemos plantear la ecuacion derecurrencia completa:
T(n) = T(n-1) + 1 (n > 0).
T(0) = 0, condicion inicial.
T(n) nos da el numero de multiplicaciones para calcular F(n).
Para obtener la complejidad temporal del algoritmo,necesitamos resolver la ecuacion de recurrencia. ¿Como sehace esto?
Analisis de Algoritmos
Ejemplos de ecuaciones de recurrencia
T(n) = T(n2 ) + n
T(n) = 2T(n-1) + 1
T(n) = 2T(n2 ) + n
T(n) = T(n-1) + T(n-2), n≥2T(n) = T(
√n) + 1
T(n) = T(⌊n/2⌋) + 1.
T(n) = T(n-1) + 2
T(n) = 64T(n4 ) + n3
T(n) = 3T(n3 ) + log2n
T(n) = T(√n) + log log n
T(n) = T(n4 ) + T(3n4 ) + 2n
T(n) = 3T(n9 ) +√n
T(n) = 7T(n2 ) + n2
T(n) = 64T(n2 ) + 2n
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrencia
(1) Substitucion forward.
(2) Substitucion backward.
(3) Recurrencias telescopicas.
(4) Recurrencias lineales homogeneas.
(5) Cambio de variables.
(6) Teorema maestro.
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaSubstitucion forward: Factorial recursivo
Ecuacion de recurrencia (factorial) T (n) = T (n− 1) + 1, T (0) = 0
Usamos la misma ecuacion para generar los primeros terminospara encontrar algun patron:
Se inicia desde la condicion inicial.
T(0) = 0
T(1) = T(0) + 1 = 0 + 1 = 1
T(2) = T(1) + 1 = 1 + 1 = 2
T(3) = T(2) + 1 = 2 + 1 = 3
...
T(k) = T(k-1) + 1 = k (el patron)
T(n) = n ⇒ Θ(n)
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaSubstitucion backward: Factorial recursivo
Resolveremos esta ecuacion a traves del metodo desubstitucion backward.
T(n) = T(n-1) + 1, substituimos T(n-1) = T(n-2) + 1
= [T(n-2) + 1] + 1 = T(n-2) + 2, substituimos T(n-2) =T(n-3) + 1
= [T(n-3) + 1] + 2 = T(n-3) + 3, substituimos T(n-3) =T(n-4) + 1
= [T(n-4) + 1] + 3 = T(n-4) + 4, etc
Hasta aquı ya hemos hallado el patron: T(n) = T(n-i) + i
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaSubstitucion backward: Factorial recursivo
Tomamos ahora la condicion inicial, T(0) = 0, debemossubstituir i=n en la formula del patron para obtener el ultimoresultado de la substitucion.
T (n) = T (n − 1) + 1 = ... = T (n − i) + i = T (n − n) + n
T (n) = T (0) + n = n
T (n) = Θ(n)
Se debe notar que la version no recursiva de este problematambien es Θ(n).
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaRecurrencias telescopicas
Las recurrencias telescopicas tienen la siguiente forma general:
T (n) = an−1 + T (n − 1)
T (n) = an−1 + an−2 + T (n − 2) (pq T (n − 1) = an−2 +T (n − 2))
T (n) = an−1 + an−2 + an−3 + T (n − 3)
...
T (n) = an−1 + an−2 + an−3 + ... an−k + ...+ a0 + T (0)
T (n) = T (0) +
n−1∑
i=0
ai
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaRecurrencias telescopicas
En general, si:
T (n) = f (n) + T (n − 1)
Tenemos:
T (n) = C +
n∑
i=1
f (i)
Donde la constante C esta dada por la condicion inicial de laecuacion de recurrencia.
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaRecurrencias telescopicas
En el caso del algoritmo recursivo para calcular el factorial den:
T (n) = T (n − 1) + 1, T (0) = 0
T (n) - T (n − 1) = 1
T (n − 1) - T (n − 2) = 1
T (n − 2) - T (n − 3) = 1
...
T (1) - T (0) = 1
Sumando:
(T (n) - T (n − 1)) + (T (n − 1) - T ((n − 2)) + (T (n − 2) -T ((n − 3))
... + (T (2) - T (1)) + (T (1) - T (0)) =
n∑
i=1
1
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaRecurrencias telescopicas
Entonces:
T (n) - T (0) =n
∑
i=1
1
T (n) = T (0) +
n∑
i=1
1
T (n) = 0 +n
∑
i=1
1 = n ⇒ T (n) = n
Resolver:
(a) T (n) = T (n − 1) + 1n , n > 0, T (0) = 1;
(b) T (n) = T (n − 1) + logn, n > 0, T (0) = 1;
(c) T (n) = T (n − 1) + 2n, n > 0, T (0) = 1
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaRecurrencias telescopicas
Sea T (n) = T (n − 1) + 1n , n > 0, T (0) = 1
T (n) - T (n − 1) = 1n
Luego:
(T (n) - T (n − 1)) + (T (n − 1) - T ((n − 2)) + (T (n − 2) -T ((n − 3)) ...
+ (T (2) - T (1)) + (T (1) - T (0)) =
n∑
i=1
1
i
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaRecurrencias telescopicas
= T (n) - T (0) =
n∑
i=1
1
i
= T (n) = T (0) +n
∑
i=1
1
i= 1 + Hn
Donde Hn es el n-esimo numero armonico. :
n∑
i=1
1
i= 1 + 1
2 + 13 + 1
4 + ... + 1n = ln n + O(1)
Entonces:
T (n) = O(ln n)
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaRecurrencias lineales homogeneas
Resolveremos ahora la ecuacion del factorial a traves derecurrencias lineales homogeneas.
Dada la siguiente ecuacion:
akXn+k + ak−1Xn+(k−1) + ... + a1Xn+1 + a0Xn = 0 (∗)
Las soluciones de esta ecuacion son de la forma: Xn = λn
Entonces de la ecuacion (∗) tenemos:
akλn+k + ak−1λn+(k−1) + ... + a1λ
n+1 + a0λn = 0
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaRecurrencias lineales homogeneas
Sacamos factor comun λn:
λn(akλk + ak−1λk−1 + ... + a1λ + a0) = 0
El polinomio: akλk + ak−1λk−1 + ... + a1λ + a0, se
denomina polinomio caracterıstico.
La solucion de la ecuacion consiste en encontrar las raıces delpolinomio caracterıstico:
akλk + ak−1λk−1 + ... + a1λ + a0 = 0
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaRecurrencias lineales homogeneas
Sean λ1, λ2, ..., λk , las raıces del polinomio caracterıstico. Lasolucion general es de la forma:
Xn = C1λn1 + C2λ
n2 + ... + Ckλ
nk
Resolvemos el sistema de ecuaciones lineales:
C1λ01 + C2λ
02 + ... + Ckλ
0k = X0
C1λ11 + C2λ
12 + ... + Ckλ
1k = X1
... ... ...
C1λk−11 + C2λ
k−12 + ... + Ckλ
k−1k = Xk−1
Los λi y los Xi son conocidos
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaRecurrencias lineales homogeneas
Sean λ1 y λ2 las raıces de la ecuacion caracterıstica:
caso 1 Si λ1, λ2 ∈ R y λ1 6= λ2, entonces la solucion general de la ecuacion de larecurrencia se obtiene con la siguiente formula:
T(n) = C1λn1 + C2λ
n2
caso 2 Si λ1 = λ2, la solucion general de la ecuacion de la recurrencia se obtienecon la siguiente formula:
T(n) = C1λn1 + C2nλ
n2
caso 3 Si λ1,2 = u ± iv
T(n) = γn[C1cos(nθ) + C2sin(nθ)], donde γ =√u2 + v2, θ =
arctang( vu),
C1 y C2 son constantes arbitrarias.
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaRecurrencias lineales homogeneas
Sea T(n) = T(n-1) + 1, T(0) = 0, tambien son validas lassiguientes expresiones:
(1) T(n+1) = T(n) + 1, y
(2) T(n+2) = T(n+1) + 1
Restando las ecuaciones: (2) - (1), obtenemos:
T(n+2) - T(n+1) = 1
T(n+1) - T(n) = 1
——————————
T(n+2) - 2T(n+1) + T(n) = 0
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaRecurrencias lineales homogeneas
Obtenemos la ecuacion homogenea:
λn+2 -2λn+1 + λn = 0
Sacando factor comun λn:
λn(λ2 −2λ + 1) = 0
λ2 −2λ + 1 = 0 (resolver la ecuacion caracterıstica)
Corresponde a una ecuacion cuadratica, donde λ = λ1 = λ2
= 1.
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaRecurrencias lineales homogeneas
De aquı obtenemos el siguiente sistema de ecuaciones lineales:
T(n) = C1λn + C2nλ
n, como λ = 1, reemplazamos en laecuacion:
T(n) = C1 + C2n (∗∗)
Sabemos que T(0) = 0, desde aquı obtenemos el siguientesistema de ecuaciones lineales:
T(0) = C1 + C20 = 0 → C1 = 0 (reemplazando en laecuacion (∗∗))T(1) = 1 (porque T(1) = T (0) +1)
T(1) = C1 + C2 = 1, entonces C2 = 1.
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaCambio de variables
En algunos casos la forma telescopica no se observadirectamente. Utilizando cambio de variables podemos hacernotoria la forma anterior y facilitar la resolucion de larecurrencia.
Por ejemplo:
T(n) = 2T(n2 ) + n, T(n) = 1, n ≤ 1
Supongamos que n = 2k , entonces tenemos que:
T(2k) = 2T(2k−1) + 2k
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaCambio de variables
La forma telescopica aun no es notoria, pero veremos quepasa si hacemos:
T(2k) = y(k), tendremos:
y(k) = 2y(k − 1) + 2k / dividiendo por 2k
y(k)2k
= 2y(k−1)2k
+ 2k
2k= y(k−1)
2k2−1 + 1 = y(k−1)2k−1 + 1
y(k)2k
= y(k−1)2k−1 + 1, haciendo r(k) = y(k)
2k, obtenemos:
r(k) = r(k-1) + 1, que es la ecuacion telescopica buscada.
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaCambio de variables
Pero sabemos que:
r(k) = r(k-1) + 1 = r(0) +
k∑
i=1
1
r(k) = 1 + k
Recapitulando. Sabemos que:
T (n) = T(2k) = y(k) = r(k)2k = (1 + k)2k = 2k + k2k
Como n = 2k , entonces k = log2n
T (n) = n + nlog2n ⇒ T (n) = O(nlog2n)
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaCambio de variables
Ejercicios:
T(n) = 2T(n-1) + 1, T(0) = 1
T(n) = 1 + T(√n), T(2) = 1
T(n) =√nT(√n) + cn, T(2) = 1
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaTeorema Maestro: Caso particular
Sea T(n) una funcion eventualmente no decreciente quesatisface la recurrencia:
T(n) = aT(nb ) + f(n), T(1) = c, n = bk , k = 1,2,...
donde a ≥ 1, b ≥ 2, c > 0. Si f (n) ∈ Θ(nd), d ≥ 0, entonces:
T (n) =
Θ(nd) si a < bd
Θ(nd logn) si a = bd
Θ(nlogba) si a > bd
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaTeorema Maestro: ejercicios
(1) T (n) = 1 + T (√n)
(2) T (n) = T (⌊ n2 ⌋) + 1
(3) T (n) = T (n3 ) + 1
(4) T (n) = 2T (n2 ) + 1
(5) T (n) = 64T (n4 ) + n3
(6) T (n) = 32T (n2 ) + n4
(7) T (n) = 2T (n2 ) + cn
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaTeorema Maestro: ejercicios
(1) T (n) = 1 + T (√n)
Usamos substitucion: sea n = 2k , k = log n
T (2k) = 1 + T (2k2 ), de aquı hacemos: y(k) = T (2k)
y(k) = 1 + y(k2 ) = n0 + y(k2 ), a = 1, b = 2, d = 0.
Ahora aplicamos el Teorema Mestro: a = bd = b0 = 1
y(k) = 1 + O(k0logk) = 1 + O(logk) = 1 + O(loglogn)
T (n) = 1 + O(loglogn) ⇒ T (n) = O(loglogn)
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaTeorema Maestro: ejercicios
(2) T (n) = T (⌊ n2 ⌋) + 1
No es necesario usar substitucion, ası que aplicamosdirectamente el Teorema Maestro
a = 1, b = 2, d = 0 ⇒ a = b0
T (n) = 1 + O(n0logn)
T (n) = O(⌊ log n ⌋)
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaTeorema Maestro: ejercicios
(3) T (n) = T (n3 ) + 1
a = 1, b = 3, d = 0, ⇒ a = b0
T (n) = 1 + O(n0logn)
T (n) = O(log3 n)
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaTeorema Maestro: ejercicios
(4) T (n) = 2T (n2 ) + 1
a = 2, b = 2, d = 0, ⇒ a > b0
T (n) = O(nlog22)
T (n) = O(n)
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaTeorema Maestro: ejercicios
(5) T (n) = 64T (n4 ) + n3
a = 64, b = 4, d = 3, ⇒ a = b3
T (n) = O(n3logn)
(6) T (n) = 32T (n2 ) + n4
a = 32, b = 2, d = 4, ⇒ a > b4 ⇒ 32 > 24
T (n) = O(nlog232) = O(nlog225)
T (n) = O(n5)
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaTeorema Maestro: ejercicios
(7) T (n) = 2T (n2 ) + cn (algoritmo Merge Sort)
a = 2, b = 2, d = 1, ⇒ a = b1
T (n) = O(nlogn)
(8) T (n) = T (n2 ) + c (Busqueda binaria)
a = 1, b = 2, d = 0, ⇒ a = b0 ⇒ 1 = 20
T (n) = O(n0log2n)
T (n) = O(logn)
Analisis de Algoritmos
Metodos para resolver ecuaciones de recurrenciaTeorema Maestro: Caso General
Sea T (n) una funcion eventualmente no decreciente que satisface larecurrencia:
T (n) = aT ( nb) + f (n) con a ≥ 1 y b > 1
T (n) =
Θ(nlogb a) si f (n) < O(nc), con c < logb a
Θ(nc logk+1b n) si f (n) = Θ(nc logkb n)
con c = logb a y para algun k ≥ 0
Θ(f (n)) si f (n) = Ω(nc), con c > logb a y∃k < 1, n0 > 0 : a· f ( n
b) ≤ k · f (n), ∀n ≥ n0
Analisis de Algoritmos
Dividir para Reinar
Una de las tecnicas mas importante y mas utilizada para eldiseno de algoritmos.
Consiste en descomponer un problema de tamano n enproblemas mas pequenos, de modo que a partir de la solucionde dichos problemas sea posible construir con facilidad unasolucion al problema original.
Analisis de Algoritmos
Esquema General
1: DR(X )2: if X es suficientemente pequeno then3: Retornar Ad-Hoc(X )4: else5: Descomponer X en subproblemas mas pequenos
X1,X2, . . . ,Xk
6: for i = 1; i ≤ k ; i ++ do7: Yi ← DR(Xi)8: end for9: Combinar las soluciones Yi para obtener una solucion Y
para X
10: return Y
11: end if
Analisis de Algoritmos
Busqueda Binaria
Algoritmo
Suponemos un arreglo A ordenado de menor a mayor.
1: BusquedaBinaria(A, li , ls, x))2: if li > ls then3: return -1 x no se encuentra en el arreglo A4: else5: Sea pivote = li+ls
26: if A[pivote] = x then7: return pivote
8: else if x < A[pivote] then9: return BusquedaBinaria(A, li , pivote − 1, x)
10: else11: return BusquedaBinaria(A, pivote + 1, ls, x)12: end if13: end if
Analisis de Algoritmos
Mınimo y Maximo de un conjunto
Algoritmo
1: MinMax(S)2: if ‖S‖ = 1 then3: return (a, a) S = a 4: else if ‖S‖ = 2 then5: return (min(a, b), max(a, b)) S = a, b6: else7: Dividir S en dos subconjuntos S1, S28: (n1,m1) =MinMax(S1)9: (n2,m2) =MinMax(S2)
10: return (min(n1, n2), max(m1,m2))11: end if
Analisis de Algoritmos
Sort por mezcla
Algoritmo
1: MergeSort(T [1 . . . n])2: if n es suficientemente pequeno then3: Ad-Hoc(T)4: else5: Sea U[1 . . . 1 +
⌊
n2
⌋
],V [1 . . . 1 +⌊
n2
⌋
]
6: U[1 . . .⌊
n2
⌋
]← T [1 . . .⌊
n2
⌋
]
7: V [1 . . .⌊
n2
⌋
]← T [1 +⌊
n2
⌋
. . . n]
8: MergeSort(U[1 . . .⌊
n2
⌋
])
9: MergeSort(V [1 . . .⌊
n2
⌋
])10: Merge(U,V ,T )11: end if
Analisis de Algoritmos
Ejemplos
Sort por Mezcla (continuacion)
1: Merge(U[1 . . .m+ 1],V [1 . . . n+ 1],T [1 . . . n+m]) U[m+ 1]y V [n+ 1] se usan como centinelas para facilitar algoritmo demezcla
2: i ← j ← 13: U[m + 1]← V [n+ 1]←∞4: for k ← 1 hasta m + n do5: if U[i ] < V [j] then6: T [k]← U[i ]7: i ← i + 18: else9: T [k]← V [j]
10: j ← j + 111: end if12: end for
Analisis de Algoritmos
Multiplicacion de enteros grandes
Sean u y v dos numero enteros de n bits cada uno.u = a2n/2 + b y v = c2n/2 + d
uv = (a2n/2 + b)(c2n/2 + d) = ac2n + (ad + bc)2n/2 + bd
ac , ad , bc y bd se multiplican recursivamente.
T (n) = 4T (n/2) + cn,T (1) = 1
El termino cn incluye dos desplazamientos (las multiplicaciones por2n y 2n/2) y las 3 sumas de a lo mas 2n bits. Usando Teoremamaestro: a = 4, b = 2, d = 1 y por lo tanto T (n) = O(n2). Esposible expresar ad + bc como (a − b)(d − c) + ac + bd . Esposible escribir
uv = ac2n + ((a − b)(d − c) + ac + bd)2n/2 + bd
y ahoraT (n) = 3T (n/2) + bn = O(n1.59)
Analisis de Algoritmos
Multiplicacion de enteros grandes
1: Mult(X ,Y , n) X e Y enteros con signo ≤ 2n. n potencia de 22: s contiene el signo de XY 3: m1,m2,m3 contiene los 3 productos 4: A,B,C ,D contiene las mitades izquierda derecha de X e Y 5: s = Sign(X ) ∗ Sign(Y )6: X = abs(X )7: Y = abs(Y )8: if n = 1 then9: if X = 1 and Y = 1 then10: return s11: else12: return 013: end if14: else15: A = n
2bits izquierdo de X
16: B = n2bits derechos de X
17: C = n2bits izquierdo de Y
18: D = n2bits derechos de Y
19: m1 = Mult(A,C , n2)
20: m2 = Mult(A− B,D − C , n2)
21: m3 = Mult(B,D, n2)
22: return (s ∗ (m1 ∗ 2n + (m1 +m2 +m3) ∗ 2 n2 +m3))
23: end if
Analisis de Algoritmos
QuickSort
Procedimiento QuickSort
1: quicksort(T [i . . . j]) Ordena elmentos del arreglo T [i . . . j] demenor a mayor
2: if j − i es suficientemente pequeno then3: InsertSort(T [i . . . j])4: else5: l =pivote(T [i . . . j])6: quicksort(T [i . . . l − 1])7: quicksort(T [l + 1 . . . j])8: end if
Analisis de Algoritmos
quickSort/Particion del arreglo (pivote)
Example
3 1 4 1 5 9 2 6 5 3 5 8 9El arreglo se particiona tomando p = 33 1 4 1 5 9 2 6 5 3 5 8 9
Se busca el primer elemento mayor que el pivote y el ultimo no mayor que elpivote
3 1 4 1 5 9 2 6 5 3 5 8 9Se intercambian los elementos3 1 3 1 5 9 2 6 5 4 5 8 9
Se vuelve a explorar3 1 3 1 5 9 2 6 5 4 5 8 9
Se intercambian
3 1 3 1 2 9 5 6 5 4 5 8 9Se explora (los ındices se cruzan)
3 1 3 1 2 9 5 6 5 4 5 8 9Se intercambia el pivote con el elemento superrayado
2 1 3 1 3 9 5 6 5 4 5 8 9
Analisis de Algoritmos
QuickSort
Procedimiento pivote (particion)
1: Pivote(T [i . . . j ]) Intercambia los elementos del arreglo T [i . . . j ] y retorna unvalor l tal que, i ≤ l ≤ j ,T [k] ≤ p ∀i ≤ k < l ,T [l ] = p y T [k] > p ∀l < k ≤ j , yp es el valor inicial de T [i ]
2: p ← T [i ]; k ← i ; l ← j + 13: repeat4: k ← k + 15: until T [k] > p or k ≥ j6: repeat7: l ← l − 18: until T [k] ≤ p9: while k < l do10: Intercambiar(T [k],T [l ])11: repeat12: k ← k + 113: until T [k] > p14: repeat15: l ← l − 116: until T [k] ≤ p17: end while18: Intercambiar(T [i ],T [l ])19: return l
Analisis de Algoritmos
QuickSortAnalisis QuickSort
Peor caso
Operacion relevante: ComparacionesSea r el tamano de uno de los subarreglos generados por elprocedimiento pivote (particion). El costo del algoritmo es:t(n) = t(r) + t(n − r) + n, es decir, el costo de ordenar un arreglode tamano r , mas el costo de ordenar un arreglo de tamano n− r ymas las comparaciones necesarias para particionar el arreglo. Elpeor caso ocurre cuando el tamano de r es cero, y en este casot(n) = t(n − 1) + n, t(1) = 0. El argumento n − 1 se explica porque la posicion del pivote es conocida (ver lıneas 6 y 7 delalgoritmo quicksort). Por lo tanto (usar telescopica)
t(n) = O(n2)
Analisis de Algoritmos
QuickSortAnalisis QuickSort
Mejor caso
El mejor caso sucede cuando r = n/2 (los dos subarreglos son delmismo tamano aproximadamente) y por lo tantot(n) = 2t(n/2) + n = O(n log2 n)
Analisis de Algoritmos
QuickSortAnalisis QuickSort
Caso Promedio
Supuesto: Sea S1 uno de los subarreglos. Asumimos que cada uno de lostamanos (0, 1, . . . n − 1) son igualmente probables. Es decir, que S1 puede serde cualquiera de estos tamanos.Con este supuesto el valor promedio de t(|S1|) es 1
n
∑n−1j=0 t(j). Dado que
tenemos que resolver dos subproblemas (ordenar dos subarreglos) en promediodel mismo tamano.
t(n) =2
n
n−1∑
j=0
t(j) + cn (1)
nt(n) = 2n−1∑
j=0
t(j) + cn2 (2)
(n − 1)t(n − 1) = 2n−2∑
j=0
t(j) + c(n − 1)2 (3)
Analisis de Algoritmos
QuickSortAnalisis QuickSort
Caso Promedio (contnuacion)
restando (2) - (3) tenemos:
nt(n)− (n − 1)t(n − 1) = 2t(n − 1) + 2cn − c (4)
nt(n) = (n + 1)t(n − 1) + 2cn (5) div . por n(n + 1)
t(n)
n + 1=
t(n − 1)
n+
2c
n + 1(6)
t(n − 1)
n=
t(n − 2)
n − 1+
2c
n(7)
t(n − 2)
n − 1=
t(n − 3)
n − 2+
2c
n − 1(8)
. . .
t(2)
3=
t(1)
2+
2c
3(9)
Analisis de Algoritmos
QuickSortAnalisis QuickSort
Caso Promedio (contnuacion)
Sumando todas las ecuaciones de (6) a (9)
t(n)
n + 1=
t(1)
2+ 2c
n+1∑
i=3
1
i
La sumatoria es loge(n + 1) + γ − 32, con γ ≈ 0.577. De esta forma
t(n)
n + 1= O(log2 n)
, es decir,t(n) = O(n log2 n)
Analisis de Algoritmos
Programacion Dinamica
• Al igual que la tecnica Dividir para Reinar, la ProgramacionDinamica (PD) resuelve problemas mediante la combinacionde las soluciones de subproblemas.
• “Programacion” se refiere en este contexto a un metodotabular y no a escribir codigo computacional
• La PD es una tecnica que se aplica especialmente en aquellosproblemas donde los subproblemas se solapan, es decir, lossubproblemas no son independientes.
• Un algoritmo de PD resuelve cada uno de los subproblemamas pequenos solo una vez y registra su respuesta en unatabla, evitando de esta forma repetir calculos.
Analisis de Algoritmos
Tecnicas de Diseno de AlgoritmosProgramacion Dinamica
• Donde tiene mayor aplicacion la Programacion Dinamica es enla resolucion de problemas de optimizacion.
• Para que un problema pueda ser abordado por esta tecnica hade cumplir dos condiciones:
La solucion al problema debe ser alcanzada a traves de unasecuencia de decisiones, una en cada etapa.
Dicha secuencia de decisiones ha de cumplir el principio deoptimo.
Analisis de Algoritmos
Tecnicas de Diseno de AlgoritmosProgramacion Dinamica
• El diseno de un algoritmo de la PD consta de los siguientespasos:
(1) Planteamiento de la solucion como una sucesion de decisionesy verificacion de que esta cumple el principio de optimo.
(2) Definicion recursiva de la solucion.
(3) Calculo del valor de la solucion optima mediante una tabla,donde se almacenan soluciones a problemas parciales parareutilizar los calculos.
(4) Construccion de la solucion optima haciendo uso de lainformacion contenida en la tabla.
Analisis de Algoritmos
Serie de Fibonacci
f (n) =
f (n − 1) + f (n − 2) si n > 2n si n ≤ 2
F(5)
F(3)
F(1)
F(0)
F(1) F(0)
F(3)
F(0)F(1)
F(2)
F(1)
F(4)
F(2)
F(1)F(2)
+
+++
+
++
Complejidad: f (n) = 1√5
(
1+√5
2
)n− 1√
5
(
1−√5
2
)n
Analisis de Algoritmos
Tecnicas de Diseno de AlgoritmosSerie Fibonacci: algoritmo no recursivo
Algorithm 12 Fibonacci(n)
1: Input: n: numero entero.2: Output: el n-esimo termino de la serie de Fibonacci.3: vector fibonacci[0] = 0;4: vector fibonacci[1] = 1;5: for (i = 2; i < n; i ++) do6: vector fibonacci[i] = vector fibonacci[i-1] + vector fibonacci[i-2];7: end for
• Se construye una tabla (vector) para guardar los calculosrealizados sin que estos se repitan y despues reutilizarlos.
• Es facil ver que este algoritmo es O(n).
• Su complejidad espacial tambien es O(n).
Analisis de Algoritmos
Tecnicas de Diseno de AlgoritmosSerie Fibonacci: segundo algoritmo no recursivo
• Existe otra forma de mejorar este algoritmo debido a que soloes necesario almacenar los dos ultimos valores para calcular elnuevo termino.
• Esto permite eliminar la tabla completa y usar solo dosvariables.
• Es facil ver que este algoritmo tambien es O(n).
• Tambien podemos ver que su complejidad espacial es O(1).
• Este algoritmo es el mas eficiente de los tres.
Analisis de Algoritmos
Tecnicas de Diseno de AlgoritmosSerie Fibonacci: segundo algoritmo no recursivo
Algorithm 13 Fibonacci(n)
1: Input: n: numero entero.2: Output: el n-esimo termino de la serie de Fibonacci.3: fn 2 = 0;4: fn 1 = 1;5: if ( n == 0 ) then6: return fn 2;7: end if8: if ( n == 1 ) then9: return fn 1;10: end if11: for ( i=2; i ≤ n; i++ ) do12: fn = fn 1 + fn 2;13: aux = fn 1;14: fn 1 = fn;15: fn 2 = aux;16: end for17: return fn;
Analisis de Algoritmos
Tecnicas de Diseno de Algoritmos
• En general, los algoritmos obtenidos mediante la aplicacion deesta tecnica consiguen tener complejidades (espacio y tiempo)bastante razonables.
• Se debe evitar complejidades espaciales demasiado elevadascuando se trata de obtener complejidades temporales de ordenpolinomico.
Analisis de Algoritmos
Tecnicas de Diseno de AlgoritmosCalculo de los Coeficientes Binomiales
• Para este problema se requiere de una tabla bidimensional.
• El algoritmo recursivo que calcula estos coeficientes es decomplejidad exponencial debido a que tambien hay repeticionde calculos.
(
n
m
)
=
1 si m = 0 o m = n
(
n − 1
m − 1
)
+
(
n− 1
m
)
si 0 < m < n
0 en caso contrario
Analisis de Algoritmos
Tecnicas de Diseno de AlgoritmosCalculo de los Coeficientes Binomiales
Algorithm 14 C(int n, int m)
1: Input: n, m: numeros enteros.2: Output: n sobre m.3: if ( m = 0||m = n) then4: return 1;5: else6: return C(n − 1,m − 1) + C(n − 1,m);7: end if
• Sea T (k) el tiempo necesario en el peor caso para calcularC (n,m), donde k = n+m. La ecuacion de recurrencia para elalgoritmo recursivo es:
T (k) = T (k − 1) + T (k − 2) ; k > 1, T (1) = 0;
Analisis de Algoritmos
Tecnicas de Diseno de AlgoritmosCalculo de los Coeficientes Binomiales
T (k) = T (k − 1) + T (k − 2) ; k > 1, T (1) = 0;
• Esta ecuacion de recurrencia es similar a la de la serie deFibonacci, por lo tanto este algoritmo tambien tienecomplejidad exponencial.
Analisis de Algoritmos
Tecnicas de Diseno de AlgoritmosCalculo de los Coeficientes Binomiales: solucion no recursiva
1
1
1
1 1
4
3
12
(4,0) +
(3,0) + (3,1)
(2,0) + (2,1)
(1,0) + (1,1)
(6,2)
(4,1)
(5,1) + (5,2)
(4,1) + (4,2)
(3,1) (3,2)+
(2,1) + (2,2)
Analisis de Algoritmos
Tecnicas de Diseno de AlgoritmosCalculo de los Coeficientes Binomiales: solucion no recursiva
.
.
.
1
1 1
1 2 1
1 3 3 1
... ... ... ... ...
... ... ... ... ...
n−1
n
0
C(n−1,m−1) + C(n−1,m)
C(n,m)
1
3
2
0 1 2 3 ... m−1 m
Analisis de Algoritmos
Tecnicas de Diseno de AlgoritmosCalculo de los Coeficientes Binomiales: solucion no recursiva
Algorithm 15 BC(int n, int m)
1: Input: n, m: numeros enteros.2: Output: C[n+1, m+1].3: for ( i=0; i ≤ n; i++) do4: C[i,0] = 1;5: end for6: for ( i=1; i ≤ n; i++) do7: C[i,1] = i;8: end for9: for ( i=2; i ≤ m; i++) do10: C[i,i] = 1;11: end for12: for ( i=3; i ≤ n; i++) do13: for ( j=2; j ≤ i-1; j++) do14: if ( j ≤ m ) then15: C[i,j] = C[i-1,j-1] + C[i-1,j];16: end if17: end for18: end for19: return C[n, m];
Analisis de Algoritmos
Tecnicas de Diseno de AlgoritmosCalculo de los Coeficientes Binomiales: solucion no recursiva
T (n) =
n−1∑
i=3
i−2∑
j=2
1 =
n−1∑
i=3
[(i − 2)− 2 + 1] =
n−1∑
i=3
(i − 3)
T (n) =n−1∑
i=3
i −n−1∑
i=3
3 =n−3∑
i=1
i −n−3∑
i=1
3
=(n − 3)(n − 3 + 1)
2− 3(n − 3)
T (n) =n2 − 11n + 24
2
T (n) = O(n2)
Analisis de Algoritmos
Subsecuencia Comun mas Larga
Definition
Dada una secuencia X = x1x2¸ . . . xn, decimos queZ = z1z2 . . . zk, con k ≤ m, es una subsecuencia de X si existeuna secuencia creciente de ındices i1i2 . . . ik de X tal que paratodo j = 1, 2, . . . , k se tiene que xij = zj
Example
Z = ACA es una subsecuencia de X = AGCAT, considerandola secuencia de ındices de X 1, 3, 4
Analisis de Algoritmos
Subsecuencia Comun mas Larga
Dadas dos secuencias X e Y , decimos que Z es una subsecuenciacomun de X e Y si es subsecuencia de X y subsecuencia de Y .Deseamos determinar la longitud de la subsecuencia comun maslarga (L) de X e Y . Ejemplo: X = AGCAT e Y = GAC , entoncesL(5, 3) = 2
L(i , j) =
0 si i = 0 o j = 0
L(i − 1, j − 1) + 1 si i 6= 0, j 6= 0 y xi = yj
maxL(i , j − 1), L(i − 1, j) i 6= 0, j 6= 0 y xi 6= yj
Analisis de Algoritmos
Tecnicas de Diseno de AlgoritmosCalculo L solucion recursiva
Algorithm 16
1: L(X , i ,Y , j)2: if i = 0 or j = 0 then3: return 04: else if Xi = Yj then5: return L(X , i − 1,Y , j − 1) +16: else7: return maxL(X , i ,Y , j − 1), L(X , i − 1,Y , j)8: end if
Complejidad
Sea k = n +m con n = |X | y m = |Y | y t(k) el costo de resolverL(n,m).
t(k) = 2t(k − 1) + c ,T (0) = 0
t(k) = O(2k) = O(2n+m)
Analisis de Algoritmos
Calculo L solucion iterativa
Tabla
0 A G C A T
0 0 0 0 0 0 0
G 0 ←↑0 տ1 1 1 1
A 0 1 1 1 2 2
C 0 1 1 2 2 2
Analisis de Algoritmos
Calculo de L solucion iterativa
Algorithm 17
1: L(X , n,Y ,m)2: Sea T [m + 1][n + 1]3: for i = 0 to m do4: T [i ][0] = 05: end for6: for i = 0 to n do7: T [0][i ] = 08: end for9: for i = 1 to m + 1 do10: for j = 1 to n + 1 do11: if Xi = Yj then12: T [i , j ] = T [i − 1, j − 1] + 113: else14: T [i , j ] = max(T [i , j − 1],T [i − 1, j − 1])15: end if16: end for17: end for
Analisis de Algoritmos
Calculo de L solucion iterativa
Complejidad
Almacenamiento: O(n ·m)
Tiempo: O(n ·m)
Analisis de Algoritmos
Multiplicacion encadenada de matrices
Definition
Dadas dos matrices Ap×q y Bq×r el producto de AB se definecomo sigue
Cp×r = AB =n
∑
k=1
aikbkj , 1 ≤ i ≤ p, 1 ≤ j ≤ r
1: for i = 1; i ≤ p; i ++ do2: for j = 1; j ≤ r ; j ++ do3: C [i , j ] = 04: for k = 1; k ≤ q; k ++ do5: C [i , j ] = C [i , j ] + A[i , k] ∗ B[k, j ]6: end for7: end for8: end for
Se necesitan pqr multiplicaciones de escalares
Analisis de Algoritmos
Multiplicacion encadenada de matrices
Supongamos ahora que se desea calcular el producto de mas dedos matrices. El producto matricial es asociativo, por lo tanto esposible calcular el producto matricial
M = M1M2 . . .Mn
de muchas maneras diferentes, todas las cuales daran la mismarespuesta:
M = (. . . ((M1M2))M3) . . .Mn)
M = (M1(M2(M3 . . . (Mn−1Mn) . . .)))
M = (. . . ((M1M2)(M3M4)) . . .)
y ası sucesivamente. Recordar que la multiplicacion de matrices noes conmutativa por lo que no es posible modificar el orden lasmultiplicaciones matriciales.
Analisis de Algoritmos
Multiplicacion encadenada de matrices
Example
Sean A13×5,B5×89,C89×3 y D3×34 y queremos calcular ABCD.Una asociacion es M = ((AB)C)D , y cuesta (en multiplicaciones de escalares).
AB 5.785 multiplicaciones(AB)C 3.471 multiplicaciones
((AB)C)D 1.326 multiplicaciones
Total 10.582 multiplicaciones
Hay 5 formas diferente de calcular ABCD .Forma Multiplicaciones
((AB)C)D 10.582(AB)(CD) 54.201(A(BC))D 2.856A((BC)D) 4.055A(B(CD)) 26.418
Analisis de Algoritmos
Multiplicacion encadenada de matrices
Algoritmo sencillo
1 Encontrar todas las formas posibles de asociacion
2 Contar el numero de multiplicaciones de escalares
3 Y quedarse con la de menor numero de multiplicaciones
Costo
Sea T (n) el numero de formas diferentes de poner parentesis en un productode n matrices. Supongamos que decidimos hacer el primer corte entre lasmatrices i-esima e (i + 1)-esima del producto en la forma siguiente:
(M1M2 . . .Mi )(Mi+1Mi+2 . . .Mn)
Ahora hay T (i) formas de poner los parentesis en el termino del lado izquierdo
y T (n − i) en el termino del lado derecho. Cualquier forma del primer grupo se
puede combinar con cualquier forma del segundo grupo. De esta forma y para
este valor concreto de i hay T (i)T (n − i) formas de poner los parentesis.
Analisis de Algoritmos
Multiplicacion encadenada de matrices
Costo (continuacion)
Dado que i puede tomar cualquier valor entre 1 y n − 1 obtenemos finalmentela recurrencia siguiente:
T (n) =
n−1∑
i=1
T (i)T (n − i)
La tabla siguiente muestra algunos valores de T (n)a
n 1 2 3 4 5 10 15
T (n) 1 1 2 5 14 4.862 2.274.440
T (n) = Ω( 4n
n2) y se necesita tiempo Ω(n) para calcular la cantidad de
multiplicaciones escalares. Por lo tanto se requiere tiempo Ω( 4n
n) lo que
evidentemente no es practico.
aLos valores de T (n) se llaman numeros de Catalan
Analisis de Algoritmos
Multiplicacion encadenada de matrices
Solucion con PD
Asumiendo que la mejor forma de hacer la multiplicacion se lograhaciendo el primer corte entre las matrices i -esima e (i + 1)-esima.Entonces los subpro-ductos M1M2 . . .Mi y Mi+1Mi+2 . . .Mn tambien deben ser optimos.mij , 1 ≤ i ≤ j ≤ n almacena la solucion optima, es decir, cantidad de mul-
tiplicaciones de escalares para MiMi+1 . . .Mj . m1n es lasolucion del problema original.
d [0..n] Vector para almacenar las dimensiones de las matrices.Las dimensiones de la matriz Mi se encuentran en d [i−1]y d [i ]. El numero de multipplicaciones de escalares almultiplicar MiMi+1 se obtiene directamente de d [i−1]×d [i ]× d [i + 1]
s La diagonal s = j − i contiene los elementos de mij .s = 0 diagonal principal, s = 1 contiene los elementosde mi,i+1, etc.
Analisis de Algoritmos
Multiplicacion encadenada de matrices
Solucion con PD (continuacion)
1 s = 0 : mi ,i = 0, i = 1, 2, . . . n
2 s = 1 : mi ,i+1 = di−1 × di × di+1, i = 1, 2, . . . n − 1
3 1 < s < n : mi ,i+s =mini≤k<i+s(mi ,k +mk+1,i+s + di−1 × dk × di+s)i = 1, 2, . . . n − s
Analisis de Algoritmos
Multiplicacion encadenada de matrices
Example
Sean A13×5,B5×89,C89×3 y D3×34 y queremos calcular ABCD.D = [13, 5, 89, 3, 34]
j = 1 2 3 4
i = 1 0 5875 1530 2856 s = 3
2 0 1335 1845 s = 2
3 0 9078 s = 1
4 0 s = 0s = 1 s = 2 s = 3
m34 = 89×3×34 = 9078 m13 = min(m11 + m23 + 13 ×5×3,m12+m33+13×89×3) =min(1530, 92656) = 1530
m14 = min(
k=1︷ ︸︸ ︷
m11 + m24 + 13 × 5 × 34,m12+m34+13×89×34, m13+m44+13×3×34) =min(4055, 54201, 2856) = 2856
m23 = 5 × 89 × 3 = 1335 m24 = min(m22+m34+5×89×34,m23 +m44 + 5× 5× 34) =min(24208, 1845) = 1845
m12 = 13×5×89 = 5875
Analisis de Algoritmos
Multiplicacion encadenada de matrices
Complejidad
Temporal:Por cada s existen n − s elementos a ser calculado en la diagonals; por cada una de estas se debe elegir entre s posibilidades dadopor los diferentes valores de k .t(n) =
∑n−1s=1 (n − s)s = n
∑n−1s=1 s −
∑n−1s=1 s
2
= n2(n − 1)/2 − n(n − 1)(2n − 1)/6t(n) = (n3 − n)/6 = Θ(n3)Almacenamiento:matriz m ( O(n2)) mas el arreglo D (O(n)). Es decir O(n2)
Analisis de Algoritmos
El problema de dar cambio
El problema
Este es un problema tıpico cuando alguien realiza una compra y eldependiente necesita darle el cambio, pues la cantidad que haentregado el cliente es mayor que la compra o cuando el cajero deun banco necesita pagar un cheque. Por ejemplo, supongamos quen = 15.785 es la cantidad a enterar (devolver o pagar) y quetenemos las siguientes denominaciones20.000, 10.000, 5.000, 2.000, 1.000, 500, 100, 50, 10, 5.Suponemos que las denominaciones son monedas (no hay billetes)y que tenemos una cantidad infinita de cada una de ellas. Debemoscompletar la cantidad n minimizando la cantidad de monedas.
Analisis de Algoritmos
El problema de dar cambio
1: ConjuntoMonedas DevolverCambio(n) Da el cambio de n unidadesutilizando el menor numero posible de monedas. C especifica un arreglocon las denominaciones
2: C = 20000, 10000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 13: S ← ∅ Conjunto que contendra la solucion4: s ← 0 s es la suma de los elementos de S5: while s 6= n do6: x ← el mayor elemento de C tal que s + x ≤ n
7: if No existe ese elemento then8: return “No existe solucion”9: end if
10: S ← S ∪ una moneda de valor x11: s ← s + x
12: end while
13: return S
Analisis de Algoritmos
Caracterısticas Generales
Problema de optimizacion (mınima cantidad de monedas)
Se dispone de un conjunto de candidatos(Monedas)
Conforme avanza el algoritmo se mantienen dos conjuntos
Conjunto con candidatos considerados y seleccionadosConjunto con candidatos considerados y rechazados
Se consideran 4 funciones
Verifica si un conjunto de candidatos es solucion (ignorando sies optima). ¿Suman las monedas seleccionadas la cantidadque hay que pagar?Verifica si una solucion es factible. s + x ≤ n
Funcion de seleccion. Elige el candidato mas prometedor de loscandidatos que no han sido seleccionados o rechazados.Funcion objetivo. Da el valor de la solucion. Numero demonedas. No aparece explıcitamente en el algoritmo.
La funcion de seleccion suele estar relacionada con la funcion objetivo.
Nunca cambian de opinion.
Analisis de Algoritmos
Esquema general Algoritmos Voraces
1: voraz(Conjunto C) C Conjunto de candidatos2: S ← ∅ Conjunto que contendra la solucion3: while C 6= ∅ and not solucion(S) do4: x ← seleccionar(C)5: C ← C − x6: if factible(S ∪ x) then7: S ← S ∪ x8: end if9: end while
10: if solucion(S) then11: return S
12: else13: return “No hay solucion”
14: end if
Analisis de Algoritmos
El problema de la Mochila
Nos dan n objetos y una mochila. Para i = 1, 2, . . . , n, el objeto i tiene un pesopositivo wi y un valor (economico) vi . La mochila puede llevar un peso que nosobrepase W . El objetivo es llenar la mochila de tal manera que se maximice elvalor de los objetos transportados, respetando la limitacion de capacidadimpuesta. Suponga que es posible romper los objetos en trozos mas pequenosde modo que podemos decidir llevar solo una fraccion xi del objeto i , es decir,0 ≤ xi ≤ 1.
1 Disene un algoritmo voraz para determinar los objetos que es convenientecargar en la mochila
2 Indique por que cree que su algoritmo es voraz ?. ¿ Donde esta lo“voraz” ?
3 Compare su solucion con la entregada por el profesor.
4 Asocie las caracterısticas generales de los algoritmos voraces a lascaracterısticas particulares de este problema. Identifique el conjunto decandidatos y las diferentes funciones.
Analisis de Algoritmos
Solucion problema de la Mochila
La funcion objetivo que queremos optimizar es:
maximizar∑n
i=1 xi vi con la restriccion∑n
i=1 xiwi ≤ W , donde vi > 0,wi > 0 y 0 ≤ xi ≤ 1 para 1 ≤ i ≤ n.
1: Mochila(w [1 . . . n], v [1 . . . n],W )2: Sea x[1 . . . n] x es un vector para almacenar la fraccion de cada objeto
que va en la mochila3: x[i ]← 0 para todo 1 ≤ i ≤ n
4: peso ← 05: while peso < W do6: i ← el mejor objeto restante7: if (peso + w [i ]) ≤W then8: x[i ]← 19: peso ← peso + w [i ]10: else11: x[i ]← (W − peso)/w [i ]12: peso ←W
13: end if14: end while15: return x
Analisis de Algoritmos
Funciones de seleccion para el problema de la mochila
1 El objeto mas valioso (Max vi )
2 El mas liviano (Mın wi )
3 El objeto cuyo valor por unidad de peso sea el mayor (Max viwi)
Ejemplo: n = 5,w = 100w 10 20 30 40 50v 20 30 66 40 60vw
2.0 1.5 2.2 1.0 1.2
Resultados con cada una de las funciones de selecion.Seleccionar: xi Valor
Max vi 0 0 1 0.5 1 146Mın wi 1 1 1 1 0 156Max vi
wi1 1 1 0 0.8 164
Analisis de Algoritmos
Introduccion
Puede aplicarse a muchos problemas (optimizacion)
Problemas para los cuales no se puede construir la solucion talcomo ocurre con la programacion dinamica o algoritmosvoraces. Se deben explorar una a una todas las posiblidadesfactibles.
Diferente a los algoritmos avidos, los algoritmos Bactrackingpueden cambiar una decision.
Exploracion exhaustiva (en profundidad) de un grafo implıcito(espacio de estados)
Exito: Se llega a una hoja (fin, si solo buscamos una solucion,se continuan buscando soluciones si se esta optimizando)Fracaso: El algortimo vuelve atras eliminando los elementosanadidos a la solucion)
Analisis de Algoritmos
El problema de las 8 reinas
1: reinas(k , col , diag45, diag135)2: sol [1 . . . k] es k-prometedor
col = sol [i ]|1 ≤ i ≤ kdiag45 = sol [i ] − i + 1|1 ≤ i ≤ k ydiag135 = sol [i ] + i − 1|1 ≤ i ≤ k
3: if k = 8 then4: Escribir sol Un vector 8-prometedor es una solucion5: else6: for j ← 1 to 8 do7: if j /∈ col y j − k /∈ diag45 y j + k /∈ diag135 then8: sol [k + 1]← j sol [1 . . . k + 1] es (k + 1)-prometedor9: reinas(k + 1, col ∪ j , diag45 ∪ j − k, diag135 ∪ j + k)
10: end if11: end for
12: end if
Llamada: =⇒ reinas(0, ∅, ∅, ∅)
Analisis de Algoritmos
El problema de la mochila
1: mochilaback(i , r) Calcula el valor de la mejor carga que se puedeconstruir empleando elementos de los tipos i a n y cuyo peso total nosobrepase a r . Los arreglos w y v almacenan los pesos y valoresrespectivamente de cada tipo de objeto.
2: b ← 03: se prueban por turno las clases de objetos admisibles4: for k ← i to n do5: if w [k] ≤ r then6: b ← max(b, v [k] +mochilaback(k , r − w [k]))7: end if8: end for
9: return b
Llamada: =⇒ mochilava(1,W )
Analisis de Algoritmos
El caso general
1: vueltaatras(v [1 . . . k])2: v es un vector k-prometedor3: if v es una solucion then4: Escribir v5: else6: for cada vector (k+1)-prometedor w tal que w [1 . . . k] = v [1 . . . k] do7: vueltaatras(w [1 . . . k + 1])8: end for
9: end if
Analisis de Algoritmos
Introduccion
Al igual que Backtracking explora un grafo dirigido implıcito.
Puede aplicarse a problemas de optimizacion
Poda
1 En cada nodo se calcula una cota para los posibles valores quecualquier solucion puede alcanzar mas adelante en el grafo.
2 Si la cota muestra que cualquier solucion debe sernecesariamente peor que la mejor solucion encontrada,entonces se evita explorar esta parte del grafo.
Ramificacion
1 Expansion de los nodos (estrategias)
AnchuraProfundidadMas prometedores (colas de prioridad)
Analisis de Algoritmos
Ramificacion y Poda/Problema de Asignacion
Example
Busqueda exhaustiva: Agente = a, b, c, Actividad = 1, 2, 3,cij costo de que el agente i ejecute la actividad j .
1 2 3
a 4 7 3b 2 6 1c 3 9 4
Problema: Asignar las tareas a los agentes de tal manera deminimizar el costo total de ejecutar las n tareas.Una posible asignacion es a→ 1, b → 2, c → 3,costo = 4 + 6 + 4 = 14; pero la asignacion a→ 3, b → 2, c → 1,costo = 3 + 6 + 3 = 12 es mejor. La mejor asignacion esa→ 2, b → 3, c → 1 y su costo es costo = 7 + 1 + 3 = 11.En general se necesitan considerar n! asignaciones
Analisis de Algoritmos
Ramificacion y Poda/Problema de Asignacion
1 2 3 4
a 11 12 18 40b 14 15 13 22c 11 17 19 23d 17 14 20 28
cota superior: a→ 1, b → 2, c → 3 y d → 4 = 11 + 15 + 19 + 28 = 73. Lasolucion no puede costar mas que 73
cota inferior: Independiente de que agente ejecute la tarea 1, esta costara 11,
la tarea 2 costara 12, la tarea 3 13 y la tarea 4 22, es decir 11+12+13+22=58.
Es decir la solucion se encuentra en el rango [58 . . . 73].
Analisis de Algoritmos
Ramificacion y Poda/Problema de Asignacion(cont.)
rango de la solucion: [58 . . . 73]1 2 3 4
a 11 12 18 40b 14 15 13 22c 11 17 19 23d 17 14 20 28
a 1
a
a
a
2
3
4
60
58
65
78*
= 12+11+13+22
= 11 + 14 +13 + 22
Analisis de Algoritmos
Ramificacion y Poda/Problema de Asignacion (cont.)
rango de la solucion: [58 . . . 73]1 2 3 4
a 11 12 18 40b 14 15 13 22c 11 17 19 23d 17 14 20 28
a 1
a 2, b 1
a
a
a
2
3
4
60
65
78*
a 2, b
a 2, b
3
4
68
59
64
= 14+12+19+23
Analisis de Algoritmos
Ramificacion y Poda/Problema de Asignacion (cont.)
1 2 3 4
a 11 12 18 40b 14 15 13 22c 11 17 19 23d 17 14 20 28
a 1
a 2, b 1
a 2, b 3a
a
a
2
3
4 78*
3, c 1, d 4
3, c 4, d 1
64
65*
a 4
68
64*
*
a
a
a 2, b 4
68
64*
*
a 2, b
a 2, b
1, b 3, c 2, d 4 69*
1, b 3, c 4, d 2 61
59
a
a 1, b 3
1, b
1, b
2
61
60
58
65*
Analisis de Algoritmos
Ramificacion y Poda / Problema de asignacion
Algoritmo (problema de asignacion)
Asignacion(A, n)Sea sol = cotaSuperior(A, n) Cota superior del problemaSea ci la cota inferior de un nodosea P una cola de prioridad con entradas 〈ci, nodo〉 y organizada por el mınimo de ci .ci = cotaInferior(A, n, r) Cota inferior del nodo raız r ( cota inferior del problema)Insertar 〈ci, r〉 en Pwhile P 6= ∅ do
e = EliminarMin(P)if e.ci < sol then
for cada hijo h de e.nodo doci = cotaInferior(A, n, h)if h es un nodo hoja then
if ci < sol thensol = ci
end ifelse
Insertar 〈ci, h〉 en Pend if
end forend if
end while
return sol