Resolución de repetición $T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n)$

Question

Estoy algoritmos de aprendizaje por mí mismo y estoy usando la excelente Introducción a los algoritmos para hacer eso. Ha sido un largo tiempo desde la última vez que estudió matemáticas, así que tal vez la solución a mi problema es trivial.

Ejercicio 4.3-5 pide a demostrar que $\Theta(n \lg n)$ es la solución a la "exacta" de recurrencia para combinar ordenar usando el método de sustitución.

La recurrencia es: $T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n)$

Aquí es cómo he comenzado a abordar el problema:

Necesito demostrar que la recurrencia es $O(n \lg n)$ $\Omega(n \lg n)$ a demostrar que es $\Theta(n \lg n)$. Vamos a empezar con $O(n \lg n)$.

Vamos a suponer que el obligado a $T(m) \leq cn \lg n$ mantiene para todos $c > 0$, $m > 0$, $m > n$; en particular, para $m = n/2$, lo que da:

$$ T(n/2) \leq cn/2 \lg(n/2) $$

Sustituyendo en la recurrencia de los rendimientos:

$$\begin{aligned} T(n) &\leq c n/2 \lg(n/2) + c n/2 \lg(n/2) + \Theta(n) \\\\ &= cn \lg(n) - (cn - \Theta(n)) \end{aligned}$$

Y luego estoy bloqueado, supongo que tengo que quitar $\Theta(n)$ con algo como $kn$ pero no parece muy riguroso.

Answer 1

Usted puede encontrar un resumen del método de sustitución en esta declaración de la pregunta y una discusión sobre las condiciones de contorno en una respuesta a la misma pregunta. El mismo material está disponible en la sección 4.3 en las páginas 83 y 84 de la tercera edición del libro. Especialmente interesante en esta referencia es el tratamiento de condiciones de límite.

Answer 2

Su trabajo no es exactamente correcto, incluso antes de que el punto que se quedó atascado.

Se han sustituido $\lceil n/2 \rceil$$\lfloor n/2 \rfloor$$n/2$, que es lo que quería evitar, ¿no? (De lo contrario, sólo tiene que utilizar la recurrencia $T(n) = 2T(n/2) + f(n)$).

Tenemos la recurrencia:

$T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + f(n)$

donde $f(n) = \theta(n)$, es decir, hay algunos $C \gt 0$ tal que $f(n) \le Cn$ todos los $n$.

Supongamos que queremos mostrar a $T(n) = \mathcal{O}(n \log n)$.

(Nota: el logaritmo es a base de $2$).

Tratamos de usar la inducción.

Suponga que $T(1) = 0$.

Supongamos que para todos los $k \lt n$,$T(k) \le D k\log k$, lo $D$ es, se determina más adelante.

Observe que $\lceil n/2 \rceil + \lfloor n/2 \rfloor = n$

No tenemos que

$T(n) \le Dn \log \lceil n/2 \rceil + f(n) \le Dn\log (\frac{n+1}{2}) + Cn$

Ahora$\log(n+1) \le \log n + \frac{1}{n}$, por lo que tenemos

$T(n) \le Dn\log n + D + Cn - Dn$

Ahora bien, si tomamos $D$, de modo que $Dn \gt Cn + D$ todos los $n \gt 2$, hemos terminado.

Recogiendo $D \gt 2C$ va a funcionar y para esto $D$, se puede comprobar la base de los casos de $n=1,2$ fácilmente.

Por lo tanto $T(n) = \mathcal{O}(n \log n)$.

Mostrando que $T(n) = \Omega(n\log n)$ podría tener más trabajo.