Pages: 1 [2]   Go Down
Print
Author Topic: Come risolvere questa ricorrenza? (compito di oggi 08/03)  (Read 2107 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
ExEcUtIvE
Apprendista Forumista
**
Offline Offline

Posts: 114


Compila o non compila, questo è il problema!


« Reply #15 on: 09-03-2012, 18:09:11 »

Grazie ragazzi, ho capito dove sbagliavo... Approssimavo un po troppo  I !!
P.S.: non ho detto che quella era la soluzione, ma che quella era la soluzione che ho messo io spiegando quali passaggi mi ci hanno portato.


Quindi da questo ragionamento deduci che è O(n)...Se ho fatto correttamente..

Logged
corel_86
Forumista
***
Offline Offline

Gender: Male
Posts: 570



« Reply #16 on: 20-07-2012, 06:18:01 »

Un mio collega mi aveva chiesto aiuto su questo esercizio dicendomi che non aveva capito bene i passaggi, spero che in modo o nell'altro riceva questo messaggio con la speranza che gli sia di aiuto.

Allora premetto che algoritmi l'ho data 2 anni quindi possono esserci degli errori. In caso correggetemi:

                                                                                           n

                     
                  (n/5)                                    (n/5)                                       (n/5)                                     (n/2)                        ->11/10n



                                       
(n/25) (n/25) (n/25) (n/10)    (n/25) (n/25) (n/25) (n/10)    (n/25) (n/25) (n/25) (n/10)   (n10) (n/10) (n/10) (n/4)         ->121/100n

il cammino più lungo è dato dal percorso n -> n/2 -> n/4 ->.......-> 1

poichè (\frac{1}{2})^in=1

allora

i=log_2n

una volta effettuato questo calcolo si fa la sommatoria

\sum_{i=0}^{log_2n } (\frac{11}{10})^i n

n \sum_{i=0}^{log_2n } (\frac{11}{10})^i

ricordando che

\sum_{i=0}^{n} x^i\begin{Bmatrix} n &&& se &&& x=1 \\ \frac{1-x^{n+1}}{1-x} &&& &&& altrimenti\end{Bmatrix}

il risultato di tutto è

n \sum_{i=0}^{log_2n } (\frac{11}{10})^i=n\frac{1-(11/10)^{log_2n +1 }}{1-(11/10)}

applicando poi le regole degli logaritmi e facendo alcuni passaggi semplici il risultato sarà

\Theta(n^2)

E' questo è tutto gente Link Immagine
Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
Pages: 1 [2]   Go Up
Print
Jump to: