La definición de [matemáticas] T (n) [/ matemáticas] en la pregunta es:
[matemáticas] T (n) = T (n – 2) + n [/ matemáticas]
y además asumo [matemáticas] T (1) = 1 [/ matemáticas] y [matemáticas] T (0) = 0 [/ matemáticas] como casos base.
- ¿Cuál es el mejor algoritmo de clasificación para alfabetizar físicamente mi colección de libros?
- ¿Aprender la construcción del compilador mejora la habilidad / visión de resolución de problemas de programación? ¿Si es así, cómo? ¿O por qué no?
- ¿Cuál es un ejemplo de un árbol binario roscado?
- ¿Cuál es el enfoque algorítmico para invertir un árbol binario dado?
- ¿Cuáles son los 5 mejores algoritmos esenciales (excepto la clasificación) que todo programador debe saber?
Como [math] T (n) [/ math] se define solo en términos de un solo término anterior [math] T (n – 2) [/ math], el árbol de recurrencia será como una “cadena”.
Se verá así:
[matemáticas] n \ leftarrow (n – 2) \ leftarrow (n – 4) \ leftarrow \ cdots \ leftarrow (n – 2k) \ leftarrow \ cdots \ leftarrow 2 \ leftarrow 0 [/ math]
(suponiendo que [math] n [/ math] es par), pero se dibuja de arriba a abajo en lugar de de izquierda a derecha.
Esto se debe a que cada nodo en el árbol de recurrencia representa los “términos adicionales” agregados a [math] T (k) [/ math] para calcular su valor (de acuerdo con la definición de la función [math] T [/ math ]), después de sustituir los valores de sus subárboles secundarios. Cada subárbol hijo representa un término precedente ([matemáticas] T (j), \, \, j <k [/ matemáticas]) involucrado en el cálculo de [matemáticas] T (k) [/ matemáticas].
En este caso, habrá un solo subárbol hijo para cada nodo [matemática] T (k) [/ matemática], que dará el valor de [matemática] T (k – 2) [/ matemática].
Este árbol te dice de inmediato que:
[matemáticas] T (n) = 2 + 4 + \ ldots + n = 2 \ left (1 + 2 + \ ldots + \ dfrac {n} {2} \ right) = \ dfrac {n} {2} \ left (\ dfrac {n} {2} + 1 \ right) = \ Theta (n ^ 2) [/ math]
