Lenguaje C

Semana 7

Clase 12
 Agenda

1 Búsqueda 2 Recursividad
Búsqueda
★ La búsqueda es la manera en la que resolvemos el problema de
buscar información. Un problema simple tiene una entrada de
ciertos valores, y una salida de un bool, dependiendo si un valor se
encontró o no.
★ A esto le conoceremos como algoritmos de búsqueda y para
comparar su eficiencia, vamos a considerar su tiempo de ejecución,
o cuánto tiempo toma un algoritmo en ejecutarse dada cierta
entrada; así que antes de continuar, recordemos un poco de
complejidad computacional.
★ Los científicos computacionales suelen describir el tiempo de
ejecución con la notación gran O, lo podemos pensar cómo “en
orden de” algo, queremos dar la idea de tiempo de ejecución y no
un número exacto de milisegundos o de pasos.
★ Recordemos el ejemplo visto en la primera semana, en donde buscábamos
un número en una agenda telefónica.

Recuerda que la línea roja

representa la búsqueda lineal, una
página a la vez, la línea amarilla
representa buscar dos páginas a la
vez, y la línea verde es dividir y
conquistar, empezamos en el
medio y dividimos el problema a
la mitad cada vez.
Usamos la gran notación O, para describir tanto la línea roja cómo la amarilla,
estas terminan siendo muy similares cada vez que “n” se hace más y más largo.

Pero, la línea verde, es

fundamentalmente distinta en su
forma, incluso si n se vuelve muy
largo, va tomar “Gran O de log n”
pasos.
★ Los científicos computacionales también suelen usar big 𝛀,
notación gran Omega, la cual describe la menor cantidad de pasos
que toma el algoritmo en el mejor de los casos. En gran notación O,
cuando decimos “en orden de”, contamos la mayor cantidad de
pasos que un algoritmo va tomar en el peor de los casos.

★ Finalmente, hay otra notación, Θ (theta), la cual usaremos para

describir el tiempo de ejecución de un algoritmo si la cantidad de
pasos que toma es igual.
Ahora, volvamos al tema principal…
★ Supongamos que tenemos siete casilleros con sus puertas cerradas,
con números escondidos detrás de ellas. Debido a que las
computadoras sólo pueden ver un elemento a la vez, solo podemos
abrir una puerta a la vez.

★ Si queremos buscar el número cero, vamos a tener que abrir una puerta
a la vez, y si no supiéramos nada acerca de los números detrás de las
puertas, el algoritmo más sencillo sería empezar a revisar de izquierda
a derecha.
Este algoritmo, “búsqueda lineal”, sería correcto pero no muy eficiente. El
pseudocódigo se vería así:

Por cada puerta de izquierda a derecha

Si el número está detrás de la puerta
Return true
Return false

El return false está fuera del ciclo, debido a que queremos hacer
eso solo si ya revisamos todas las puertas.
Podemos escribir nuestro pseudocódigo para que sea más cercano a C:

For i from 0 to n-1

If número detrás puertas[i]
Return true
Return false

-> El tiempo de ejecución gran O para este algoritmo va ser O(n).

-> La menor cantidad de pasos, gran Omega, sería 𝛀(1), debido a que
podemos encontrar el número que estamos buscando enseguida.
★ Si sabemos que los números detrás de las puertas están ordenados,
entonces, podemos empezar en el medio, y encontrar nuestro valor
de manera más eficaz, debido a que sabemos que podemos ir
derecha o izquierda, dividiendo el problema a la mitad cada vez. A
esto le conoceremos como búsqueda binaria.
Para la “búsqueda binaria”, el pseudocódigo para nuestro algoritmo se
vería así:

Si no hay puertas
Return false
Si número detrás la puerta del medio
Return true
Else if numero < puerta del medio
Busca la parte izquierda
Else if numero > puerta del medio
Busca la parte derecha
Podemos escribir este pseudocódigo para que sea más cómo C:

If no puertas
Return false
If número detrás puertas[medio]
Return true
Else if número < puertas[medio]
Busca puertas[0] hasta puertas[medio - 1]
Else if número > puertas[medio]
Busca puertas[medio + 1] hasta puertas[n - 1]
★ El peor de los casos para búsqueda es O(log n), debido a que es
posible que tengamos que dividir el número de puertas entre dos
hasta que ya no haya más puertas. El mejor de los casos 𝛀(1) es que
el número que estemos buscando se encuentre directamente en el
medio.

