estoy en un poco de un atasco en busca de la fórmula de recurrencia de este método javaSe busca: fórmula de recurrencia del método de salida árbol binario Dentro de la Orden de
void printInorder(Node<T> v) {
if(v != null) {
printInorder(v.getLeft());
System.out.println(v.getData());
printInorder(v.getRight());
}
}
Algunos criterios:
- su un árbol binario completo (cada nudo interior tiene 2 hijos, cada hoja tiene la misma profundidad)
- el árbol tiene n nudos y una complejidad de O (n)
Tengo que encontrar la fórmula de recurrencia en relación con el depth h del árbol con n knots, y como una ventaja adicional, necesito extrapolar la fórmula explícita que conduce a O (n) de eso.
Ahora bien, esto es lo que tengo:
d = depth of the tree
c = constant runtime for execution of the method itself
d = 1: T(n) = c
d = 3: T(n) = T(d=1) + T(d=2) + T(d=3) + c
he usado el ejemplo d = 3 para aclarar las cosas por mí mismo, estoy teniendo dificultades para romper este abajo más lejos. ¿Mi suposición es incluso correcta?
Editar: Siguiente intento de cosas
[x] = { x in real numbers : max([x]) <= x }, [x] rounded down to next full number
d = 1: T(d) = 1
d > 1: T(d) = 2^(h-1) * T(n/(2^(h-1)))
1: T(h) = T(i = 0) + T(i = 1) + ... T(i = h-1)
2: T(h) <= (2^(0-1) + n/(2^(0-1))) + (2^(1-1) + n/(2^(1-1))) + ... + (2^(h-2) + n/(2^(h-2)))
3: T(h) = n + n + ... + n
4: T(h) = (h-1)n
5: T(h) = O(n)
Debido a que cada nivel de profundidad del árbol contiene exactamente 2^(h-1) nodos, el factor h en la línea 4 puede ser ignorado porque n es más relevante para el resultado final.
