algoritmica parte ii: creación de algoritmos 2... · 2019-10-01 · - 1 escuela tÉcnica superior...
Post on 06-Jul-2020
0 Views
Preview:
TRANSCRIPT
PARTE II: Creación de algoritmos
Eugenio Fco. Sánchez Úbeda
Cristina Puente ÁguedaUniversidad Pontificia ComillasDepartamento de Sistemas Informáticos
ALGORITMICA
- 1ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Estructuras de datos (I)
• No es el tema central de esta asignatura
– “formas de organizar los datos para procesarlos con un algoritmo”
• Estructuras básicas necesarias:
– Unidimensionales: arrays, listas enlazadas, pilas y colas
– Bidimensionales: árboles
+ operaciones básicas genéricas para manipular estas estructuras
- 2ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Estructuras de datos (II)
• Arrays
– Estructura básica fundamental
– Acceso directo (rápido)
– “Primitiva” en casi todos los lenguajes de programación
– Tradicionalmente estática (no se puede cambiar su tamaño de forma
dinámica, o es muy costoso)
– Array de registros
• Cada elemento del array es un registro con varios campos
A[1] A[N]A[k]
clave
vA:
1 size(vA)
vA(k) ó vA[k]
- 3ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Estructuras de datos (III)
• Listas enlazadas
– “Conjunto de elementos organizados secuencialmente”
– Dinámica (añadir y eliminar elementos sin problemas)
– Acceso secuencial (lento)
– No suele ser una “Primitiva” en casi ningún lenguaje de programación
– Elemento básico:
– Tipos de listas:
• Simples, doblemente enlazadas, circulares, ordenadas, ...
– Operaciones básicas:
• Insertar, sacar, buscar, borrar
cabeza(L) L
e• next(e) ó e.next
• prev(e) ó e.prev (puede no existir)
• valor(e) ó e.valor
- 4ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Estructuras de datos (IV)
• Listas enlazadas (ejemplo inserción)
5
715nil(L)
x 5
715nil(L)
inicialmente:
Resultado final:
715nil(L)
x 5
next(x) = next(nil(L));
prev(next(nil(L))) = x;
715nil(L)
x 5
next(nil(L)) = x;
prev(x) = nil(L);
L = Insertar_Lista (L, x)
next(x) = next(nil(L));
prev(next(nil(L))) = x;
next(nil(L)) = x;
prev(x) = nil(L);
- 5ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Estructuras de datos (V)
• Pilas
– Dinámica LIFO
– Restricción importante en el acceso a los datos
• Menos operaciones, más portable
– Aplicaciones:
• Muchas, por ejemplo para almacenar resultados
intermedios en una operación: 2 * ((9+1) *(2+3) +50)
– Notación polaca inversa (calculadoras HP)
– Operaciones básicas:
• Meter y sacar
– Implementación:
• Con listas enlazadas
• Con array (conocido el tamaño
máximo de la pila)
53 7 8 9
ult imo(P)
pila
53 47 8 9
ult imo(P)
2pila
53 47 8 9
ult imo(P)
2pila
Pila con un array P de 9 elementos:
Meter(P,4), Meter(P,2) :
Sacar(P): :
- 6ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Estructuras de datos (VI)
• Colas
– Dinámica FIFO
– Restricción importante en el acceso a los datos
• Menos operaciones, más portable
– Aplicaciones:
• Se usan menos que las pilas
– Operaciones básicas:
• Insertar y sacar
– Implementación:
• Con listas enlazadas
• Con array (dado tño. máximo de la pila)
Caja@
5 4 78
primero(C) ult imo(C)
Cola
53 4 78 9
primero(C)ult imo(C)
2
53 4 78 9
primero(C)ult imo(C)
2
Siguiente(C):
Insertar(C,9), Insertar(C,2), Insertar(C,3):
Cola implantada con array C de 9 elementos
- 7ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Estructuras de datos (VII)
• Árboles
– “Colección de vértices y arcos cumpliendo conjunto de requisitos”
• Un nodo (´vértice) es raíz
• Existe un único camino entre raíz y cualquier nodo
• Todo nodo tiene un padre (salvo el raíz)
– Terminología:
• padres, hijos, abuelos, tíos, ...
• Raíz, terminales (hojas)
• Altura, nivel
• Subárbol, camino
• Sucesor, antecesor
15
6
3
42
7
13
9
18
17 20
- 8ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Estructuras de datos (VIII)
• Árboles
– Tipos: binarios, n-arios (multicamino)
– Árbol vacío vs. completo (equilibrado)
– Los nodos terminales suelen ser distintos
(ficticios, sin hijos)
NILNIL
NILNIL
15
6
3
42
7
13
18
17 20
NILNIL NILNIL
NILNILNIL
• Propiedades interesantes:
– Existe exactamente un único camino conectado 2 nodos en un árbol
– 2 nodos tienen al menos un ancestro común
– Un árbol con N nodos tiene N-1 arcos
– Un árbol binario con N nodos internos tiene N+1 terminales
– La altura de un árbol binario completo con N nodos internos es
aproximadamente log2(N)
- 9ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Estructuras de datos (IX)
• Árboles • Recorridos:
– Preorden: visitar 1º Padre, 2º Izq. y 3º Dcha.
– Se implementa sin recursividad con una pila
– Orden central (In order): visitar 1º Izq., 2º Padre y 3º Dcha.
– Es el más típico (usar pila para eliminar recursividad)
– Postorden: visitar 1º Izq. 2º Dcha. y 3º Padre
– Usar pila para evitar recursividad
– Por Niveles (Level-Order): arriba-abajo e Izq. a Dcha.
– Usar una cola
15
6
3
42
7
13
9
18
17 20
15
6
3
42
7
13
9
18
17 20
15
6
3
42
7
13
9
18
17 20
Pre-orden Orden cent ral Post -orden
15,6, 3,2,4, 7,13,9, 18,17,20 2,4, 3,9,13, 7,6,17, 20,18,152,3, 4,6,7, 9,13,15, 17,18,20
- 10ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Estructuras de datos (X)
• Árboles
– Representación
• Árboles binarios:
• Árboles multicamino:
hijo_dcha(n)hijo_izq(n)
padre(n)rai z(T)
clave(n)altura(T)
Cada nodo n:
padre(n) hermano(n) hijo_izq(n)
raiz(T)
- 11
2
Proceso de creación
- 12ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Proceso de creación: idea (I)
• Finalidad última de un algoritmo: permitir solucionar un
problema
– Debe ser fácil de entender, codificar y depurar
– Uso eficiente de los recursos (tiempo y espacio)
• Fases típicas en la creación de soluciones informáticas
– Análisis del problema
– Diseño de la solución
– Implementación
Bueno sí, pero realmente lo que hay que hacer ....
Bla bla bla ...
Descripción del problema a resolver (apuntes)
- 13ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Proceso de creación: idea (II)
• Una vez especificado el problema a resolver
– Fase de creación del algoritmo
• Ciclo en espiral con cuatro etapas fundamentales
Descripción del problema
Diseño del algoritmo
Implementación prototipo
Análisis resultados
Descripción del problema a resolver (apuntes) • Formulación precisa
• En términos algorítmicos
• Usar pseudocódigo
• Probar la idea codificando el algoritmo
• Exactitud• Eficiencia
• Uso de prototipos:
– Validar ideas iniciales, detectar errores de concepto
– Empezar con algoritmos simples para determinar el beneficio de posibles mejoras del mismo
- 14ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Proceso de creación: diseño
• Fases típicas en la fase de diseño:
– Formular de forma informal el algoritmo
– Elegir la estructura de datos más conveniente para el
algoritmo
– Elegir el paradigma a seguir
– Perfilar el núcleo del algoritmo
– Añadir los detalles
– Controlar los casos especiales
– Revisar todo el algoritmo, usar ejemplos
– Optimizar de forma teórica (una vez que funciona)
– Estimar teóricamente el tiempo de ejecución y requisitos de
memoria
- 15ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Proceso de creación: análisis (I)
• Qué mirar en el análisis
– Tiempos de ejecución y consumos de
memoria
– Casos especiales (robustez del algoritmo)
– Posibles mejoras del algoritmo
• Acelerarlo y/o reducir consumoIdeal
- Tiempo CPU +
+
Memoria
-
A
B
C
- 16ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Proceso de creación: análisis (II)
• Es posible saber en qué puntos
se pierde más tiempo
- 17ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Proceso de creación: implementación (I)
• Un programa es una representación concreta de un
algoritmo en un lenguaje de programación
• Los detalles de un lenguaje de programación específico se
deben obviar durante el diseño del algoritmo
– Es tan sólo un medio para expresar un algoritmo de forma que un
procesador lo pueda ejecutar
– Algunos lenguajes facilitan su programación mejor que otros
• Desde el punto de vista de los algoritmos, hay que prestar
especial atención en los lenguajes de programación:
– Estructura de los bucles (for, do, do-while, etc), valor del contador a
la salida, recorrido de matrices, ...
– Paso por valor / referencia
– Índices de vectores (empiezan en 0 ó en 1)
– Recursividad
– Funciones estándar (módulo, ordenación, ...)
- 18ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Proceso de creación: implementación (II)
• Cada lenguaje tiene sus particularidades
• Muy bajo nivel:
– Ensamblador
• Bajo Nivel:
– Ej: C
• Alto nivel:
– Ej: Matlab
- 19ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Proceso de creación: implementación (III)
• Ejemplo: recorrido de matrices
en Matlab
¿Por qué no tarda lo mismo?
¿Es una diferencia en el orden de crecimiento o es
una constante?
n x m
m x n
- 20ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Técnicas de simplificación (I)
• Existen casos especiales que “ensucian y enmarañan” un
algoritmo inicialmente elegante
– Complican innecesariamente la algorítmica
– Son fuente de errores
• Ejemplos
– Existen elementos terminales en las estructuras que se usan
(inicio y fin normalmente)
– Naturaleza de la estructura (disposición ordenada de los
elementos, ...)
– Otras condiciones que no permiten tratar de igual forma todos los
elementos de la estructura
N1
N2 N3
N4
N7
N6N5
- 21ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Ejemplo 1: Inserción directa (I)
• Idea
• Utilizando un vector de registros y ordenando sobre el
mismo (utilizando espacio auxiliar para un registro):
mano
7Selecciona
últ ima carta
Inserta en
posición correcta
24 9
Cartas ya ordenadas
Es pac io d is ponible en memo ria
2 1 8695
- 22ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Ejemplo 1: Inserción directa (II)
A = InserciónDirecta(A, N) %A vector de registros a ordenar, N: nº de registros
1 For i=2 to N
carta = A[i]; % selecciona última carta
j=i-1; %
busca punto de inserción
2 While (j>0 & carta < A[j]) % alternando comparaciones
A[j+1]=A[j]; % y movimientos
j=j-1;
end 2
A[j+1]=carta; % inserta la carta
end 1
Secuencia origen Secuencia destino
BúsquedaSeleccionar el
siguiente
Inserción directa
- 23ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Ejemplo 2: ¿Es número primo?
• Problema
– Dado un número, ¿es primo?
• Idea
– Un número es primo si sólo es divisible por sí mismo y por la unidad
• El 9 no es primo porque 9/3 = 3. El 5 sí porque no es divisible entre 4,3,2
• Diseño del Algoritmo
– Planteamiento (algoritmo informal):
• “Para saber si el número n es primo hay que dividir sucesivamente el
número n por 2, 3, 4, ... hasta (n-1). En cuanto una división sea exacta,
ya se sabe que no es primo. Si no ocurre nunca, es primo.”
– Pseudocódigo:
Flag_es_primo = EsPrimo (n)
¿?
Fin
¿Existen formas de optimizar el algoritmo?
- 24ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Ejemplo 3: Horas de punta/llano/valle
• Problema
– Dada una curva de demanda para un día, determinar las horas de
punta, llano y valle (fijado el número que se quieren tener de cada
tipo)
A:
1
1
23 4 5 6
7
8
9
1011 12 13
14 15 16 17 18 1920 21 22 23
24
15
17
19
21
23
25
27
29
31
33
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
Hora
Co
nsu
mo
25.328.328.528.12829.730.329.929.529.429.831.130.530.229.127.324.221.41918.418.518.819.521.2 25.328.328.528.12829.730.329.929.529.429.831.130.530.229.127.324.221.41918.418.518.819.521.2
N
Horas de VALLE
Horas de PUNTA
Algoritmo pedido
199 20 21 23 22 10 15 16 14248 199 20 21 23 22 10 15 16 14248HLL:1 nll
18 11 171213 18 11 171213HP:1 np
3 6 2 1 745 3 6 2 1 745HV:1 nv
np=5
nv=7
nll =12
El consumo horario de
electricidad de un país tiene
un perfil muy característico.
Para cada día, dicho perfil
queda representado por 24
valores, uno para cada
hora. Por ejemplo, en el
array A y la gráfica asociada
se muestra el perfil de
consumo de España para el
lunes 14 de junio de 2004
(ver www.ree.es).
[HP, HLL, HV]=HorasPLLV(A, np, nll, nv)
- 25
3
Paradigmas de diseño
- 26ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Paradigmas
• Esquemas o modelos de diseño más o menos genéricos
• Muchos algoritmos utilizan alguno de los planteamientos
clásicos
– Conocerlos dan base para hacer desarrollos propios ...
• Paradigmas básicos clásicos:
– Fuerza bruta
– Divide y vencerás
– Voraz
– Paralelismo ...
- 27ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Fuerza bruta
• Consiste en resolver el problema “rudamente”
– Probar sistemáticamente todas y una de las posibles soluciones al
problema y elegir
– La falta de habilidad o imaginación para mejorar el proceso es su
característica fundamental
• Se confía en la capacidad de cálculo del ordenador para
conseguir resolverlo
• Suele ser la primera versión del algoritmo, una cota superior
de “al menos se puede resolver en ...”
• Cuando usarlo:
– No se dispone de mucho tiempo para pensar (desarrollo rápido)
– Se ejecutará pocas veces
- 28ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Fuerza bruta: ejemplo (I)
• ¿ Aparece el patrón P en el array A ?
0 0 1 1 1 0 0 1 0 1 0 1 1 0 1 1 1 0 1
0 1 1 0 1
A:
1 N
P:
1 M
• ¿Cuántos posibles encajes de P en A hay que probar?
• ¿Cuál es el peor caso?
• En el peor caso la versión de fuerza bruta requiere del orden de N • M
• ¿cómo es dicha versión?
no_existe = ExistePatron (A,N, P, M)
¿?
Fin
- 29ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Fuerza bruta: ejemplo (II)
• ¿ Aparece el patrón P en
el array A ?0 0 1 1 1 0 1 0 1 1 0 1 1 1 0 1
0 1 1 0 1
A:
1 N
P:
1 M
no_existe = ExistePatron (A,N, P, M)
I=1; j=1;
Repeat
1 if A(i) = P(j)
i=i+1; j=j+1;
Else
i = i-j+2; j=1;
End 1
Until ( j>M OR i>N);
2 if j>M
no_existe = 0;
Else
no_existe = 1;
End 2
Fin
0 0 1 1 1 0 1 0 1 1 0 1 1 1 0 1
0 1 1 0 1
0 1 1 0 1
0 1 1 0 1
0 1 1 0 1
0 1 1 0 1
0 1 1 0 1
0 1 1 0 1
0 1 1 0 1
i=2;j=1
i=5;j=4
i=13;j=6
Finaliza búsqueda
El índice i se utiliza para marcar qué “encaje” se está probando (empieza en i=i-
j+2) y al mismo tiempo comprobar las distintas
posiciones del encaje (i=i+1)Prueba fallida lenta
Pruebas fallidas rápidas (con una
única comparación se descartan estos
3 encajes)
- 30ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Divide y vencerás / Combina y vencerás (I)
• Consiste en:
– Dividir el problema en subproblemas, similares al original, pero de
tamaño menor.
– Se solucionan los problemas recursivamente. Si es suficientemente
pequeño se resuelve directamente.
– Se combinan esas soluciones para construir la solución al problema
original.
• Existen muchos algoritmos basados en esta sencilla idea ...
Problema
original
Subproblemas
Solución
final
Soluciones
parciales
- 31ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Divide y vencerás / Combina y vencerás (II)
• Esquema general
sol = DivideyVenceras (problema)
1 if EsPequeño (problema)
sol = ResolverDirectamente (problema);
Else 1
[sub_problemas] = Divide (problema); % M subproblemas
2 For i = 1 to M
sol_parciales[i] = DivideyVenceras (sub_problemas[i]);
end 2
sol = Combinar (sol_parciales);
end 1
Fin
- 32ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Divide y vencerás: ejemplo (I)
• Normalmente utiliza dos llamadas recursivas, típicamente
una para cada mitad
• Ejemplo:
– Dibujar una regla con las siguientes características:
• Dado un valor de n (por ejemplo n=4)
n
n-1n-1
2n
Ojo, en los extremos no hay marca
PintaMarca(4,n-1)
PintaMarca(8,n)
n-2
- 33ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Divide y vencerás: ejemplo (II)
• Dibujar una regla
– Ejemplo con n = 7 (aparecen 126 marcas)
• El aspecto de la regla se repite recursivamente ...
- 34ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Divide y vencerás: ejemplo (IV)
• Árbol de llamadas recursivas
– Ejemplo con n = 4 (aparecen 15 marcas)
– En cada nodo se representa iz, de y altura
0,16,4
0,8,3 8,16,3
0,4,2 8,12,24,8,2 12,16,2
0,2,1 8,10,14,6,1 12,14,1 14,16,110,12,16,8,12,4,1
- 35ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Divide y vencerás: ejemplo (V)
PintaReglaICD (iz,de,a) %izq-cent-dcha
1 if a > 0
me = (iz +de)/2 ; % siempre es exacta
PintaReglaICD(iz,me,a-1);
PintaMarca(me,a);
PintaReglaICD(me,de,a-1);
end 1
Fin
0,16,4
0,8,3 8,16,3
0,4,2 8,12,24,8,2 12,16,2
0,2,1 8,10,14,6,1 12,14,1 14,16,110,12,16,8,12,4,1
- 36ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Divide y vencerás: ejemplo (VI)
PintaReglaCID (iz,de,a) %cent-izq-dcha
1 if a > 0
me = (iz +de)/2 ; % siempre es exacta
PintaMarca(me,a);
PintaReglaCID(iz,me,a-1);
PintaReglaCID(me,de,a-1);
end 1
Fin
0,16,4
0,8,3 8,16,3
0,4,2 8,12,24,8,2 12,16,2
0,2,1 8,10,14,6,1 12,14,1 14,16,110,12,16,8,12,4,1
- 37ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Divide y vencerás: ejemplo (VII)
Para saber más:http://en.wikipedia.org/wiki/Mandelbrot_set
- 38ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Algoritmo voraz (I)
• Producir un resultado “óptimo” a partir de un conjunto de
opciones candidatas
– Optimizar cierta medida o función objetivo
– Cumpliendo ciertas restricciones
• Hipótesis de partida:
– Al menos existe una solución óptima, si hay varias equivalentes
• Características de este enfoque:
– La solución se va formando poco a poco (incrementalmente)
• Se elige la mejor forma de incrementar la solución parcial eligiendo la
mejor opción candidata
• Una vez incrementada (mejorada) la solución parcial, no se puede
modificar eliminando elementos de la misma
- 39ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Algoritmo voraz (II)
• Esquema general
sol = Voraz (candidatos)
sol = { };
1 while (candidatos { } AND NoEsSolucion(sol) )
mejor = Seleccionar (candidatos);
candidatos = candidatos – {mejor};
2 if EsValida (sol {mejor} )
sol = sol {mejor} ;
end 2
end 1
Fin
- 40ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Algoritmo voraz: ejemplo (I)
• Desglose de un importe
– Dado un importe, desglosarlo en el menor número de billetes y
monedas posible
– Útil en una máquina que tenga que devolver cambio (por ej. una
expendedora de billetes de metro)
• Se plantea utilizando un par de vectores:
50 20 10 5 2 1val:
1 N
2 1 0 0 1 1cant:
1 N
importe: 123
Desglose del importe según las monedas con
los valores val, minimizando el número
de monedasDevuelve el vector de
cantidades (con el número de monedas de
cada tipo)
• El vector de valores de monedas está ordenado de + a -
• Se supone que el importe se puede desglosar perfectamente
- 41ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Algoritmo voraz: ejemplo (II)
• El desglose del dinero se puede plantear como un algoritmo
voraz ya que:
– Conjunto de candidatos
• Cada una de las monedas disponibles
– Solución posible
• Conjunto de monedas tal que sumen el importe a desglosar
– Condición de factibilidad (EsValida)
• En todo momento la suma de las monedas tiene que ser menor o igual al
importe
– Función de selección
• Elegir, mientras sea posible, la moneda de valor mayor de entre las
candidatas
– Función objetivo
• Minimizar el número de monedas
- 42ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Algoritmo voraz: ejemplo (III)
• Desglose de un importe, tres posibles enfoques:
cant = DesgloseVersion1 (importe, val, N)
cant = ceros (N); % inicializa a ceros
i=1;
1 while (i N & importe > 0)
2 if (val(i) importe)
cant(i) = cant(i) + 1;
importe = importe - val(i);
else 2
i = i + 1;
end 2
end 1
Fin
cant = DesgloseVersion2 (importe, val, N)
cant = ceros (N); % inicializa a ceros
i=1;
1 while (i N & importe > 0)
2 while (val(i) importe)
cant(i) = cant(i) + 1;
importe = importe - val(i);
end 2
i = i + 1;
end 1
Fincant = DesgloseVersion3 (importe, val, N)
cant = ceros (N); % inicializa a ceros
i=1;
1 while (i N & importe > 0)
cant(i) = floor (importe / val(i));
importe = mod (importe, val(i));
i = i + 1;
end 1
Fin
• ¿Son teóricamente equivalentes en cuanto a tiempo de ejecución?
• Desde el punto de vista práctico ¿existirán diferencias?
- 43ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Algoritmo voraz: ejemplo (IV)
• Desglose de un importe
DesgloseVersion1
DesgloseVersion2
DesgloseVersion3
El tiempo de ejecución es lineal con el importe a desglosar en las tres
versiones (asintóticamente equivalentes), pero las constantes reales son claramente diferentes
top related