★ Aunque la búsqueda binaria es mucho más rápida que la búsqueda

lineal, nuestro arreglo tiene que estar ordenado primero.
Si queremos verificar strings, recordemos que debemos usar strcmp para
comparar cadenas.

argv.c

for (int i = 0; i < 7; i++) {

if (strcmp(names[i], "David") == 0) {
printf("Found %s\n", numbers[i]);
return 0;
}
}
printf("Not found\n");
return 1;
Recursividad
★ La recursión es la habilidad que tiene una función para llamarse a sí
misma. No hemos visto esto en código todavía, pero vimos el
pseudocódigo para la búsqueda binaria:
Si no hay puertas
Return false
Si el número está en la puerta del medio
Return true
Else if número < puerta del medio
Busca en el lado izquierdo
Else if número > puerta del medio
Busca en el lado derecho
★ Usamos el mismo algoritmo de “Buscar” para cada mitad. Esto
parece un proceso cíclico que nunca va terminar, pero realmente le
estamos cambiando la entrada a la función y dividiendo el
problema a la mitad cada vez, parando una vez ya no haya más
puertas que abrir.
Veamos el tema de una forma más sencilla, antes, implementamos una
“pirámide” de bloques con la siguiente forma:

argv.c

void draw(int n)
{
#
for (int i = 0; i < n; i++) { ##
for (int j = 0; j < i + 1; j++) {
printf("#");
###
} ####
printf("\n");
}
}
★ Debido a que una pirámide es una estructura recursiva, podemos
escribir una función recursiva para dibujar la imagen, una función
que se llama a sí misma para dibujar una versión más pequeña de la
imagen antes de añadir otra fila.
argv.c

void draw(int n)
{
if (n <= 0) {
return;
}
draw(n - 1);
for (int i = 0; i < n; i++) {
printf("#");
}
printf("\n");
}
★ Podemos reescribir nuestra función draw para que se use a sí
misma.
★ Si n es 0 o negativo pararemos sin imprimir nada. Tenemos que
asegurarnos que va parar para tener nuestro caso base, sino la
función se va a llamar a sí misma una y otra vez.
★ Si la entrada es válida, llamaremos a draw de nuevo, para imprimir
una pirámide de tamaño n - 1.
★ Luego, imprimimos la fila de bloques que necesitamos para nuestra
pirámide de tamaño n.
Veamos otro ejemplo:

factorial.c

long factorial(int n)
{
if (n == 0) // Caso base
{
return 1;
}
else
{
return n * factorial(n - 1);
}
}
Supongamos que queremos calcular 5!, el cual se puede subdividir de la
siguiente manera:

factorial(1) 1

factorial(2) 2 * factorial(1)

factorial(3) 3 * factorial(2)

factorial(4) 4 * factorial(3)

factorial(5) 5 * factorial(4)

Donde cada llamada a la función retornará un valor a la

llamada anterior.
★ Ahora, podemos tomar la idea de recursión y usarla para ordenar,
usaremos otro algoritmo llamado ordenamiento por mezcla. El
pseudocódigo se ve:

Si solo hay un número

Salir
Else
Ordena el lado izquierdo del número
Ordena el lado derecho del número
Mezcla ambas mitades
★ Nuestra estrategia será la de ordenar cada mitad, y luego mezclarlas
juntas. Empecemos con dos mitades ordenadas que se miran así:

2 4 5 7 0 1 3 6

0 2 4 5 7 1 3 6
0 1 2 4 5 7 3 6

0 1 2 4 5 7 3 6

0 1 2 3 4 5 7 6
0 1 2 3 4 5 7 6

0 1 2 3 4 5 7 6

0 1 2 3 4 5 6 7
★ Cada vez que mezclamos dos mitades, solo necesitamos ver a cada
número una sola vez. Dividimos nuestra lista de ocho números tres
veces, o log(n) veces. Necesitamos más memoria para mezclar
nuestras nuevas listas, pero, el tiempo de ejecución en el peor de
los casos para este ordenamiento es de O(n log n).

★ El tiempo de ejecución en el mejor de los casos sigue siendo 𝛀(n

log n), ya que debemos hacer todo el trabajo incluso si la lista está
ordenada. Entonces el ordenamiento por mezcla también (n log n).
¿Preguntas?