Teórica08

Vista previa del material en texto

Algoritmos de búsqueda sobre secuencias
Algoritmos y Estructuras de Datos I
1
Búsqueda lineal
I Recordemos el problema de búsqueda por valor de un
elemento en una secuencia.
I proc contiene(in s : seq〈Z〉, in x : Z, out result : Bool){
Pre {True}
Post {result = true ↔ (∃i : Z)(0 ≤ i < |s| ∧L s[i ] = x)}
}
I ¿Cómo podemos buscar un elemento en una secuencia?
2
Búsqueda lineal
s[0] s[1] s[2] s[3] s[4] . . . s[|s| − 1]
= x? 6= x = x? 6= x = x? 6= x = x? 6= x = x? 6= x
↑ ↑ ↑ ↑ ↑
i i i i i
I ¿Qué invariante de ciclo podemos proponer?
I ≡ 0 ≤ i ≤ |s|∧L
(∀j : Z)(0 ≤ j < i →L s[j ] 6= x)
I ¿Qué función variante podemos usar?
fv = |s| − i
3
Búsqueda lineal
I Invariante de ciclo:
I ≡ 0 ≤ i ≤ |s| ∧L (∀j : Z)(0 ≤ j < i →L s[j ] 6= x)
I Función variante:
fv = |s| − i
I ¿Cómo lo podemos implementar en C++?
bool contiene(vector<int> &s, int x) {
int i = 0;
while( i < s.size() && s[i] != x ) {
i=i+1;
}
return i < s.size();
}
I ¿Es la implementación correcto con respecto a la
especificación?
4
Recap: Teorema de corrección de un ciclo
I Teorema. Sean un predicado I y una función fv : V→ Z
(donde V es el producto cartesiano de los dominios de las
variables del programa), y supongamos que I ⇒ def(B). Si
1. PC ⇒ I ,
2. {I ∧ B} S {I},
3. I ∧ ¬B ⇒ QC ,
4. {I ∧ B ∧ v0 = fv} S {fv < v0},
5. I ∧ fv ≤ 0⇒ ¬B,
... entonces la siguiente tripla de Hoare es válida:
{PC} while B do S endwhile {QC}
5
Búsqueda lineal
I Para este programa, tenemos:
I PC ≡ i = 0,
I QC ≡ (i < |s|)↔ (∃j : Z)(0 ≤ j < |s| ∧L s[j ] = x).
I B ≡ i < |s| ∧L s[i ] 6= x
I I ≡ 0 ≤ i ≤ |s| ∧L (∀j : Z)(0 ≤ j < i →L s[j ] 6= x)
I fv = |s| − i
I Ahora tenemos que probar que:
1. PC ⇒ I ,
2. {I ∧ B} S {I},
3. I ∧ ¬B ⇒ QC ,
4. {I ∧ B ∧ v0 = fv} S {fv < v0},
5. I ∧ fv ≤ 0⇒ ¬B,
6
Recap: Teorema de corrección de un ciclo
1. PC ⇒ I ,
2. {I ∧ B} S {I},
3. I ∧ ¬B ⇒ QC ,
4. {I ∧ B ∧ v0 = fv} S {fv < v0},
5. I ∧ fv ≤ 0⇒ ¬B,
En otras palabras, hay que mostrar que:
I I es un invariante del ciclo (punto 1. y 2.)
I Se cumple la postcondición del ciclo a la salida del ciclo
(punto 3.)
I La función variante es estrictamente decreciente (punto 4.)
I Si la función variante alcanza la cota inferior la guarda se deja
de cumplir (punto 5.)
7
Corrección de búsqueda lineal
¿I es un invariante del ciclo?
I ≡ 0 ≤ i ≤ |s| ∧L (∀j : Z)(0 ≤ j < i →L s[j ] 6= x)
I La variable i toma el primer valor 0 y se incrementa por cada
iteración hasta llegar a |s|.
I ⇒ 0 ≤ i ≤ |s|
I En cada iteración, todos los elementos a izquierda de i son
distintos de x
I ⇒ (∀j : Z)(0 ≤ j < i →L s[j ] 6= x)
8
Corrección de búsqueda lineal
¿Se cumple la postcondición del ciclo a la salida del ciclo?
I ≡ 0 ≤ i ≤ |s| ∧L (∀j : Z)(0 ≤ j < i →L s[j ] 6= x)
QC ≡ (i < |s|)↔ (∃i : Z)(0 ≤ i < |s| ∧L s[i ] = x)
I Al salir del ciclo, no se cumple la guarda. Entonces no se
cumple i < |s| o no se cumple s[i ] 6= x
I Si no se cumple i < |s|, no existe ninguna posición que
contenga x
I Si no se cumple s[i ] 6= x , existe al menos una posición que
contiene a x
9
Corrección de búsqueda lineal
¿Es la función variante estrictamente decreciente?
fv = |s| − i
I En cada iteración, se incremente en 1 el valor de i
I Por lo tanto, en cada iteración se reduce en 1 la función
variante.
10
Corrección de búsqueda lineal
¿Si la función variante alcanza la cota inferior la guarda se deja de
cumplir?
fv = |s| − i
B ≡ i < |s| ∧L s[i ] 6= x
I Si fv = |s| − i ≤ 0,entonces i ≥ |s|
I Como siempre pasa que i ≤ |s|, entonces es cierto que i = |s|
I Por lo tanto i < |s| es falso.
11
Corrección de búsqueda lineal
I Finalmente,ahora que probamos que:
1. PC ⇒ I ,
2. {I ∧ B} S {I},
3. I ∧ ¬B ⇒ QC ,
4. {I ∧ B ∧ v0 = fv} S {fv < v0},
5. I ∧ fv ≤ 0⇒ ¬B,
I ...podemos por el teorema concluir que el ciclo termina y es
correcto.
12
Búsqueda lineal
I Implementación:
bool contiene(vector<int> &s, int x) {
int i = 0;
while( i < s.size() && s[i] != x ) {
i=i+1;
}
return i < s.size();
}
I Analicemos cuántas veces va a iterar este programa:
s x # iteraciones
〈〉 1 0
〈1〉 1 0
〈1, 2〉 2 1
〈1, 2, 3〉 4 3
〈1, 2, 3, 4〉 4 3
〈1, 2, 3, 4, 5〉 -1 5
13
Búsqueda lineal
I ¿De qué depende cuántas veces se ejecuta el ciclo? Esto
depende de
I El tamaño de la secuencia
I Si el valor buscado está o no contenido en la secuencia
I ¿Qué tiene que pasar para que el tiempo de ejecución sea el
máximo posible?
I El elemento no debe estar contenido.
I Esto representa el peor caso en tiempo de ejecución.
14
Complejidad computacional
Definición. La función de complejidad de un algoritmo es una
función f : N→ R≥0 tal que f (n) es la cantidad de operaciones
elementales que realiza el algoritmo en el peor caso para una
entrada de tamaño n.
Algunas observaciones:
1. Medimos la cantidad de operaciones elementales en lugar del
tiempo total.
2. Nos interesa el peor caso (el que genera la mayor cantidad de
operaciones elementales) del programa.
3. El tiempo de ejecución se mide en función del tamaño de la
entrada y no de la entrada particular.
15
Notación “O grande”
Definición. Si f y g son dos funciones, decimos que f ∈ O(g) si
existen c ∈ R y n0 ∈ N tales que
f (n) ≤ c g(n) para todo n ≥ n0.
Intuitivamente, f ∈ O(g) si g(n) “le gana” a f (n) para valores
grandes de n.
Ejemplos:
I Si f (n) = n y g(n) = n2, entonces f ∈ O(g).
I Si f (n) = n2 y g(n) = n, entonces f 6∈ O(g).
I Si f (n) = 100n y g(n) = n2, entonces f ∈ O(g).
I Si f (n) = 4n2 y g(n) = 2n2, entonces f ∈ O(g) (y a la
inversa).
16
Complejidad computacional
Utilizamos la notación “O grande” para expresar la función de
complejidad computacional f de un algoritmo.
I Si f ∈ O(n) (y f 6∈ O(1)) decimos que el programa es lineal.
I Si f ∈ O(n2) (y f 6∈ O(n)) decimos que el programa es
cuadrático.
I Si f ∈ O(n3) (y f 6∈ O(n2)) decimos que el programa es
cúbico.
I En general, si f ∈ O(nk), decimos que el programa es
polinomial.
I Si f ∈ O(2n) o similar, decimos que el programa es
exponencial.
La búsqueda lineal tiene un tiempo de ejecución (de peor caso)
perteneciente O(n). Decimos también “el algoritmo es O(n)”. ¿Se
puede dar un algoritmos de búsqueda más eficiente?
17
Búsqueda sobre secuencias ordenadas
I Supongamos ahora que la secuencia está ordenada.
I proc contieneOrdenada(in s : seq〈Z〉, in x : Z, out result :
Bool){
Pre {ordenado(s)}
Post {result = true ↔ (∃i : Z)(0 ≤ i < |s| ∧L s[i ] = x)}
}
I ¿Podemos aprovechar que la secuencia está ordenada para
crear un programa más eficiente ?
18
Búsqueda sobre secuencias ordenadas
Podemos interrumpir la búsqueda tan pronto como verificamos que
s[i ] ≥ x .
bool contieneOrdenada(vector<int> &s, int x) {
int i = 0;
while( i < s.size() && s[i] < x ) {
i=i+1;
}
return (i < s.size() && s[i] == x);
}
¿Cuál es el tiempo de ejecución de peor caso?
19
Búsqueda sobre secuencias ordenadas
I Podemos interrumpir la búsqueda tan pronto como
verificamos que s[i ] ≥ x .
Función contieneOrdenado Texec máx.# veces
int i = 0; c ′1 1
while( i < s.size() && s[i] < x ) { c ′2 1 + |s|
i=i+1; c ′3 |s|
}
return (i < s.size() && s[i] == x); c ′4 1
I Sea n la longitud de s, ¿cuál es el tiempo de ejecución en el
peor caso?
TcontieneOrdenado(n) = 1 ∗ c ′1 + (1 + n) ∗ c ′2 + n ∗ c ′3 + 1 ∗ c ′4
I ¿A qué O grande pertenece la función TcontieneOrdenado(n)?
TcontieneOrdenado(n) ∈ O(n)
20
Búsqueda sobre secuencias
I Tcontiene(n) ∈ O(n)
I TcontieneOrdenado(n) ∈ O(n)
I El tiempo de ejecución de peor caso de contiene y
contieneOrdenado está acotado por la misma función c ∗ n.
I Entonces ambas funciones crecen a la misma velocidad
I Abuso de notación: podemos decir que ambos programas
tienen el “mismo” tiempo de ejecución de peor caso
21
Búsqueda sobre secuencias ordenadas
I ¿Podemos aprovechar el ordenamiento de la secuencia para
mejorar el tiempo de ejecució de peor caso?
I ¿Necesitamos iterar si |s| = 0? Trivialmente, x 6∈ s
I ¿Necesitamos iterar si |s| = 1?Trivialmente,
s[0]== x ↔ x ∈ s
I ¿Necesitamos iterar si x < s[0]? Trivialmente, x 6∈ s
I ¿Necesitamos iterar si x ≥ s[|s| − 1]? Trivialmente,
s[|s| − 1] == x ↔ x ∈ s
22
Búsqueda sobre secuencias ordenadas
Asumamos por un momento que |s| > 1 ∧L (s[0] ≤ x ≤ s[|s| − 1])
↑ ↑
low high
?
↑ ↑ ↑
low mid high
≤ x ≤ x ≤ x ≤ x ≤ x
↑ ↑
low high
23
Búsqueda sobre secuencias ordenadas
≤ x ≤ x ≤ x ≤ x ≤ x ?
↑ ↑ ↑
low mid high
≤ x ≤ x ≤ x ≤ x ≤ x > x > x > x > x
↑ ↑
low high
≤ x ≤ x ≤ x ≤ x ≤ x ? > x > x > x > x
↑ ↑ ↑
low mid high
≤ x ≤ x ≤ x ≤ x ≤ x > x > x > x > x > x
↑ ↑
low high
Si x ∈ s, tiene que estar en la posición low de la secuencia.
24
Búsqueda sobre secuencias ordenadas
≤ x ≤ x ≤ x ≤ x ≤ x > x > x > x > x > x
↑ ↑
low high
I ¿Qué invariante de ciclo podemos escribir?
I ≡ 0 ≤ low < high < |s| ∧L s[low ] ≤ x < s[high]
I ¿Qué función variante podemos definir?
fv = high − low − 1
25
Búsqueda sobre secuencias ordenadas
bool contieneOrdenada(vector<int> &s, int x) {
// casos triviales
if (s.size()==0 ) {
return false;
} else if (s.size()==1) {
return s[0]==x;
} else if (x<s[0]) {
return false;
} else if (x≥s[s.size()−1]) {
return s[s.size()−1]==x;
} else {
// casos no triviales
◦ ..
}
}
26
Búsqueda sobre secuencias ordenadas
} else {
// casos no triviales
int low = 0;
int high = s.size() − 1;
while( low+1 < high ) {
int mid = (low+high) / 2;
if( s[mid] ≤ x ) {
low = mid;
} else {
high = mid;
}
}
return s[low] == x;
}
}
A este algoritmo se lo denomina búsqueda binaria
27
Búsqueda binaria
I Veamos ahora que este algoritmo es correcto.
PC ≡ ordenada(s) ∧ (|s| > 1 ∧L s[0] ≤ x ≤ [|s| − 1])
∧ low = 0 ∧ high = |s| − 1
QC ≡ (s[low ] = x)↔ (∃i : Z)(0 ≤ i < |s| ∧L s[i ] = x)
B ≡ low + 1 < high
I ≡ 0 ≤ low < high < |s| ∧L s[low ] ≤ x < s[high]
fv = high − low − 1
28
Corrección de la búsqueda binaria
I ¿Es I un invariante para el ciclo?
I El valor de low es siempre menor estricto que high
I low arranca en 0 y sólo se aumenta
I high arranca en |s| − 1 y siempre se disminuye
I Siempre se respecta que s[low ] ≤ x y que x < s[high]
I ¿A la salida del ciclo se cumple la postcondicion QC?
I Al salir, se cumple que low + 1 = high
I Sabemos que s[high] > x y s[low ] <= x
I Como s está ordenada, si x ∈ s, entonces s[low ] = x
29
Corrección de la búsqueda binaria
I ¿Es la función variante estrictamente decreciente?
I Nunca ocurre que low = high
I Por lo tanto, siempre ocurre que low < mid < high
I De este modo, en cada iteración, o bien high es estrictamente
menor, o bien low es estrictamente mayor.
I Por lo tanto, la expresión high − low − 1 siempre es
estrictamente menor.
I ¿Si la función variante alcanza la cota inferior la guarda se
deja de cumplir?
I Si high − low − 1 ≤ 0, entonces high ≤ low + 1.
I Por lo tanto, no se cumple (high > low + 1), que es la guarda
del ciclo
30
Búsqueda binaria
I ¿Podemos interrumpir el ciclo si encontramos x antes de
finalizar las iteraciones?
I Una posibilidad no recomendada (no lo hagan en casa!):
I ◦ ..
while( low+1 < high) {
int mid = (low+high) / 2;
if( s[mid] < x ) {
low = mid;
} else if( s[mid] > x ) {
high = low;
} else {
return true; // Argh!
}
}
return s[low] == x;
}
31
Búsqueda binaria
I Una posibilidad aún peor (ni lo intenten!):
I bool salir = false;
while( low+1 < high && !salir ) {
int mid = (low+high) / 2;
if( s[mid] < x ) {
low = mid;
} else if( s[mid] > x ) {
high = mid;
} else {
salir = true; // Puaj!
}
}
return s[low] == x || s[(low+high)/2] == x;
}
32
Búsqueda binaria
I Si queremos salir del ciclo, el lugar para decirlo es ...
la guarda!
I while( low+1 < high && s[low] != x ) {
int mid = (low+high) / 2;
if( s[mid] ≤ x ) {
low = mid;
} else {
high = mid;
}
}
return s[low] == x;
}
I Usamos fuertemente la condición s[low ] ≤ x < s[high] del
invariante.
33
Búsqueda binaria
I ¿Cuántas iteraciones realiza el ciclo (en peor caso)?
Número de
iteración
high − low
0 |s| − 1
1 ∼= (|s| − 1)/2
2 ∼= (|s| − 1)/4
3 ∼= (|s| − 1)/8
...
...
t ∼= (|s| − 1)/2t
I Sea t la cantidad de iteraciones necesarias para llegar a
high − low = 1.
1 = (|s|−1)/2t entonces 2t = |s|−1 entonces t = log2(|s|−1).
Luego, el tiempo de ejecución de peor caso de la búsqueda binaria
es O(log2 |s| − 1) = O(log2 |s|) .
34
Búsqueda binaria
I ¿Es mejor un algoritmo que ejecuta una cantidad logaŕıtmica
de iteraciones?
Búsqueda Búsqueda
|s| Lineal Binaria
10 10 4
102 100 7
106 1, 000, 000 21
2,3× 107 23, 000, 000 25
7× 109 7, 000, 000, 000 33 (!)
I Śı! Búsqueda binaria es más eficiente que búsqueda lineal
I Pero, requiere que la secuencia esté ya ordenada.
35
Bibliograf́ıa
I David Gries - The Science of Programming
I Chapter 16 - Developing Invariants (Linear Search, Binary
Search)
I Cormen et al. - Introduction to Algorithms
I Chapter 2.2 -Analyzing algorithms
I Chapter 3 - Growth of Functions
36