Come risolvere la recidiva.T (n).= T (n-1) + t (n / 2) + n?

Question

Sono consapevole del fatto che ottenere un tempo di esecuzione con il metodo dell'albero di ricorsione, dobbiamo disegnare un albero e trovare:

a) Numero di livelli in albero .

Dal lato sinistro dell'albero diminuisce di 1 formato, quindi è il percorso più lungo dalla radice. Dimensione subproblem al livello I è n-i. Impostazione N - I= 1 Quando colpisce una dimensione di 1, otteniamo il numero di livelli, i= n - 1.

B) Costo per nodo nell'albero : cn

c) Numero di nodi al livello I : Questo è dove sono bloccato. Non è in grado di trovare i nodi al livello che sin dal lato sinistro diminuisce di 1, lato destro della metà. Naturalmente, l'albero è più denso verso sinistra. Non ogni nodo avrà due figli.

Se posso ottenere una risposta a c, posso calcolare T (n)= costo del livello 0 + costo del livello 1 + costo del livello 2 + ... Costo del livello N-1. Se Y1 è il numero di nodi al livello 1, Y2 al livello 2, ecc ... Quindi
=> T (n)= cn + y1 * cn + y2 * cn + y3 * cn + .... yn-1 * cn per ottenere il costo totale.

Qualcuno può guidarmi all'approccio che sto prendendo? è corretto ? Posso prendere un'ipotesi che per sufficientemente grandi n, possiamo ignorare t (n / 2) e quindi procedere? .

La ricerca online mi ha confuso. Il problema è 4,4-5 da CLRS.

Si prega di vedere qui

Questa soluzione dice t (n)= o (2 ^ n) e t (n)= omega (n ^ 2) e non spiega come.

Vedi anche qui

Questa soluzione dice T (n)= o (n ^ 2). Ma contraddice con sopra la soluzione

Answer 1

Let $ s (n)= t (n) - 2n - 2 $ . Puoi verificare che $ s (n)= s (n-1) + s (n / 2) $ (ignorando il fatto che $ N / 2 $ Non è necessario essere un intero). Ciò dimostra che l'additivo $ N $ termine non fa una grande differenza.

per grande $ N $ , abbiamo grosso modo $ s (n) - s (n-1) \ circa S '(n) $ , e quindi siamo portati a risolvere l'equazione differenziale $$ S '(n)= s (n / 2). $$ Considerare $ f (n)=exp (\ tfrac {1} {2} \ log_2 ^ 2 n) $ . Poi $$ f '(n)=exp (\ tfrac {1} {2} \ log_2 ^ 2 n) \ clot \ frac {\ ln n} {\ ln n} {(\ ln 4) n}, $$ mentre $$ f (n / 2)=exp (\ tfrac {1} {2} (\ log_2 n - 1) ^ 2) \ circa \ exp (\ tfrac {1} {2} \ log ^ 2 n) \ exp ( - \ log n)=exp (\ tfrac {1} {2} \ log ^ 2 n) \ cdot \ frac {1} {n}. $$ Questo suggerisce che, per lo meno, $ \ ln s (n)=theta (\ log ^ 2 n) $ .

Da dove viene? Puoi pensare a $ s (n) $ (con un caso di base appropriato!) Come il numero di modi per passare da $ N $ a zero applicando due operazioni: sottrarre 1 e dividere per 2. Una sequenza "tipica" di tale sequenza conterrà approssimativamente $ \ log_2n $ Molte operazioni del secondo tipo, fuori da $ \ theta (n) $ operazioni in totale, portando alla stima molto approssimativa $ \ binom {\ theta (n)} {\ log_2 n} $ , che è anche del modulo $ \ exp \ theta (\ log ^ 2 n) $ .

---

.

Considerare la concretezza La seguente definizione precisa di $ s (n) $ : il caso base è $ s (0 )= 1 $ e per $ n> 0 $ , $$ S (n)= s (n-1) + s (\ lfloor n / 2 \ rfloor). $$ Questa è sequenza A000123 . Knuth, Una recidiva quasi lineare , ha dimostrato che $$ \ log_4 s (n) \ sim \ log_4 ^ 2 n, $$ Cioè, il rapporto tra i due termini tende a 1 come $ n \ to \ fity $ . La voce OEIS contiene ancora più precisa asintotica.

Answer 2

Non sono d'accordo con l'ipnosi del fibonacci, ma non sono sicuro al cento per cento della mia risposta

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

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

Tuttavia, non ottieni t (n) con aggiunta semplice.

Se vai un livello nella ricorsione (puoi disegnare un albero)

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]

questo per mostrarti che non è solo solo $ o (n ^ 2) $

Devo completarlo, ma sospetto che sia $ o ((n ^ 2) * log n) $ o $ o ((n ^ 2) * n ^ {log n})= o (n ^ 3) $

{C'è un termine n (1 + 1/2 + 1/4 + .. 1 / N) che decade nel registro N passi, devo verificare di nuovo}