Eficiencia de Los Algoritmos
La eficiencia de los algoritmos La eficiencia de los algoritmos # " #
Views 109 Downloads 0 File size 151KB
Recommend stories
- Author / Uploaded
- squalologin
Citation preview
La eficiencia de los algoritmos
La eficiencia de los algoritmos
# "
#
TEMA 1
& ' ( ) * + &" (+ , +-% +
LA EFICIENCIA DE LOS ALGORITMOS
INDICE
! " #$ %
1
2
La eficiencia de los algoritmos
!"#$ %
. -
'
' / '
La eficiencia de los algoritmos
A.V. Aho, J.E. Hopcroft, J.D. Ullman: “The design and analysis of computer algorithms”. Addison-Wesley, 1974. A.V. Aho, J.E. Hopcroft, J.D. Ullman: “Estructuras de datos y algoritmos”. AddisonWesley Iberoamericana, 1988. S. Sahni: “Concepts in Discrete Mathematics”. The Camelot Publishing Company, 1985.
0112 %' 3 ' & '()*
4$4 $5 67 +, +. / 5 8 99: 6+ !+ ) . ! ,
99; #
BIBLIOGRAFÍA COMPLEMENTARIA 3
4
La eficiencia de los algoritmos
Normalmente, un problema se puede resolver por métodos distintos, con distintos grados de eficiencia. Ejemplo: búsqueda de un número en una guía telefónica. Cuando se usa un ordenador es importante limitar el consumo de recursos.
La eficiencia de los algoritmos
COSTE = Consumo de estos recursos por parte de un algoritmo.
En esta asignatura nos interesa el estudio del coste temporal.
Si un programa se va a usar una o muy pocas veces, puede darse el caso de que lo más importante sea que sea fácil de entender, codificar y depurar.
Recursos: Tiempo: Aplicaciones informáticas que trabajan “en tiempo real”: requieren que los cálculos se realicen en el menor tiempo posible. Aplicaciones que manejan un gran volumen de información: si no se tratan adecuadamente pueden necesitar tiempos impracticables.
A medida que se dispone de ordenadores más rápidos, se pretende resolver problemas más grandes y complejos, por lo que el uso de algoritmos eficientes sigue siendo importante.
Problemas intrínsecamente complejos. Espacio: Las máquinas tienen una memoria limitada.
5
6
La eficiencia de los algoritmos
FACTORES DE LOS QUE DEPENDEN LOS PARAMETROS DEL COSTE:
La eficiencia de los algoritmos
APROXIMACIONES AL ANÁLISIS DE LA EFICIENCIA DE LOS ALGORITMOS (memoria y tiempo de ejecución):
A - Factores propios del problema: procedimiento de resolución del problema, y los datos.
Análisis experimental o "a posteriori" (se verá en la prácticas de laboratorio). Consiste en ejecutar casos de prueba, haciendo medidas para: una máquina concreta,
B - Factores dependientes de la máquina:
tipo de computador, lenguaje de programación, carga del sistema, etc.
En esta asignatura nos interesan los factores propios del problema.
un lenguaje concreto, un compilador concreto y datos concretos. Análisis teórico o "a priori" (se verá en las clases teóricas). Consiste en obtener una expresión que indique el comportamiento del algoritmo en función de los parámetros que influyan. Interesante porque: La predicción del coste puede evitar una implementación posiblemente laboriosa. Es aplicable en la etapa de diseño de los algoritmos, constituyendo uno de los factores fundamentales a tener en cuenta.
7
8
La eficiencia de los algoritmos
La eficiencia de los algoritmos
EJEMPLOS:
1.- Algoritmo de ordenación: la talla del problema será el número de elementos a ordenar.
COMPLEJIDAD (O COSTE) DE UN ALGORITMO:
2.- Algoritmo de búsqueda de un elemento en una secuencia: la talla del problema será el número de elementos de la secuencia.
Es una medida de la cantidad de recursos (tiempo, memoria) que el algoritmo necesita.
3.- Algoritmo del cálculo del factorial de un número: la talla será el valor del número.
La complejidad de un algoritmo se expresa en función del tamaño o talla del problema. ¿COMO CALCULAR LA COMPLEJIDAD TEMPORAL DE UN ALGORITMO?
TALLA DE UN PROBLEMA: Es cualquier parámetro en función del cual se pueda expresar la complejidad del problema: Nº de datos de entrada Nº de datos de salida Valor de las variables numéricas Una función de los anteriores Suele guardar relación con el volumen de los datos a tratar, y por ello se le suele llamar “tamaño” del problema.
Contando el número de operaciones elementales o pasos de programa que realiza. De esta forma: coste(n) = Número de pasos de programa en función de n. Es independiente de la máquina concreta utilizada.
9
10
La eficiencia de los algoritmos
Son aquellas cuyo tiempo de ejecución está acotado superiormente por una constante que no depende de la talla del problema.
La eficiencia de los algoritmos
EJEMPLOS DE COSTES:
x := x + y coste = 1 paso.
EJEMPLOS DE PASOS DE PROGRAMA: para i := 1 hasta n hacer x := x + y fpara
x := y + z 1 paso
talla = n, coste(n) = n pasos.
x := y + z x := x * x 2 pasos (ó también 1 paso) si x = 0 entonces y := y + 1 sino y := y - 1 fsi 1 paso (ó también 2 pasos)
para i := 1 hasta n hacer para j := 1 hasta n hacer x := x + y fpara fpara talla = n, coste(n) = n2 pasos.
si x = 0 entonces y := y + 1 fsi 1 paso
11
12
La eficiencia de los algoritmos
La eficiencia de los algoritmos
GRÁFICAS DE FUNCIONES
TABLA DE TIEMPOS DE EJECUCIÓN Tiempos de ejecución en un máquina capaz de ejecutar 109 pasos de programa por segundo para tallas (n) y costes (en número de pasos) dados. n (Talla) Pasos log2n n nlog2n
1
8
32
103
106
109
< 1 ns
3 ns
5 ns
10 ns
20 ns
30 ns
1 ns
8 ns
32 ns
1 s
1 ms
1s
< 1 ns
24 ns
160 ns
10 s
20 ms
30 s
1 ms
17 min 38 años
2
n
1 ns
64 ns
1 s
n3
1 ns
512 ns
33 s
2n
2 ns
256 ns
4.3 s
n!
1 ns
40 s
nn
1 ns
17 ms
> 1018 años > 1031 años
> 1010 años > 10291 > 10300K > 10300M años años años > 102K > 105M >109000M años años años >103K > 106M >109000M años años años 1 s 38 años
Problemas inabordables
13
14
La eficiencia de los algoritmos
TALLAS PARA DOS ORDENADORES DE DIFERENTE POTENCIA Talla (n) del problema que puede ejecutarse en un tiempo prefijado, en función de la velocidad del computador (que aumenta de V a 10V). Nº de pasos 300 log2n 100 n 5 n2 n3 / 2 2n n! / 100 nn / 100
n para 10V n para 10V n para V 1010 109 100 10 45 3.2 27 2.3 13 1.3 10 1.1 7 1
n para V 10 10 14 12 10 9 7
A medida que se baja en la tabla, aumenta más despacio la talla del problema que es posible tratar usando una máquina 10 veces más rápida. Cuando el coste es lineal (100 n en esta tabla) una máquina 10 veces más rápida permitirá tratar un problema 10 veces “más grande”.
La eficiencia de los algoritmos
¿De qué depende la complejidad de un algoritmo A? 1. De la talla del problema: n. 2. Para una talla fija, de la instancia del problema. En general obtendremos una expresión del coste distinta para cada instancia: costeA(I,n) = Número de pasos de programa para una talla n y una instancia I
Nos interesan las instancias significativas: Ip: peor de los casos. Cuando son necesarios el máximo número de cálculos. Im: mejor de los casos. Cuando son necesarios el mínimo número de cálculos.
15
16
La eficiencia de los algoritmos
La eficiencia de los algoritmos
EJEMPLOS DE INSTANCIAS
Sean: n la talla del problema de A S(n) = { I : I Instancia talla(I) = n }
1.- Búsqueda secuencial de un elemento x en un vector a: función buscar
entonces:
( x: elemento; a: vector índice de entero; n: índice) devuelve índice;
p
costeA (n) = máx {costeA(I,n) : I S(n)} = costeA(Ip,n) (coste peor) costeA
m
(n) = mín { costeA(I,n) : I S(n)} = costeA(Ip,n)
(coste mejor) costeA
Med
(n) = S(n) P(I) * costeA(I,n)
(coste medio)
{1n k:1kn:ak=x} var i:índice fvar; i:=1; mientras a[i] x hacer i:=i+1 fmientras; devuelve i {1in ai=x j:1j 3.
21
22
La eficiencia de los algoritmos
La eficiencia de los algoritmos
CONSIDERACIONES: Interesa estudiar el comportamiento de un algoritmo para tallas relativamente grandes: complejidades asintóticas. Interesa comparar los comportamientos de los algoritmos según el orden de magnitud de sus complejidades. Interesa hacer estudios de la complejidad independientes de la velocidad del computador donde se programa el algoritmo desarrollado. Esto significa que funciones de complejidad que difieren en un factor constante se consideran idénticas a efectos de medidas de costes.
/0 Objetivo: obtener una notación clara y simple para expresar el coste de un algoritmo para valores grandes de la talla y con independencia de la velocidad del ordenador utilizado. En lo que sigue, f, g, f1, f2, y f3 serán funciones de N en R+. (R+ = { x R: x > 0 } en este tema.)
Por lo tanto, para el cálculo de la complejidad adoptaremos un CRITERIO ASINTOTICO.
23
24
La eficiencia de los algoritmos
La eficiencia de los algoritmos
NOTACION
NOTACION O Definición. Se dice que
Definición. Se dice que
- f es como mucho del orden de g, o que
- f es como mínimo del orden de g, o que
- f crece más lentamente o igual que g, o que
- f crece más rápidamente o igual que g,
- g es una cota superior de f,
o que
sii c>0, n0 N: f(n) c g(n) n n0
- g es una cota inferior de f, sii c>0, n0 N: c g(n) f(n) n n0
Definición. O(g(n)) = { funciones que son como mucho del orden de g(n) }
Definición. (g(n)) = { funciones que son como mínimo del orden de g(n) }
Ejemplos.
Ejemplos.
1.- 3n O(n): Si se toma C=3 y n0=0 se tiene
1.- 3n (n):
f(n) = 3n 3n = C·g(n) n0.
Si se toma C=1 y n0=0 se tiene C·g(n) = 1·n 3n = f(n) n0.
2
2.- 3n O(n ): Si se toma C=3 y n0=0 se tiene
2.- n2 (3n):
2
f(n) =3n C·g(n) = 3n n0.
Si se toma C=1 y n0=3 se tiene C·g(n) = 1·3n n2 = f(n) n3.
25
26
La eficiencia de los algoritmos
La eficiencia de los algoritmos
b) 3n (n) ( “
NOTACION Definición. Se dice que - f es del orden de g, o que - f crece igual de rápidamente que g, o que
“
).
Definición. Se dice que - f es de menor orden que g, o que - f crece más lentamente que g, sii f(n) O(g(n)) pero f(n) (g(n)).
- g es una cota superior e inferior de f, sii c,d>0, n0 N: c g(n) f(n) d g(n) n n0
Definición. Se dice que
Definición. (g(n)) = { funciones que son del orden de g(n) }
- f es de mayor orden que g, o que - f crece más rápidamente que g, sii f(n) (g(n)) pero f(n) (g(n)).
!
TEOREMA. 1- f es de menor orden que g sii O(f(n)) O(g(n)).
Proposición. f(n) (g(n)) f(n) O(g(n)) f(n) (g(n)) f(n) (g(n)) f(n) O(g(n)) g(n) O(f(n))
2- f es de mayor orden que g sii (f(n)) (g(n)). Nota: denota en este tema la inclusión estricta.
Ejemplo. 3n (n), pues a) 3n O(n) (visto anteriormente).
27
28
La eficiencia de los algoritmos
Los siguientes teoremas son útiles para comparar tasas de crecimiento de funciones.
La eficiencia de los algoritmos
COROLARIO a. Si p es un polinomio de grado r, entonces p es del mismo orden que nr. b.
TEOREMA
n , con >1 constante, crece rápidamente que cualquier polinomio.
más
c. Si 1>K2>1, entonces
f (n) K 0 (f(n)) (g(n)) n g ( n) lim
n crece más rápidamente que n, pero log(n) es del mismo orden que log(n).
(f y g son del mismo orden).
d. Cualquier polinomio crece más rápidamente que log(n). TEOREMA lim
n
f ( n)
g (n)
e. n! crece más rápidamente que n. f(n ) crece más rápidamente que g(n),
f.
nn crece más rápidamente que n!.
o lo que es lo mismo: O(g(n)) O(f(n)).
TEOREMA lim
n
f ( n)
g (n)
0 g(n ) crece más rápidamente que f(n).
o lo que es lo mismo: O(f(n)) O(g(n)).
29
30
La eficiencia de los algoritmos
La eficiencia de los algoritmos
"
& 1& %#"#"2 (&
Muchas veces las notaciones asintóticas pueden aparecer dentro de expresiones, por ejemplo:
En primer lugar hay que determinar la talla del algoritmo.
f(n ) = n2 + O(1/n) significa que f(n ) es una función cuadrática más un término asintótico menor que 1/n. Se debe de entender como suma de conjuntos de funciones.
Para calcular el coste de un algoritmo:
En los algoritmos en los que el coste temporal sea independiente de las instancias, es decir, cuando el caso mejor y el peor coincidan, utilizaremos directamente la notación para estimar la complejidad del algoritmo: coste (n) (f(n)).
f(n ) n2 + O(1/n)
En los algoritmos en los que el coste temporal varíe en función de las instancias, podremos distinguir:
#$ %
COROLARIO
Peor caso y
a) De menor a mayor orden: O(1) O(log(n)) O(n) O(nlog(n)) 2
3
n
Mejor caso. n
O(n )O(n ) ... O(K ) O(n!) O(n ). b) De mayor a menor orden: (1) (log(n)) (n) (nlog(n)) 2
3
n
n
(n ) (n ) ... (K ) (n!) (n ).
31
32
La eficiencia de los algoritmos
PEOR CASO:
La eficiencia de los algoritmos
EJEMPLOS.
Utilizaremos la notación (o la si fuera necesario) para estimar la complejidad del algoritmo en el peor de los casos: costep (n) (f(n)),
1. Para el algoritmo de búsqueda secuencial: • Talla del problema: n. • Instancias significativas: caso mejor, caso peor. costep(n) (n)
con lo que obtendremos una cota superior de la complejidad del algoritmo: costeA(n) (f(n)).
costem(n) (1) Por lo tanto: coste(n) (n) coste(n) (1)
MEJOR CASO: Utilizaremos la notación (o la si fuera necesario) para estimar la complejidad del algoritmo en el mejor de los casos: m
costeA (n) (g(n)), con lo que obtendremos una cota inferior de la complejidad del algoritmo: costeA(n) (g(n)).
2. Búsqueda del máximo de un vector: • Talla del problema: n. • Instancias: no hay instancias significativas que afecten al coste. En cualquier caso se recorre todo el vector. coste(n) (n).
33
34
La eficiencia de los algoritmos
#"131/" #%/" 2 &"!//
La eficiencia de los algoritmos
2 &"!///"&%1%#(4 1"%
Procedimiento a seguir: 1. Determinar qué parámetro(s) nos da(n) la talla o tamaño del problema, en función de la cual se expresará la complejidad. 2. Identificar el caso peor y el caso mejor de comportamiento del algoritmo en cuanto a consumo de tiempo (o de espacio si se estudia la complejidad espacial). 3. Aplicar un método de obtención de las cotas de complejidad.
Complejidad Temporal: se calcula contando el número de pasos de programa de cada instrucción en función de la talla del problema.
Vamos a estudiar la complejidad de las siguientes instrucciones: operaciones básicas, secuencia de instrucciones, sentencia alternativa, y sentencia iterativa.
Operaciones básicas. Se van a considerar como pasos de programa las operaciones básicas: asignación, comparación, operaciones aritméticas, lectura/escritura... Coste de un paso de programa (1) Ejemplo. Las siguientes instrucciones tienen un coste (1): x := y + z; b := x y (a b); escribir(‘Un texto constante como éste’).
35
36
La eficiencia de los algoritmos
Secuencia de instrucciones ( S = S1 ; S2).
La eficiencia de los algoritmos
Sentencia alternativa “si .. fsi”.
coste( S ) = coste( S1 ) + coste( S2 ) Caso especial: para grandes tallas, puede darse que una de las instrucciones tenga coste despreciable frente a la otra, con lo que se podrá aplicar el siguiente resultado:
S1 sino S2 fsi
coste( “SI “ ) = coste( B ) + coste( S1 ó S2 ), dependiendo de la acción (S1 ó S2) que se ejecute: B cierta se ejecutará S1
coste( S 1 ) ( f1 ) coste( S2 ) ( f2 )
Si B entonces
coste( S ) ( f2 )
O( f1 ) O( f2 )
coste( “SI” ) = coste( B ; S1 ) B falsa se ejecutará S2 coste( “SI” ) = coste( B ; S2 )
Ejemplos.
Si denotamos: coste( B ) ( g ),
1. Supongamos que: coste( S1 ) = 2n + 3 (n),
coste( S1 ) ( f1 ),
coste( S2 ) = 5n + 1 (n).
coste( S2 ) ( f2 ),
Entonces coste( S1 ; S2 ) = 7n + 4 (n). 2. Supongamos que:
en la práctica se suelen dar los siguientes casos: Costes parciales
coste( S1 ) = 3n + 1 (n), coste( S2 ) = 7n2 (n2). Entonces coste( S1 ; S2 ) (n2).
coste( “SI” )
O( g ) O( f1 ) = O( f2 )
( f1 )
O( g ) O( f1 ) O( f2 )
( f1 ), O( f2 )
37
38
La eficiencia de los algoritmos
Sentencia iterativa “mientras ... fmientras”.
Sea n el número de iteraciones que de hecho se ejecutan la ejecución de la instrucción anterior será equivalente en efectos y en coste a la ejecución de:
B ; S;
...
nª iteración
(falla B)
B ; S;
B
(Nota: B es una función y no un procedimiento, por lo que el cuadro anterior contiene una imprecisión.) coste( “Mientras” ) = i = 1..n coste( B(i) ; S(i) ) + coste( B(i+1) ) donde
(i)
Casos Prácticos Caso 1. Se realizan n iteraciones, y la i-ésima p iteración (guarda + cuerpo) tiene un coste i , con p constante.
Mientras B hacer S fmientras
1ª iteración
La eficiencia de los algoritmos
hace referencia a la i-ésima iteración.
Coste =
n
ip
i 1
n p 1 n p (n p 1 ) p1 2
Coste (np+1)
Ejemplo: Para i := n decreciendo hasta 1 hacer escribe_letra(“a”, i) fpara, en donde escribe_letra(“a”, i) escribe i veces el carácter “a” y tiene un coste (i). La talla del problema es n, y su coste será: n
Puesto que los costes parciales anteriores pueden ser distintos en cada iteración del bucle, la casuística que puede presentarse es muy variada.
39
coste =
i (n i 1
40
2
).
La eficiencia de los algoritmos
Son habituales los siguientes subcasos: n
p=0
1 n (n) .
p=1
i
p=2
i
i 1
1
n( n 1) ( n 2 ) . 2
2
n(n 1)(2n 1) ( n 3 ) . 6
n
i 1 n
i 1
Caso 2: Medidas logarítmicas. Supongamos que en cada iteración la talla n se reduce en un factor c, hasta llegar a una talla mínima n0 >0 para la que se da la condición de salida del bucle. Tras la 1ª iteración: la talla pasa a n/c 2 Tras la 2ª " : " n/c ..................................................... y tras una q-ésima iteración, la talla se reduce a n0. Como se tendrá que n/c iteraciones será:
k
= n0, el número de
k = logc (n/n0).
La eficiencia de los algoritmos
Ejemplo: búsqueda ordenado.
dicotómica
en
un
vector
{ v está ordenado } procedimiento dicotómica (v: vector 1..n
de entero; n, x: entero; sal está: lógico; sal m: entero) es var i,j: entero fvar; i:=1 ; j:=n; está := falso; repetir m := (i+j) div 2; opción v[m] > x: j := m - 1; v[m] < x: i := m + 1; v[m] = x: está := verdadero; fopción hasta que i>j está fprocedimiento {1mn((está vm=x) (está k:1kn:vkx)} • La talla del problema es la dimensión del vector. Se puede considerar la talla como un valor dinámico que tras cada iteración es la longitud de la zona del vector donde aún no se ha descartado que pueda estar x.
41
42
La eficiencia de los algoritmos
La eficiencia de los algoritmos
Caso peor: x no está en el vector, y por lo tanto en número de iteraciones es máximo. costep(n) = 1 + coste_iteración = 1 + (1 + coste_si + coste_guarda)*(nº iteraciones) = 1 + K*(nº iteraciones). El cálculo del número de iteraciones en este caso es un ejemplo de reducción logarítmica. Tras cada iteración se reduce la talla aproximadamente a la mitad, hasta llegar a un tamaño 1. Por ello, el número de iteraciones es log2n. Luego costep(n) = 1 + Klog2n (log2n).
Caso mejor: se encuentra de inmediato el elemento y la iteración cesa: costem(n) (1).
&! ! ( v[i]
i := i + 1 x := v[i];
fmientras
desplazar hacia la derecha todos los elementos de v[p .. i - 1]; v[p] := x; 1
i-1
{
n
}
i:=i+1 fmientras 51
i
52
La eficiencia de los algoritmos
¡los pasos 1 y 2 se pueden realizar de forma simultánea! Reformulación en un paso de insertar ordenadamente v[i] en v[1 .. i - 1] {i n ordenado(v, 1, i-1) v[1 .. i-1] = perm(V, 1, i-1)}
La eficiencia de los algoritmos
>
?@A? ( B ' % B @ C 0D2 E = D? 02? 1 1 (1) 1
p:=i; x:=v[i]; mayor:=true;
i 1
( B
%3% B @
mientras (p>1) mayorhacer si v[p-1] F (
@ > F (
@ G > DF (
@D?H @D?H D? i
02? 1 i (i) j 1
v[p]:= x; {(i n) ordenado(v, 1, i) v[1 .. i] = perm(V, 1, i)}
53
54
La eficiencia de los algoritmos
i := 2; mientras i n hacer
La eficiencia de los algoritmos
" 5insertar ordenadamente v[i] en v[1..i-1], 6 7 n 1
insertar ordenadamente v[i] en v[1..i-1]; i := i + 1 fmientras >
? ( El vector está ya ordenado coste(n) (n) ( El vector está ordenado al revés coste(n) (n2)
02? 1 n 1 (n) i 1
( / / F (
@ G > DF (
@0DA2?H
" 5 . : 6;5 575 8 9
@D@?H D? @
= F 0?2 0/2 = F 0?2 0/2@ G
59
60
La eficiencia de los algoritmos
= - 0?@2 0/@2
La eficiencia de los algoritmos
5.2- Otros algoritmos sobre vectores. 5.2.1La bandera nacional holandesa
n 1
n 1
i 1
i 1
(n (i 1)) n i 1 (n )
02?
2
Sea una fila de n bolas de color blanco, rojo y azul. Sea un brazo mecánico capaz de efectuar las operaciones: • color(i): averigua el color de la bola que se encuentra en la posición i-ésima de la fila.
" algoritmo ordenar (DATOS v:vector[1..n]de TipoBase; RESULTADOS v: vector [1..n] de TipoBase) var siguiente: entero fvar para siguiente:=1 hasta n-1 hacer para j:=n descendiendo hasta siguiente+1 hacer si v[j] < v[j-1] entonces intercambiar(v[j],v[j-1]) fsi fpara fpara falgoritmo
K
(
• perm(i,j): posiciones.
permuta
las
bolas
de
estas
Se pide un algoritmo iterativo que en una sola pasada sobre la fila, realizando como mucho n intercambios, y sin utilizar una fila auxiliar, deje a las bolas formando la bandera nacional holandesa. 1. ESPECIFICACION. Precondición: la fila está constituida únicamente por bolas rojas, blancas y azules, dispuestas en cualquier orden. 1
n ?
n 1
n
n 1
n 1
i 1
i 1
1 n (i 1) 1 n i
02?
i 1 j i 1
n 1
n 1
i 1
i 1
Postcondición: 1
n azul
n 1 i ( n 2 )
blanco
rojo
en donde alguna de las zonas puede estar vacía.
61
62
La eficiencia de los algoritmos
La eficiencia de los algoritmos
coincide con toda la fila. En el estado final, la zona indefinida está vacía.
2. INVARIANTE. En un estado intermedio cualquiera, en la fila -Hay tres bandas formadas por bolas ya revisadas y situadas en una posición adecuada. -Entre unas posiciones “v” y “x” está una banda indefinida formada por aquellas bolas que aún no se han revisado. -El color de cualquier bola de la fila es blanco, rojo o azul.
3a) El invariante se cumple al empezar la iteración si se inicializa: u:=0; v:=1; x:=n
0 1
n
u v
x
la zona indefinida:
Si se indica con 1
n ? u
v
r x
Invariante:
i:1 i u:color(i)=azul j:u0. El cuerpo de la iteración deberá consistir de unas instrucciones tales que, manteniendo el invariante, disminuyan la función limitadora:
u
r
v
x
v+1
I v x color(v)=azul: intercambio
opción: 1
color(v) = blanco: v:=v+1;
n ?
r
color(v) = azul: u:=u+1; perm(v,u); v:=v+1; u
color(v) = rojo: perm(v,x); x:=x-1 fopción
v
x
u+1 v+1
I v x color(v)=rojo:
Veamos que la "opción" es correcta y mantiene el invariante: • Siempre se cumple alguna de las guardas. Cabe recordar que el invariante afirma que cualquiera de las bolas es de uno de los tres colores que se citan, luego
intercambio 1
n ? u
r x
v v+1
65
x-1
66
La eficiencia de los algoritmos
• Es inmediato comprobar que en cualquier caso de la "opción", la función limitadora decrece.
La eficiencia de los algoritmos
5.2.2 Búsqueda binaria. Enunciado del problema:
El algoritmo queda escrito como sigue: > Búsqueda de un elemento que tiene un valor dado X.
u:=0; v:=1; x:=n;
> Inicialmente el vector se encuentra ordenado (ascendentemente)
mientras v x hacer opción: color(v) = blanco: v:=v+1;
> Supondremos, por simplicidad, que:
color(v) = azul: u:=u+1; perm(v,u); v:=v+1; color(v) = rojo: perm(v,x); x:=x-1 fopción
- el vector es de enteros - la cota inferior del vector es 1 - la cota superior del vector es N
fmientras
Definición del problema Talla = n (tamaño del vector) algoritmo búsqueda_binaria n
Coste(n)=
1 (n) i 1
(datos v: Vector[b1 .. bn ] de TipoBase; x:TipoBase; resultados está: lógico) P = {x = X v = V ordenado(V) } Q = {está = ( i: 1 i N: x = v[i]}
67
68
La eficiencia de los algoritmos
Estrategia: como el vector está ordenado ascendentemente, la búsqueda binaria se plantea como una búsqueda en el subvector donde se puede encontrar el elemento buscado, subvector de búsqueda.
La eficiencia de los algoritmos
Diseño del algoritmo a partir del invariante ¿El invariante se cumple al empezar la iteración?
En cada iteración de la búsqueda: > Acceder al elemento central v[m] del subvector de búsqueda
En efecto, al inicio el subvector de búsqueda coincide con el vector v, por lo que izq := 1; der:= N; m : = (izq + der) div 2
> SI: X = v[m]
X < v[m] buscar en subvector izquierdo
v[1] v[2]
X > v[m] buscar en subvector derecho
izq
v[1] v[2]
1
búsqueda finalizada
...
2
izq
m
2
v[m ]
v[n]
m
der
Por tanto
v[N ]
v[m ]
...
P inicioI
N
der
I {( i:1 i < izq: v[i] < X)# i:der $i N : X< v[i]) 1 izq N 1 der N 1 m N m=(izq+der)div2} t = der -izq + 1 ó
número de elementos del subvector de búsqueda 69
70
La eficiencia de los algoritmos
¿El invariante se cumple al terminar la iteración?
La postcondición Q = {está = ( i: 1 i N: x = v[i]} se puede alcanzar de dos formas tras salir del bucle:
La eficiencia de los algoritmos
¿Se cumple el invariante tras cada iteración? Las instrucciones que conforman el cuerpo de la iteración deben hacer que el invariante “progrese” hacia la postcondición con cada iteración. Con ello, el tamaño del subvector de búsqueda debe decrecer. I (v[m] X) #izq $der) t = der -izq + 1
está = true v[m] = X está = false i: 1 i N : X v[i]
Cuerpo_iteración I Por tanto, en la primer iteración
Equivalentemente, se termina sii v[m] = X izqder
v[1] v[2]
izq
Por tanto, seguiremos buscando si
...
2
v[m ] x
v[n]
m
der
Si v[m] $x, el elemento estará en [m+1 .. der]
B = (v[m] X) #izq $der) v[1] v[2]
1
2
...
v[n]
v[m ] x m
izq
Si v[m]x, el elemento estará en [izq .. m-1]
71
72
der
La eficiencia de los algoritmos
v[1] v[2]
izq
...
2
der
v[m ] x
v[n]
m
N
La eficiencia de los algoritmos
Por tanto, el cuerpo de la iteración sería opción v[m] $x: izq:= m + 1 v[m] x: der:= m - 1 fopción m := (izq + der) div 2
Veamos que la "opción" es correcta y mantiene el invariante y hace decrecer la función limitadora: • Siempre se cumple alguna de las guardas: si v[m] X entonces (v[m] $x) (v[m] x) • Para cada opción, cuando se parte de un estado en que se cumple IB, la ejecución de la instrucción correspondiente conduce de nuevo al invariante Opción 1 I v[m] < X izq < der izq:= m + 1 m := (izq + der) div 2 I y la función limitadora decrece 73
74
La eficiencia de los algoritmos
Opción 2
La eficiencia de los algoritmos
Este problema se soluciona re-escribiendo la opción
I v[m] X izq < der
opción
der:= m - 1
v[m] $x: izq:= m + 1
m := (izq + der) div 2
v[m] x: der:= m
¿I?
fopción
y la función limitadora decrece
m := (izq + der) div 2
¡CUIDADO! Supongamos que
Ejercicios:
- izq y der son consecutivos: izq = der -1. Por tanto, m = izq - izq =1. Por tanto m = 1 - v[m] X v[1]
1.- Comprobar que con la modificación realizada, la función limitadora decrece cuando v[m] x (pista: si está dentro del bucle izq der - 1) 2.- Comprobar que si izq y der son consecutivos, pero v[m] $x no hay problemas.
v[2]
Por tanto, la búsqueda binaria queda como sigue: izq= m = 1
der
función búsqueda_binaria(v:Vector[1..N]de enteros; x:entero) devuelve Lógico
Al ejecutar la instrucción der :=m -1 var está:Lógico; m, izq, der :entero fvar
¡der := 0! ¡No se cumple el invariante!
75
izq := 1; der := N;
76
La eficiencia de los algoritmos
La eficiencia de los algoritmos
m := (izq + der) div 2; mientras (v[m] x) #izq $der) hacer opción v[m] $x: izq:= m + 1 v[m] x: der:= m fopción m := (izq + der) div 2 fmientras devuelve está := (v[m] = x) ffuncion
B 0 2% / C 0D2
E > F (
M > F (
M
> D@