Resolver la relación de recurrencia de la forma $T(n/2 + c)$

Question

Es obvio que el Teorema Maestro no puede ser aplicado a las recurrencias de la siguiente forma:

$T(n) = 4T(n/2 + 2) + n$

Ya que sólo estoy interesado en el $ \theta $ ligado a la recurrencia y no a la solución exacta, ¿cuál es la mejor manera de abordar este problema?

Answer 1

Un enfoque diferente (al de Rick Decker) es intentar encontrar una función "agradable" que satisfaga esta recurrencia, y luego ver qué variaciones son posibles. Tenemos la relación

$$T(n)=4T(n/2+2)+n$$

y podemos deshacernos de la $2$ por una sustitución variable $n=m+4$ para que

$$T(m+4)=4T(m/2+4)+m+4$$

y podemos cambiar esto a una recurrencia lineal con sustitución $m=2^t$

$$T(2^t+4)=4T(2^{t-1}+4)+2^t+4$$

y eliminar la multiplicación por $4$ con la sustitución $T(2^t+4)=4^tf(t)$

$$f(t)=f(t-1)+2^{-t}+4^{1-t}.$$

Esto parece un exponencial, así que si intentamos (también conocido como ansatz ) la solución $f(t)=A+B2^{-t}+C4^{-t}$ tenemos

$$A+B2^{-t}+C4^{-t}=A+2B2^{-t}+4C4^{-t}+2^{-t}+4 \cdot4 ^{-t}$$ $$(B-2B-1)2^{-t}+(C-4C-4)4^{-t}=0,$$

de donde $B=-2$ y $C=- \frac43 $ . Desenrollando nuestras sustituciones, conseguimos $$t= \lg m= \lg (n-4) \Rightarrow T(m+4)=m^2f( \lg m)=Am^2-2m- \frac43 $$ $$T(n)=A(n-4)^2-2n- \frac {20}3$$

y ya casi hemos terminado. Sin embargo, como esta es una ecuación de recurrencia y no una ecuación diferencial, hay agujeros de comportamiento no especificados entre ellas, y la solución para $f(t)$ no se vería afectada si una función de un solo período $g(t)$ se añadió a ella, así que en su lugar encontramos $T(m+4)=m^2g( \lg m)-2m- \frac43 $ . Si sabemos $T(n)$ es continua, entonces $g(n)$ está limitada, y podemos decir que $T(n)= \Theta (n^2)$ . De lo contrario, una función que no es $ \Theta (n^2)$ y satisface la recurrencia es $T(m+4)=m^2 \tan ( \pi\lg m)-2m- \frac43 $ .

Answer 2

Un enfoque diferente. Pruebe el método del árbol de recursividad (consulte CLRS)
$ T(n)=T(n/2+2)+n$
Usando el árbol conseguimos, en el nivel $i$ la suma como
$4^i c(n/2^i)+ 2*4^i $ parando en $T(3)$ (asumiendo que es un valor constante).
Se detiene cuando $n=2^i$ y por lo tanto $i= \log n$ Por lo tanto, sumando la ecuación de $i=0$ a $i= \log n$ tenemos
$(2^{ \log n} - 1) + (2^{2 \log n}-1)/3 $ que da $ \theta (n^2)$ .

Answer 3

En primer lugar, tenga en cuenta que no hay (casi) ninguna solución a su recurrencia como se ha dicho. Por ejemplo, empezando con $n=7$ tenemos $$ \begin {align} T(7)&=4T(5.5)+7 \\ &=4(4T(4.75)+5.5)+7=16T(4.75)+22+7 \\ &=64T(4.375)+76+22+7 \end {align} $$ Ya te lo imaginas. A medida que continuamos este proceso, los argumentos se acercan a 4 pero nunca llegan a 4, así que a menos que defina $T(x)$ para algunos $x$ en esta secuencia, tendrás un cálculo divergente.

