Qualcuno può aiutare a risolvere questo relazione di ricorrenza? [chiuso]

Question

T(n) = 2T(n/2) + 0(1)

T(n) = T(sqrt(n)) + 0(1)

In primo utilizzo metodo di sostituzione per n, logn, ecc; tutto mi ha dato risposte sbagliate.
alberi di ricorrenza:. Non so se posso applicare come la radice sarà una costante

Può qualcuno aiuto?

Answer 1

Diamo un'occhiata al primo. Prima di tutto, è necessario sapere T (caso base). Lei ha detto che si tratta di una costante, ma quando si fa il problema è importante che si scrive in giù. Di solito è qualcosa di simile a T (1) = 1. userò che, ma si può generalizzare a qualunque cosa sia.

Avanti, scoprire quante volte si ripresentano (che è, l'altezza dell'albero di ricorsione). n è la dimensione del problema, in modo da quante volte possiamo più volte dividere n per 2? Matematicamente parlando, che cosa sono io quando n/(2^i) = 1? Figura fuori, presa su di esso per più tardi.

Avanti, fare un paio di sostituzioni, fino a quando si inizia a notare un modello.

T(n) = 2(2(2T(n/2*2*2) + θ(1)) + θ(1)) + θ(1)

Ok, lo schema è che moltiplicano T () da 2 un mucchio di volte, e dividere n da 2 un mucchio di volte. Quante volte? volte i.

T(n) = (2^i)*T(n/(2^i)) + ...

Per le grandi-? termini, alla fine, si usa un trucco carino. Guardate sopra dove abbiamo un paio di sostituzioni, e ignorare la parte T (). Vogliamo che la somma dei termini ?. Si noti che si sommano a (1 + 2 + 4 + ... + 2^i) * θ(1). Si può trovare una forma chiusa per 1 + 2 + 4 + ... + 2^i? Ti darò che uno; è (2^i - 1). E 'una buona per solo memorizzare, ma ecco come si sarebbe capirlo .

In ogni caso, tutto sommato otteniamo

T(n) = (2^i) * T(n/(2^i)) + (2^i - 1) * θ(1)

Se avete risolto per i prima, poi si sa che i = log_2(n). Plug che, fare un po 'di algebra, e si arriva fino a

T(n) = n*T(1) + (n - 1)*θ(1). T(1) = 1. Così T(n) = n + (n - 1)*θ(1). Che è n volte una costante, più una costante, oltre a n. Lasciamo cadere termini di ordine inferiore e costanti, quindi è ? (n).

Prasoon Saurav è proprio sull'utilizzo del metodo padrone, ma è importante che tu sappia cosa la relazione di ricorrenza sta dicendo. Le cose da porsi sono, quanto lavoro mi faccio ad ogni passo, e qual è il numero di passi per un ingresso di dimensioni n?

Answer 2

Master Theorem per risolvere tali relazioni di ricorrenza.

  

Sia un essere un numero intero maggiore o uguale a 1 e b essere un numero maggiore reali che   1. Sia c essere un numero reale positivo e    D un numero reale non negativo. Data una ricorrenza della forma

     

  

• T (n) = T (n / b) + n ^c .. se n> 1

  

• T (n) = d .. se n = 1

  

     

poi per una potenza di n b,

     

  
1. se log _b un c ),
  
2. se log _b a = c, T (n) = T (n ^c log n),
  
3. se log _b a> c, T (n) = T (n ^{log _b a} ).
  

1) T(n) = 2T(n/2) + 0(1)

In questo caso

a = b = 2;
   log _b a = 1; c = 0 (dal n ^c = 1 => c = 0)

Case (3) è applicabile. Così T(n) = Θ(n):)

---

2) T(n) = T(sqrt(n)) + 0(1)

Sia m = log ₂ n;

=> T (2 ^m ) = T (2 ^{m / 2} ) + 0(1)

Ora rinominando K (m) = T (2 ^m ) => K (m) = K (m / 2) + 0(1)

Applicare Case (2).

---

Answer 3

Da parte 1, è possibile utilizzare teorema come suggerito @Prasoon Saurav.

Per la parte 2, semplicemente ampliare la ricorrenza:

T(n) = T(n ^ 1/2) + O(1)         // sqrt(n) = n ^ 1/2
     = T(n ^ 1/4) + O(1) + O(1)  // sqrt(sqrt(n)) = n ^ 1/4
     etc.

La serie continuerà a termini k fino n ^ 1/(2^k) <= 1, cioè 2^k = log n o k = log log n. Che dà T(n) = k * O(1) = O(log log n).

Answer 4

Diamo un'occhiata alla prima recidiva, T (n) = 2T (n / 2) + 1. Il n / 2 è il nostro indizio qui: parametro di ogni termine nidificato è la metà di quella del suo genitore. Pertanto, se si parte con n = 2 ^ k allora avremo k termini nella nostra espansione, ciascuna aggiungendo 1 al totale, prima di colpire il nostro caso base, T (0). Quindi, assumendo T (0) = 1, possiamo dire T (2 ^ k) = k + 1. Ora, poiché n = 2 ^ k dobbiamo avere k = log_2 (n). Pertanto T (n) = log_2 (n) + 1.

Si può applicare lo stesso trucco per la tua seconda recidiva, T (n) = T (n ^ 0.5) + 1. Se cominciamo con n = 2 ^ 2 ^ k avremo k termini nella nostra espansione, ognuno dei quali aggiunge 1 al totale. Supponendo T (0) = 1, si deve avere T (2 ^ 2 ^ k) = k + 1. Poiché n = 2 ^ 2 ^ k dobbiamo avere k = log_2 (log_2 (n)), quindi T (n) = log_2 (log_2 (n)) + 1.

Answer 5

relazioni di ricorrenza e funzioni ricorsive come bene dovrebbe essere risolto partendo f (1). Nel caso 1, T (1) = 1; T (2) = 3; T (4) = 7; T (8) = 15; È chiaro che T (n) = 2 * n -1, che in notazione O è O (n).
Nel secondo caso T (1) = 1; T (2) = 2; T (4) = 3; T (16) = 4; T (256) = 5; T (256 * 256) = 6; Ci vorrà poco tempo per scoprire che T (n) = log (log (n)) + 1 in cui registro è in base 2. Chiaramente questo è O (log (log (n)) relazione.

Answer 6

La maggior parte delle volte il modo migliore per trattare con recidiva è quello di disegnare l'albero recidiva e con attenzione gestire il caso base.

Comunque qui vi darà leggero sentore di risolvere utilizzando il metodo di sostituzione.

In reiterazione primo tentativo di sostituzione n = 2^k Nella ricorrenza secondo tentativo cambio n = 2^2^k