Resolviendo una ecuación de recurrencia con dos variables
Tengo esta función que recorre cada nodo de un árbol binario hijo-hermano derecho una vez y quiero resolver la relación de recurrencia de la función.
En primer lugar, creo que la relación se ve así:
T(n) = 1+m[4+T(n-m)] = 1+4m+mT(n-m)
Donde m es el número de nodos en un nivel y n es el número total de nodos en el árbol.
¿Es esto correcto? ¿Y cómo puedo resolver esta relación de recurrencia con dos variables?
void maxWidth(Node node, int height, vector<int>& width){
if(node==nullptr){
return;
}
while(node!=nullptr){
if(width.size()==height){
width.push_back(0);
}
if(width.size()>height){
width[height]=width[height]+1;
}
if(node->left_child!=nullptr){
maxWidth(node->left_child,height+1,width);
}
node=node->right_sib;
}
}
davy.ai
Para resolver la relación de recurrencia
T(n) = 1+4m+mT(n-m), podemos utilizar el método del árbol recursivo. En este método, creamos un árbol de recursión donde cada nivel representa el número de nodos en ese nivel y el costo de cada nivel es el costo total de todos los nodos en ese nivel. El costo total del algoritmo es la suma de los costos de todos los niveles.Supongamos que la raíz del árbol binario tiene n nodos. En el primer nivel, hay solo un nodo (la raíz), por lo que el costo es 1. En el segundo nivel, hay m nodos (los hijos de la raíz) y cada nodo requiere un tiempo constante de 4. Por lo tanto, el costo del segundo nivel es 4m. En el tercer nivel, nuevamente hay m nodos y cada nodo requiere un tiempo de T(n-m) para recorrer su subárbol. Entonces, el costo del tercer nivel es mT(n-m).
Podemos continuar este proceso hasta llegar al nivel inferior (que tiene 0 nodos). El costo total del algoritmo es la suma de los costos de todos los niveles:
T(n) = 1 + 4m + mT(n-m) + 4m + mT(n-2m) + ... + 4m + mT(n-(h-1)m)donde h es la altura del árbol (el número de niveles).
Para simplificar esta expresión, podemos factorizar el término común de 4m:
T(n) = 1 + 4m(h-1) + m(T(n-m) + T(n-2m) + ... + T(n-(h-1)m))Podemos simplificar el segundo término utilizando la identidad:
T(a) + T(ar) + T(ar^2) + ... + T(ar^(k-1)) = (1-r^k)/(1-r) * T(a)donde a es el valor inicial, r es la razón común y k es el número de términos.
En nuestro caso, a = n-m, r = m/n y k = h-1. Entonces tenemos:
T(n) = 1 + 4m(h-1) + m((1-(m/n)^(h-1))/(1-(m/n))) * T(m)donde T(m) es el tiempo necesario para procesar un subárbol de tamaño m (lo cual es una constante). Podemos simplificar aún más al observar que:
(1-(m/n)^(h-1))/(1-(m/n))es una serie geométrica, y utilizando la fórmula para la suma de una serie geométrica, obtenemos:
T(n) = 1 + 4m(h-1) + m((n/m)^h - 1)/(n/m - 1) * T(m)Esta es la solución cerrada para la relación de recurrencia. Expresa el tiempo necesario para procesar un árbol binario con n nodos en función del tiempo necesario para procesar un subárbol de tamaño m (lo cual es una constante), la altura del árbol y el número de nodos en cada nivel (que depende de la altura).
Para utilizar esta fórmula en la práctica, necesitamos determinar el valor de m (el número de nodos en cada nivel) y luego calcular el valor de T(n) utilizando la fórmula. Podemos determinar m observando que el árbol binario es un árbol de hijo izquierdo-hermano derecho, lo que significa que cada nodo tiene como máximo un hijo (el hijo izquierdo) y cualquier descendiente adicional son sus hermanos. Por lo tanto, el número de nodos en cada nivel es igual al número de hermanos de los nodos en el nivel anterior (si los hay). El número de hermanos de la raíz es n-1, el número de hermanos de los hijos de la raíz es n-2, y así sucesivamente. Por lo tanto, el número de nodos en el nivel i es n-i.
Utilizando esta observación, podemos calcular el valor de m para la fórmula:
m = max(n-i : 1 <= i <= h)donde h es la altura del árbol. Al reemplazar este valor de m en la fórmula, obtenemos la solución cerrada para la relación de recurrencia.