Divide y vencerás en C: máximo, suma, búsqueda binaria y recurrencias

​

Lo que vas a aprender

• El esquema general de divide y vencerás.
• Cómo se aplica a vectores dividiendo por la mitad.
• La búsqueda binaria.
• Calcular el coste con ecuaciones de recurrencia.
• Cuándo compensa y cuándo no.

​

Cómo se usa el simulador

• Elige el problema: máximo, suma, ¿creciente? o búsqueda binaria.
• Datos: número de elementos (2 – 16) y disposición: aleatorio, creciente o casi creciente. 🎲 Nuevos datos genera otros.
• Avanza con ⏮, ◀, ▶ Ejecutar, ▶ y ⏭.
• Se resalta el trozo del vector que trata cada llamada y su mitad, la línea del código en C y el árbol de subproblemas. Los contadores dan las llamadas, las comparaciones y el tamaño de la pila.
• Cómo funciona muestra la ecuación de recurrencia y su solución.

​

Fundamentos teóricos

​

El esquema

resolver(problema):
    si es trivial: devolver su solución directa
    dividir en subproblemas más pequeños
    resolver cada subproblema (recursivamente)
    combinar las soluciones

​

Con vectores

int maximo(int V[], int ini, int fin) {
    if (ini == fin) return V[ini];            // caso trivial
    int mitad = (ini + fin) / 2;              // dividir
    int izq = maximo(V, ini, mitad);          // resolver
    int der = maximo(V, mitad + 1, fin);
    return izq > der ? izq : der;             // combinar
}

​

Búsqueda binaria

​

Ecuaciones de recurrencia

• Si $a < b^k$: $O(n^k)$.
• Si $a = b^k$: $O(n^k\log n)$.
• Si $a > b^k$: $O(n^{\log_b a})$.

​

¿Cuándo compensa?

​

Ejemplos resueltos

​

Experimenta con el simulador

​

Errores frecuentes

• Calcular mal la mitad y dejar trozos vacíos o solapados.
• Olvidar el caso trivial.
• Aplicar búsqueda binaria a un vector desordenado.

​

Herramientas relacionadas