Actualmente, estoy estudiando Introducción a los algoritmos (CLRS) y hay un método particular que describen en el libro para resolver las relaciones de recurrencia.
El siguiente método puede ilustrarse con este ejemplo. Supongamos que tenemos la recurrencia
Inicialmente hacen la sustitución m = lg (n), y luego la conectan nuevamente a la recurrencia y obtienen:
Hasta este punto lo entiendo perfectamente. El siguiente paso es el que me confunde.
Ahora "renombran" la recurrencia y dejan , lo que aparentemente produceS ( m ) = T ( 2 m )
Por alguna razón, no me queda claro por qué funciona este cambio de nombre, y solo parece una trampa. ¿Alguien puede explicar esto mejor?
k
que estoy recibiendo por debajo de la ecuación S (k) = 2S (k / 2) + m ¿Cómo puedo obtener sustitutom
parak
¿Qué medios es que y son dos funciones diferentes que producen el mismo resultado, teniendo entradas como y respectivamente.S T m 2 mS(m)=T(2m) S T m 2m
La función se puede considerar como un operador con dos pasos internos (de lo contrario, composición de funciones):S
Por lo tanto, las transiciones son:
fuente