Cómo resolver la recurrencia.Tennesse).= T (N-1) + T (N / 2) + N?

Question

Soy consciente de que para obtener un tiempo de ejecución por el método de árbol de recursiones, necesitamos dibujar un árbol y encontrar:

a) Número de niveles en árbol .

Dado que el lado izquierdo del árbol disminuye en 1 de tamaño, por lo que es un camino más largo de la raíz. El tamaño del subproblema a nivel I es n-i. Configuración N - i= 1 Cuando llega a un tamaño de 1, obtenemos el número de niveles, I= N - 1.

b) Costo por nodo en árbol : cn

c) Número de nodos en el nivel I : Aquí es donde estoy atascado. No puede encontrar nodos a nivel I desde el lado izquierdo disminuye en 1, lado derecho a la mitad. Naturalmente, el árbol es más denso hacia el lado izquierdo. No todos los nodos tendrán dos hijos.

Si puedo obtener respuesta a C, puedo calcular T (n)= Costo de Nivel 0 + Costo del Nivel 1 + Costo del Nivel 2 + ... Costo del nivel N-1. Si Y1 es el número de nodos en el nivel 1, Y2 en el nivel 2, etc. entonces
=> T (n)= CN + Y1 * CN + Y2 * CN + Y3 * CN + .... YN-1 * CN Para obtener un costo total.

¿Puede alguien guiarme al enfoque que estoy tomando? es correcto ? ¿Puedo suponer que para NURSUMENTO N, podemos ignorar T (N / 2) y luego proceder? .

búsqueda en línea confundida conmigo. El problema es 4.4-5 de CLRS.

Por favor, consulte aquí

Esta solución dice T (N)= O (2 ^ N) y t (n)= omega (n ^ 2) y no explica cómo.

También vea aquí

Esta solución dice T (N)= O (n ^ 2). pero contradice con la solución anterior

Answer 1

Let $ s (n)= t (n) - 2n - 2 $ . Puede verificar que $ s (n)= s (n-1) + s (n / 2) $ (ignorando el hecho de que $ n / 2 $ No necesita ser un número entero). Esto muestra que el aditivo $ n $ término no hace una gran diferencia.

para un gran $ n $ , tenemos aproximadamente $ s (n) - s (n-1) \ aprox S '(n) $ , por lo que nos llevan a resolver la ecuación diferencial $$ S '(n)= s (n / 2). $$ Considere $ f (n)=exp (\ tfrac {1} {2} \ log_2 ^ 2 n) $ . Luego $$ f '(n)=exp (\ tfrac {1} {2} \ log_2 ^ 2 n) \ cdot \ frac {\ ln n} {(\ ln 4) n}, $$ mientras que $$ f (n / 2)=exp (\ tfrac {1} {2} (\ log_2 n - 1) ^ 2) \ aprox \ exp (\ tfrac {1} {2} \ log ^ 2 n) \ exp ( - \ log n)=exp (\ tfrac {1} {2} \ log ^ 2 n) \ CDOT \ frac {1} {n}. $$ Esto sugiere que, al menos, $ \ ln s (n)=theTa (\ log ^ 2 n) $ .

¿De dónde viene esto? Puede pensar en $ s (n) $ (¡con un caso base apropiado!) Como la cantidad de formas de ir de $ n $ a cero al aplicar dos operaciones: restar 1 y dividir por 2. Una secuencia "típica" contendrá aproximadamente $ \ log_2n $ muchas operaciones del segundo tipo, fuera de $ \ theta (n) $ Operaciones en total, lo que lleva a la estimación aproximada $ \ binom {\ theta (n)} {\ log_2 n} $ , que también es del formulario $ \ exp \ theta (\ log ^ 2 n) $ .

---

Considere para la concreencia la siguiente definición precisa de $ s (n) $ : el caso base es $ s (0 )= 1 $ , y para $ n> 0 $ , $$ S (n)= S (N-1) + S (\ lfloor n / 2 \ rfloor). $$ Esto es secuencia a000123 . Knuth, una recurrencia casi lineal , mostró que $$ \ log_4 s (n) \ sim \ log_4 ^ 2 n, $$ es decir, la proporción de los dos términos tiende a 1 como $ n \ to \ infty $ . La entrada OEIS contiene asintóticos aún más precisos.

Answer 2

No estoy de acuerdo con la hipnosis del fibonacci, pero no estoy cenando por ciento de mi respuesta

ves $ t (n)= t (n-1) + c * n= o (n ^ 2) $

$ t (n)= t (n / 2) + c * n= o (n log n) $

Sin embargo, no obtienes UR T (N) por agregado directo.

Si va un nivel en la recursión (u puede dibujar un árbol)

t (n)= T (N-2) + T ((N-1) / 2) + T (N / 2-1) + T (N / 4) + [N + (N-1) + (N-1) / 2 + (N / 2-1) + N / 4]

Esto para mostrarte que tampoco es solo $ o (n ^ 2) $

Tengo que completarlo, pero sospecho que $ O ((n ^ 2) * log n) $ o $ O ((n ^ 2) * n ^ {log n})= O (n ^ 3) $

{Hay un término N (1 + 1/2 + 1/4 + .. 1 / N) que se descompone en los pasos de registro n, tengo que volver a comprobar}