Sin embargo, no todo está perdido, ya que podemos modificar ligeramente su recurrencia a $$ T(n)=4T \left ( \left\lfloor\frac {n}{2} \right\rfloor +2 \right )+n \qquad\qquad\qquad\text {(*)} $$ y observar que tendremos $T(4)=4T( \lfloor4 /2 \rfloor +2)+4=4T(4)+4 \text {, so }T(4)=-4/3$ y podemos detener las llamadas recursivas en $n=4$ . Lo que estoy a punto de hacer puede generalizarse a las recurrencias en las que el argumento es $( \lfloor n/a \rfloor +b)$ pero espero que la respuesta a esta recurrencia en particular sea suficiente.

El truco aquí es calcular $T(2^k)$ para $k>2$ . Primero, considera sólo el argumento para $T$ . Tendremos $$ \begin {align} 2^k&=2^k \\ \left\lfloor\frac {2^k}{2} \right\rfloor +2&=2^{k-1}+2 \\ \left\lfloor\frac {2^{k-1}+2}{2} \right\rfloor +2&=2^{k-2}+1+2 \\ \left\lfloor\frac {2^{k-2}+1+2}{2} \right\rfloor +2&=2^{k-3}+1+2 \\ \left\lfloor\frac {2^{k-3}+1+2}{2} \right\rfloor +2&=2^{k-4}+1+2 \\ \end {align} $$ y así, excepto los dos primeros términos, cada argumento posterior será de la forma $2^{k-j}+3$ . Ahora vamos a expandirnos $T(2^k)$ usando nuestra recurrencia (*) de arriba: $$ \begin {align} T(2^k)&=4T(2^{k-1}+2)+2^k \\ &=4(4T(2^{k-2}+3)+(2^{k-1}+2))+2^k \\ &=4^2T(2^{k-2}+3)+4(2^{k-1}+2)+2^k \\ &=4^2(4T(2^{k-3}+3)+(2^{k-2}+3))+4(2^{k-1}+2)+2^k \\ &=4^3T(2^{k-3}+3)+4^2(2^{k-2}+3)+4(2^{k-1}+2)+2^k \end {align} $$ y a estas alturas el patrón debería estar claro. Tendremos $$ \begin {align} T(2^k)&=4^jT(2^{k-j}+3)+4^{j-1}(2^{k-j+1}+3)+ \cdots +4(2^{k-1}+2)+2^k \\ T(2^k)&=4^jT(2^{k-j}+3)+4^{j-1}(2^{k-j+1}+3)+ \cdots +4(2^{k-1}+3)+(2^k+3)-7 \end {align} $$ Ahora paramos el cálculo cuando el argumento $2^{k-j}+3=4 \text {, namely when }j=k$ dándonos $$ \begin {align} T(2^k)&=4^kT(4)-7+ \sum_ {i=0}^{k-1}4^i(2^{k-i}+3) \\ &=4^k(- \frac {4}{3})-7+2^k \sum_ {i=0}^{k-1}2^i+3 \sum_ {i=0}^{k-1}4^i \\ &=4^k(- \frac {4}{3})-7+2^k(2^k-1)+3 \frac {4^k-1}{3} \\ &= \frac {2}{3}(2^k)^2-2^k-8 \end {align} $$ así que concluimos que cuando $n$ es un poder de 2 que tenemos $$ T(n)= \frac {2}{3}n^2-n-8 $$ Ya casi hemos terminado. Una vez que establezcamos que $T(4),T(5), T(6), \dots $ es una secuencia estrictamente creciente (lo cual no es tan difícil de hacer) podemos concluir que para $2^{k-1}<n \le2 ^k$ , $$ \frac {2}{3}2^{2(k-1)}-2^{k-1}-8 < T(n) \le \frac {2}{3}2^{2k}-2^k-8 $$ y así llegamos finalmente a la theta que querías, es decir $T(n)= \Theta (n^2)$ .

Un problema divertido, gracias por posarlo.