← Volver a los ejercicios

árbol: partir el problema en dos

Hasta aquí las funciones bajaban de una en una. Esta parte el rango por la mitad y se llama dos veces, y el proceso deja de ser una fila para volverse un árbol. Se dibuja un nodo por paso, en el orden en que las llamadas ocurren: primero la rama izquierda hasta el fondo, después la derecha.

1. Antes de ejecutar, prediga

Llamada de partida:
¿Cuántas llamadas a producto se hacen en total?
Y como máximo, ¿cuántos marcos quedan abiertos al mismo tiempo?

2. Ejecute: el árbol a la izquierda, la pila a la derecha

marco abierto cerrado, con su valor camino de la pila todavía no se ha llamado
Marcos abiertos ahora, el más nuevo arriba:
Paso 0 de 0
Cada llamada da dos pasos: uno al entrar, que abre su marco, lo pinta de amarillo y le pone el número de orden en que se abrió; y otro al salir, que lo cierra y lo pinta de verde con su valor. La rama gruesa es el camino de la raíz al marco actual: exactamente lo que hay en la pila de la derecha, con los mismos números. Cada marco abierto dice qué está esperando.

3. Lo que se lleva de aquí

Para n números hay n hojas y n − 1 nodos que parten: 2n − 1 llamadas. Es más que las n + 1 de la versión lineal, así que en tiempo no se ganó nada.

Lo que cambió es cuántas de esas llamadas están abiertas a la vez. La versión lineal las abre todas antes de cerrar la primera: n + 1 marcos. El árbol cierra la rama izquierda entera antes de abrir la derecha, así que en la pila nunca hay más que un camino de la raíz a una hoja: tantos marcos como niveles, ⌈log₂ n⌉ + 1. Para n = 1024, once en vez de mil y veinticinco.

Las dos predicciones dan números distintos porque miden cosas distintas: las llamadas son el tiempo, los marcos abiertos al tiempo son el espacio.

El siguiente ejercicio pone los tres procesos en una tabla, para compararlos con los mismos números.

Ir a cuentas: tres procesos, una tabla →