Recurencia

8

Nota: esto es de las notas de Algoritmos de JeffE sobre Recurrencias, página 5.

(1) Entonces definimos la recurrenciaT(n)=nT(n)+nSin ningún caso base. Ahora entiendo que para la mayoría de las recurrencias, dado que estamos buscando límites asintóticos, el caso base no importaría. Pero en este caso, ni siquiera veo dónde podríamos definir el caso base. ¿Hay algún número que tengamos éxito para garantizar que seguimos tomando raíces cuadradas a partir de cualquier número entero?T(n)=a para n<b, para algunos reales a, b?

(2) En la página 7, Erickson entiende que la cantidad de capas en el árbol de recursión L satisfarán2L=2. ¿De dónde viene esto? No tengo idea. Veo que el número de hojas en el árbol debería sumar(n)(n)=norte, pero no tengo idea de a dónde ir desde allí.

Cualquier ayuda es apreciada!

Notas que estoy viendo: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf

DB Cooper
fuente

Respuestas:

7

Realmente deberías hacerte una tercera pregunta: ¿qué sucede si norteNo es un cuadrado perfecto. La respuesta a esta pregunta es que la recurrencia real debería tenerT(norte) o T(norte) en vez de T(norte), aunque en el análisis solo consideraremos las entradas que son cuadrados "recursivos".

Con respecto a su primera pregunta, puede haber más de un caso base. Por ejemplo, tal vezT(norte)=1 para todos norte100. Le garantizamos que eventualmente llegará a este caso base. En este caso, como en la mayoría de los casos, la forma exacta del caso base no afecta a las grandes asintóticas Theta (pero sí afecta a la constante oculta).

Finalmente, con respecto a su segunda pregunta, suponga que su caso base especifica T(norte) para norteC. El árbol de recursión (que es una interpretación particular de algunas características de la recurrencia) tiene la siguiente forma:

  • La raíz es una instancia de tamaño norte.
  • La raíz tiene norte niños que son instancias de tamaño norte.
  • Cada nodo en la profundidad 1 tiene norte=norte1/ /4 4 niños que son instancias de tamaño norte=norte1/ /8.
  • Más generalmente, un nodo en profundidad re es una instancia de tamaño norte1/ /2re. Puede probar esto por inducción comprobando el casore=0 0 (dónde norte1/ /2re=norte) y calculando norte1/ /2re=norte1/ /2re+1.

La recursión termina cuando la instancia tiene un tamaño como máximo C, y esto sucede cuando norte1/ /2reC. En el momento en que esto sucede, tenemosnorte1/ /2re-1>C (asumiendo norte>C), y entonces C<norte1/ /2reC. Tomando el logaritmo,12Iniciar sesiónC<Iniciar sesiónnorte2re<Iniciar sesiónC y entonces Iniciar sesiónnorte2re=Θ(1), Insinuando 2re=Θ(Iniciar sesiónnorte). Podemos concluir quereIniciar sesiónIniciar sesiónnorte. Este es el número de capas en el árbol. Jeff usaC=2, que es cómo obtiene su fórmula particular.

Yuval Filmus
fuente
4

Respondiendo tu primera pregunta. Alternativa al uso del límite superior y el límite inferior para lograr un caso base, una opción es que podría asumir la forma denorte.

Tomemos, por ejemplo, la fusión recursiva:

T(norte)=2CT(norte2)+Cnorte

Claramente, la mayoría norteno se dividirá equitativamente en enteros. Entonces es bastante común suponer quenorte es de la forma:

norte=2kknorte

Esto implica cada norte es un poder positivo de 2, resolviendo así nuestro caso base siempre 1. Alternativamente, podríamos hacer el caso baseC en vez de 1 asumiendo norte es de la forma:

norte=C2kknorte,Cnorte+

Podemos aplicar esto a nuestra recurrencia:

T(norte)=norteT(norte)+norte

Asumir norte es de la forma:

norte=C2kknorte,Cnorte+
Entonces el caso base siempre se resolverá a una constante C.

Ahora, si puede probarlo bajo esta suposición, podría pasar a hacer una prueba de nortevalores que no tienen este formulario. Un enfoque sería intentar vincularlo con el siguiente más alto (o más bajo)norteque lo hace tener esa forma.

Ryan
fuente