[Algoritmi] Scrivere equazione di ricorrenza da un'algoritmo

mathix1
Qualcuno può aiutarmi a scrivere l'equazione di ricorrenza di questo algoritmo???

Sia considerato il seguente algoritmo ricorsivo per il calcolo della sommatoria di una sequenza di S numeri:
int sommatoria(Sequenza S)
{  
     se |S| = 1 allora
               ritorna S0 ossia l'unico elemento della sequenza
     se |S| = 2 allora 
               ritorna S0+S1, ossia la somma degli elementi della sequenza

     suddividi S in tre sottosequenze S1,S2,S3 di ampiezza uguale
     t1 = sommatoria(S1)
     t2 = sommatoria(S2)
     t3 = sommatoria(S3)
     ritorna t1+t2+t3
}


io ho scritto: T(n) = 3(T/2) ma non ho idea se sia giusta e se vada risolta nella forma ax+b
grazie in anticipo per l'aiuto.

Risposte
apatriarca
Come saresti arrivato a quella forma? Come ti hanno insegnato a procedere per scrivere l'equazione di ricorrenza per un qualche algoritmo?

mathix1
"apatriarca":
Come saresti arrivato a quella forma? Come ti hanno insegnato a procedere per scrivere l'equazione di ricorrenza per un qualche algoritmo?

mmm ho scritto male: intendevo T(n) = 3(T/3)
cioè O(1) per le prime due operazioni che sono costanti, giusto? e 3 volte T diviso il numero il numero di sottosequenze di S.

ad ogni modo, nessuno mi ha insegnato a farle, nel senso che non ho potuto seguire quest'argomento a lezione e sul testo le equazioni di ricorrenza sono trattate malissimo.

sono capace solo di risolverle con il teorema principale e la forma ax+b, ma non di scrivere un'equazione di ricorrenza partendo da un'algoritmo.

qualsiasi tipo di aiuto è gradito

hamming_burst
"mathix":

sono capace solo di risolverle con il teorema principale e la forma ax+b, ma non di scrivere un'equazione di ricorrenza partendo da un'algoritmo.


Se non hai mai visto nulla del genere, dubito che darti il risultato serva a qualcosa, prima di tutto consiglio di guardare qualche esempio pratico:
- post490341.html#p490341
- post474675.html#p474675
- post479901.html#p479901 (Dispense varie, guarda sezione Analisi Algoritmi)

con ciò poi prova ad applicare lo stesso metodo, il ragionamento che hai fatto è corretto, ti manca solo una parte per finire l'equazione... :-)

mathix1
"ham_burst":
con ciò poi prova ad applicare lo stesso metodo, il ragionamento che hai fatto è corretto, ti manca solo una parte per finire l'equazione... :-)


studiando meglio sono arrivato a capire che quello è un caso divide et impera per cui

ho scritto T(n) = 3T(n/3) + c

T(1) = a+b
T(n) = an+b = 3T(n/3) + c
an+b = 3( an/3 + b) + c
an+b = an + 3b + c
-2b = c
b= -(c/2)

T(1)= a - (c/2)
2a - c

ho sbagliato qualcosa?

hamming_burst
"mathix":

studiando meglio sono arrivato a capire che quello è un caso divide et impera per cui

esatto.

Lo schema divide-et-impera, riporta due "funzioni" principali che cercano di raggruppare i costi dell'algoritmo:
- D() - divide: costo di suddivisione dell'input
- C() - conquer: costo riunire i sotto-problemi

visto che nell'algoritmo non si dice nulla su "come" si suddivide l'input, ipotizziamo sia solo un'operazione aritmetica, perciò di costo costante (sorry per il gioco di parole :-)) e riunire i problemi è una semplice somma, sempre costante. Perciò:

- D() in $\Theta(1)$
- C() in $\Theta(1)$

unendo la ricorsione con il costo immediato dell'algoritmo ed ipotizzando che la dimensione dell'input $n$ sia una potenza esatta di $3$:

$3T(n/3) + \Theta(1) + Theta(1) = 3T(3) + \Theta(1)$

che alla fine è ciò che hai scritto, ma non formalmente scritto bene :-)



ho scritto T(n) = 3T(n/3) + c

T(1) = a+b
T(n) = an+b = 3T(n/3) + c
an+b = 3( an/3 + b) + c
an+b = an + 3b + c
-2b = c
b= -(c/2)

T(1)= a - (c/2)
2a - c

ho sbagliato qualcosa?

Non conoscendo il metodo con cui risolvi le ricorrenze non posso darti smentita Mi pare di capire che cerchi di eguagliare un'equazione lineare (che penso equivalga ad ipotizzare una classe di complessità) con la tua ricorrenza. interessante :-)

Comunque sì è un algoritmo lineare di complessità $O(n)$ perciò la tua ipotesi è corretta.

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.