Dom 18 Agosto, 07:04:32 - 2019

Autore Topic: Costi computazionali ed equazioni di ricorrenza  (Letto 8103 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline heavenriver

  • Global Moderator
  • Direttore di Dipartimento
  • *****
  • Post: 1060
  • FeedBack: +103/-67
  • z = z² + c
    • Mostra profilo
    • Sito web (Curriculum Vitae)
Costi computazionali ed equazioni di ricorrenza
« il: Lun 31 Dicembre, 14:06:53 - 2012 »
Apro questo topic per confrontare i nostri risultati negli esercizi numero 1 della parte di Algoritmi, quelli sui costi computazionali. Ho diversi dubbi:

19 gennaio 2012: i metodi ciop e cucu mi vengono di costo lineare alla dimensione dell'array. Il metodo cip, per quel che ho capito, quadruplica la dimensione dell'array a ogni chiamata (perché chiama due volte ciop, e ciop raddoppia la dimensione dell'array). Quindi anche cip è lineare alla dimensione dell'array (asintoticamente)? Perciò il costo è O(n)? Come lo metto in equazione di ricorrenza?

22 febbraio 2012: mistero2 è lineare alla dimensione dell'array, ma mistero1? L'equazione di ricorrenza mi viene:
f(n) = c se n = 0; f(n-1)*g(n-1) + c altrimenti.
g(n) è mistero2, quindi è lineare. Ho sbagliato a scrivere l'equazione? Se la svolgo così, mi termina a f(0)gn(0) + nc, che è lineare (visto che g(0) è una costante). Qualcosa non mi torna!

27 aprile 2012: nel metodo swap, devo assumere che setCharAt sia costante o lineare? Io ho assunto che sia costante, quindi swap costa O(1). Il metodo m2 è chiaramente O(n). Invece m1 ha costo pari a m2 + m3. Ora, i costi di m3? Chiama se stesso s.length() volte (se si parte da k = 0), e il doppio di quelle volte chiama swap. Allora devo fare il prodotto tra i costi dei due metodi, o la somma? A me verrebbe da dire la somma, e quindi da considerare anche m3 lineare alla dimensione della stringa. Sto sbagliando?

18 giugno 2012: ho sempre lo stesso dubbio, m1(int[], int) che chiama sé stesso e m2 va considerato, in termini di costi, come somma dei costi dei metodi oppure come prodotto dei costi? (Anche qui mi viene da pensare alla somma, perché alla fine vengono chiamati lo stesso numero di volte...) Supponiamo che m2 venga chiamato k volte, e così pure m1: il costo totale è quindi k*m1 + k*m2?

12 settembre 2012: metodo pow... che diamine è b >> 1?!?

4 marzo 2011: mi viene che il costo richiesto è O(m2n), m numero di righe e n numero di colonne della matrice, ma non so come metterlo in funzione del costo della matrice (oppure scrivo semplicemente che rispetto alla dimensione della matrice ha costo lineare?) e non so come scrivere l'equazione di ricorrenza. (Che poi... è SEMPRE richiesta l'equazione di ricorrenza?)

6 maggio 2011: per favore, illuminatemi su cos'è n >>= 1 e int lsb = 0x1 & n O_O e poi l'equazione di ricorrenza mi viene una cosa bruttissima per il metodo smartExp: f(n) = c se n = 0, f2(n/2) + c altrimenti. Sarebbe alla fin fine fn(n/2n). Mi ricordo che si può tradurre in costo logaritmico, anche se non ricordo come si faccia... e poi chiede anche il costo in funzione della dimensione dell'input che non so proprio come possa calcolarlo. Devo considerare il numero di bit necessari a rappresentare il numero, e calcolarmi quanti bit è lunga la rappresentazione del numero elevato a potenza, o cosa?

21 giugno 2011: qui mi è chiaro solo il fatto che append espande l'array aggiungendoci il boolean passato come parametro, quindi ha costo lineare. Sul resto, illuminatemi - non ho idea di dove mettere le mani.

14 settembre 2011: come sopra per il secondo metodo, mistero. Ho capito che divide l'array in 3 parti e ricorre sulla prima nel primo parametro, e sulla seconda e la terza nel secondo parametro di Math.max. Come calcolo i costi computazionali?

11 novembre 2011: vi risulta che il costo dell'algoritmo richiesto sia O(xaa), dove x è il double e a è la dimensione dell'array?

Offline Agilulfo

  • Neo-Laureato
  • **
  • Post: 79
  • FeedBack: +25/-0
    • Mostra profilo
Re:Costi computazionali ed equazioni di ricorrenza
« Risposta #1 il: Mar 01 Gennaio, 15:56:54 - 2013 »
19 gennaio 2012
http://solo.dis.uniroma1.it/index.php?topic=14628.msg117645#msg117645

per le equazioni di ricorrenza:
T(|v|) = O(|v|), quando |v| >= n (passo base)
T(|v|) = T(4*|v|) + O(|v|), quando |v| < n

con considerazioni simili fatte nel post linkato, risolvendo le equazioni il costo viene lo stesso


22 febbraio 2012
http://solo.dis.uniroma1.it/index.php?topic=14740.msg117973#msg117973

mistero1:
T(n) = O(1), se n = 0
T(n) = T(n-1) + costo_mistero2

e vabe, mistero2 costa nel caso peggiore O(n), in pratica è una ricorsione di coda con una singola chiamata ricorsiva
(le equazioni di ricorrenza sarebbero banali)

quindi la seconda di mistero1 diventa T(n) = T(n-1) + O(n) --> O(n^2)


27 aprile 2012
si, StringBuffer è implementato con un array (dinamico) sottostante, quindi l'accesso posizionale è costante (setCharAt() e charAt())

per il punto a, theta(n) e in funzione della dimensione dell'input: theta(2^x)

per il punto b, m3 ha costo theta((|s|-k)!); m1 chiama m3 con k=0 e quindi il costo totale di m1 (m2+m3) viene theta(|s| + |s|!) = theta(|s|!)
per capire il costo di m3 definiamo z = |s|-k, ad ogni passo m3 si chiama ricorsivamente z volte con un input decrementato di 1 ogni volta (z-1)
e quindi viene z*(z-1)*(z-2)*...*2*1 = z!

se non è chiaro, pensa al caso di un algoritmo che si chiama ricorsivamente un numero costante di volte (ad es. 2 volte) con l'input n che viene decrementato di 1,
allora il costo di tale algoritmo è 2*2*2*...*2*2 (n volte) = 2^n

oppure si può ragionare con le equazioni di ricorrenza: T(z) = z*T(z-1) + c (ometto di scrivere il caso T(z=0) che è costante)

per il punto c, dato in input "abc", l'algoritmo restituisce un array di stringhe contenente tutte le n! (6 in questo caso) permutazioni dell'input
[abc, acb, bac, bca, cba, cab]


18 giugno 2012
devi calcolarne il prodotto, visto che m1 chiama m2 ad ogni suo passo ricorsivo
(ci sarebbe la somma se ci fosse un ipotetico metodo m0 che chiama m1 e m2 separatamente, con m1 che non chiama m2 al suo interno)

punto a, costo di m2: O(|a|-i)
punto b, costo di m1: O(|a|^2)
in pratica m1 viene chiamato |a| volte, ed ogni volta m2 viene chiamato con un input sempre più piccolo |a|, |a|-1, |a|-2, |a|-3, ..., 2, 1
se facciamo la somma dei costi viene la somma dei primi |a| numeri naturali che è |a|*(|a|+1)/2 = O(|a|^2)

oppure con le equazioni di ricorrenza: T(|a|) = T(|a|-1) + O(|a|)

punto c, questa è a trabocchetto :P
è vero che non usa esplicitamente memoria aggiuntiva (ad es. array di appoggio)
ma bisogna considerare il fatto che è un algoritmo ricorsivo e quindi usa lo stack per i record di attivazione per chiamare le vare istanze dei metodi chiamati ricorsivamente
e chiaramente questo spazio extra non è costante visto che dipende dall'input


12 settembre 2012
b>>1 è lo shift logico di b a destra di 1 posizione, in pratica divide b per 2^1 (lo dimezza)

a) theta(k^n + logn) = theta(k^n), se k > 1
k^n perché kDadoConta si chiama ricorsivamente k volte con n che decrementa di 1
logn perché pow dimezza il valore di n ad ogni passo

theta(n + logn) = theta(n), se k = 1
con le equazioni di ricorrenza, T(n) = k*T(n-1) + c, diventa k^n oppure n a seconda del valore di k (in pratica quando k=1, la "parte" con il c prevale su 1^k)

b) immagino sia theta((2^x)^(2^y)) e theta(2^y), in termini di bit


4 marzo 2011
mmm interessante
io avrei distinto i diversi casi possibili (d è la dimensione dell'input):
- m >> n (m molto più grande di n): m*n = m = d, O(d*m) = O(d*d) = O(d^2)
- n >> m: m*n = n = d, O(d*m) = O(d*1) = O(d)
- m ~= n (m quasi uguale a n): m*n = m*m = d, O(d*m) = O(d*d^(1/2)) = O(d^(3/2))
quindi nel caso peggiore diventa quadratico

non so risponderti se serve sempre scrivere le equazioni di ricorrenza visto che non so come siano le modalità d'esame ora :P
tipo verrebbe una roba così? T(m*n) = T(m*n-1) + O(m), boh :P


6 maggio 2011
n>>=1, vuol dire fai lo shift logico di n a destra di 1 posizione e poi assegnalo a n (n = n>>1)
int lsb = 0x1 & n, vuol dire assegna a lsb il risultato dell'AND logico tra 1 (solo il primo bit da destra è 1, gli altri bit sono 0) e n
in pratica si salva in lsb il least significant bit di n prima di shiftare (se shifti ti perdi chiaramente l'ultimo bit a destra :P)
(è un metodo veloce per calcolare la potenza di un numero http://en.wikipedia.org/wiki/Exponentiation_by_squaring#Basic_method)

fastPower ha costo theta(log2(n)), visto che n viene dimezzato ad ogni iterazione
smartPower ha costo theta(n), con le equazioni di ricorrenza: T(n) = 2*T(n/2) + c, T(0) = O(1)

in funzione della dimensione dell'input diventano rispettivamente theta(x) e theta(2^x)
"Devo considerare il numero di bit necessari a rappresentare il numero" <-- questo, visto che il numero è l'input, mentre la potenza del numero è l'output


21 giugno 2011
si, il punto a è lineare: theta(|vet|)

per il metodo bit scriviamo le equazioni di ricorrenza: T(n) = T(n/2) + theta(logn) e dovrebbe venire theta((logn)^2)
in funzione della dimensione dell'input: theta(x^2)

in pratica bit viene eseguito logn volte (con n che viene dimezzato ogni volta) e ogni volta che viene chiamato bit, viene chiamato anche append che lavora sul vettore output di bit
questo vettore ha lunghezza logn (perché a questo vettore viene aggiunto un elemento ogni volta che n viene dimezzato)
e quindi moltiplicando viene logn al quadrato

la versione iterativa verrebbe più o meno così, in pseudocodice:
boolean[] ris = new boolean[0]
while (n>0)
   boolean b = n%2!=0
   ris = append(ris, b)
   n = n/2;

che costa 1+2+3+...+(logn-1)+logn = theta((logn)^2) (somma dei primi logn numeri naturali)


14 settembre 2011
boh costa theta(|a|), lineare
poniamo n = j-i, le equazioni di ricorrenza: T(n) = 3*T(n/3) + c, T(n<=3) = costo_boh = theta(3) = theta(1), risolvendo viene theta(n)
visto che mistero viene chiamato con i=0, j=a.length-1: theta(|a|) anche qui


11 novembre 2011
il costo è semplicemente theta(|a|), il numero di passi non dipende da x (sottolineo il numero di passi, perché il valore dell'output dipenderà da x)


se ci stan dubbi o qualcosa è poco chiaro, chiedi pure :P (ti ricordo cmq che queste sono le mie soluzioni, quindi non sono giuste al 100% ;D)

Offline heavenriver

  • Global Moderator
  • Direttore di Dipartimento
  • *****
  • Post: 1060
  • FeedBack: +103/-67
  • z = z² + c
    • Mostra profilo
    • Sito web (Curriculum Vitae)
Re:Costi computazionali ed equazioni di ricorrenza
« Risposta #2 il: Mer 02 Gennaio, 14:44:37 - 2013 »
Agilulfo sei una mano santa :asd:
Ti ringrazio tantissimo per tutto quello che hai scritto! Ci sono alcune piccole cose che non mi sono chiare:

(19 gennaio 2012)

edit2: allora, ragionando con la somma della serie geometrica, posso dire che ciop() viene fatta 1-2^(2k) / 1-2 sulla dimensione originale |v|, e, semplificando con le varie formule dei logaritmi e ignorando le costanti nell'analisi asintotica, viene n*|v|
quindi O(n*|v|*log4(n/|v|))

Questo passaggio mi risulta poco chiaro. Il costo |v| è dato da ciop, log4(n/|v|) è dato da cip... la n da cosa è data?
Inoltre, il pattern dell'equazione di ricorrenza dà come risultato finale T(|v|) = T(4n|v|) + n*O(|v|)... da qui come faccio a trasformarlo in un O-di-qualcosa?

(27 aprile 2012)

Ok, vediamo se ho capito: in m3 il ciclo for fa z = |s| - k iterazioni, e ogni iterazione chiama una volta m3, ed è per questo che l'equazione di ricorrenza viene come da te scritta... di conseguenza anche m1 ha lo stesso costo asintotico, perché ha un O(n) (oppure O(2x)) quando chiama m2 (che è lineare) e poi ci aggiunge il costo di m3, che è chiaramente superiore al costo lineare del metodo precedente. Ho capito bene?

(18 giugno 2012)

Riguardo al punto c): allora tecnicamente nessun algoritmo ricorsivo lavora in-place?

(12 settembre 2012)

Quindi dall'equazione di ricorrenza otteniamo kn + n*c... ma da lì come sei passato al costo in funzione della dimensione dell'input? Hai posto k = 2x e n = 2y?

(6 maggio 2011)

fastPower l'ho capito, ma da cosa hai dedotto che smartExp ha costo lineare?

(21 giugno 2011)

Qui non capisco bene il costo di append... sono d'accordo sul bit logaritmico, ma considerato che append è una ricorsione di coda in teoria non dovrebbe essere lineare? O sto dicendo castronerie? :asd:

Tutto il resto è chiaro come il sole e ti ringrazio infinitamente di nuovo per la pazienza xD

Altro test per vedere se ho capito: prendiamo l'esame del 24 luglio 2012, sempre esercizio 1... il metodo m, quindi, ha costo lineare? E' corretto se scrivo l'equazione T(n) = T(n-1) + c? (Preso n = |a| - i)
Invece il costo spaziale come lo calcolo? Posso dire che, se l'algoritmo chiama se stesso k volte, il costo è k*a[i ] (perché crea k volte un intero di appoggio nel metodo ricorsivo, prima di terminare l'esecuzione)?

Offline Agilulfo

  • Neo-Laureato
  • **
  • Post: 79
  • FeedBack: +25/-0
    • Mostra profilo
Re:Costi computazionali ed equazioni di ricorrenza
« Risposta #3 il: Mer 02 Gennaio, 19:03:07 - 2013 »
Agilulfo sei una mano santa :asd:
Ti ringrazio tantissimo per tutto quello che hai scritto! Ci sono alcune piccole cose che non mi sono chiare:

(19 gennaio 2012)

Questo passaggio mi risulta poco chiaro. Il costo |v| è dato da ciop, log4(n/|v|) è dato da cip... la n da cosa è data?
Inoltre, il pattern dell'equazione di ricorrenza dà come risultato finale T(|v|) = T(4n|v|) + n*O(|v|)... da qui come faccio a trasformarlo in un O-di-qualcosa?
ho ricontrollato i calcoli e sembra che alla fine il costo venga fuori lineare (in funzione di n o di |v|) :P

ok, ragionando con le equazioni di ricorrenza viene più veloce (uso v per indicare |v|, per rendere il tutto più leggibile):
T(v) = T(4v) + O(v) =
= T(16v) + O(4v) + O(v) =
= T(64v) + O(16v) + O(4v) + O(v) = ...

(al passo k-esimo tale che 4kv == n)
= T(4kv) + O(4k-1v) + O(4k-2v) + ... (questi ultimi 2 e gli altri termini possiamo sostituirli con un bel O(4kv), ricordando che la somma della serie geometrica fino a k-1 è O(4k))

sostituendo il caso base:
T(v,n) = O(n) + O(4kv)

sostituendo k con log4(n/v):
T(v,n) = O(n) + O(n/v * v) = O(n)
e questo risultato per n > |v|
sembra ragionevole, secondo me :P cip termina abbastanza velocemente, quadruplicando la dimensione dell'input, ma nel mentre deve sostenere il costo di ciop che diventa sempre 4 volte più lungo da fare ;D

se n < |v|, allora c'è solo il costo di cucu (che è il passo base di cip): O(|v|)

quindi scrivendolo insieme O(max{n, |v|}) = O(n + |v|)

Citazione
(27 aprile 2012)

Ok, vediamo se ho capito: in m3 il ciclo for fa z = |s| - k iterazioni, e ogni iterazione chiama una volta m3, ed è per questo che l'equazione di ricorrenza viene come da te scritta... di conseguenza anche m1 ha lo stesso costo asintotico, perché ha un O(n) (oppure O(2x)) quando chiama m2 (che è lineare) e poi ci aggiunge il costo di m3, che è chiaramente superiore al costo lineare del metodo precedente. Ho capito bene?

si, il costo di m3 dipende anche da k (se si considera m3 come metodo a sé stante), ma quando questo viene chiamato da m1, il valore (iniziale) di k è già noto e quindi rimane solo il costo dato da |s|

Citazione
(18 giugno 2012)

Riguardo al punto c): allora tecnicamente nessun algoritmo ricorsivo lavora in-place?
è interessante questa discussione http://cstheory.stackexchange.com/questions/9563/all-recursive-algorithms-are-inherently-not-inplace-isnt-it :P

Citazione
(12 settembre 2012)

Quindi dall'equazione di ricorrenza otteniamo kn + n*c... ma da lì come sei passato al costo in funzione della dimensione dell'input? Hai posto k = 2x e n = 2y?

mmm si, quando ci son valori numerici la dimensione è in bit per rappresentarli
mentre quando ci stanno gli array, array.length è la loro dimensione

http://solo.dis.uniroma1.it/index.php?topic=6949.msg69076#msg69076 e i seguenti 4-5 post

Citazione
(6 maggio 2011)

fastPower l'ho capito, ma da cosa hai dedotto che smartExp ha costo lineare?

di solito con un metodo ricorsivo con k chiamate ricorsive con un input di dimensione n/k, viene lineare

T(n) = 2*T(n/2) + c
applicando il Master Theorem con a=2, b=2, f(n)=c
caso 1:
f(n) = c = O(nlogb(a)-e) = O(n1-1) (con e=1)
allora T(n) = theta(nlogb(a)) = theta(n)

Citazione
(21 giugno 2011)

Qui non capisco bene il costo di append... sono d'accordo sul bit logaritmico, ma considerato che append è una ricorsione di coda in teoria non dovrebbe essere lineare? O sto dicendo castronerie? :asd:

append è lineare in funzione della dimensione dell'input, ma se l'input ha dimensione logn, allora anche append è "lineare" a logn

per farti un esempio, immagina un'implementazione alternativa di append, chiamata append2, e quest'ultima ha costo O(|vet|2) (quadratico)
se passassimo ad append2 un array lungo logn, allora append2 avrebbe costo O((logn)2), quadratico rispetto alla dimensione dell'input (che è logn)

Citazione
Tutto il resto è chiaro come il sole e ti ringrazio infinitamente di nuovo per la pazienza xD

Altro test per vedere se ho capito: prendiamo l'esame del 24 luglio 2012, sempre esercizio 1... il metodo m, quindi, ha costo lineare? E' corretto se scrivo l'equazione T(n) = T(n-1) + c? (Preso n = |a| - i)
Invece il costo spaziale come lo calcolo? Posso dire che, se l'algoritmo chiama se stesso k volte, il costo è k*a[i ] (perché crea k volte un intero di appoggio nel metodo ricorsivo, prima di terminare l'esecuzione)?

quando dici che l'algoritmo chiama se stesso k volte, dici semplicemente che la sua complessità temporale è theta(k), no? (con k = |a|)
cmq non è necessario indicare a[i ], visto che la dimensione di un intero di appoggio è costante rispetto all'input: quindi asintoticamente diventa theta(|a|)
tornando in tema di algoritmi ricorsivi ci sarebbe anche lo spazio occupato dalle chiamate ricorsive che cmq è lineare rispetto ad |a|, quindi va bene theta(|a|)


p.s.: non sono sicurissimo del primo esercizio (cip, ciop e cucu), se noti qualcosa che non va fammi sapere :P

Offline heavenriver

  • Global Moderator
  • Direttore di Dipartimento
  • *****
  • Post: 1060
  • FeedBack: +103/-67
  • z = z² + c
    • Mostra profilo
    • Sito web (Curriculum Vitae)
Re:Costi computazionali ed equazioni di ricorrenza
« Risposta #4 il: Gio 03 Gennaio, 14:31:32 - 2013 »
Allora, provo a risolvere l'esercizio di cip e ciop ragionando in maniera leggermente differente (più simile al tuo ragionamento nel post di prima)... n < v.length esegue n < |v|, n < |4v|, ..., n < |4k|v|). Quindi k = log4(n/|v|). Questo in teoria dovrebbe essere il numero di chiamate di cip. Parimenti ciop costa O(4k|v|). Siccome i costi vanno moltiplicati: O(log4(n/|v|)) * O(4log4(n/|v|)|v|) (che è il costo di ciop) = O(log4(n/|v|)) * O(n/|v| * |v|) = O(log4(n/|v|)) * O(n). Non li ho sommati perché c'è la ricorsione di mezzo, e in base a quanto mi hai scritto nel post prima, suppongo si debbano moltiplicare. Se invece non ci ho capito niente e vanno sommati allora viene un facile facile O(n). Correggimi se sbaglio! :sisi:

Riguardo a "in place o non in place"... ma dobbiamo fargli il pippone filosofico anche all'esame? :asd: Ai fini dell'esame, gli algoritmi ricorsivi possono essere considerati in place?

Riguardo al calcolo in funzione della dimensione: quindi, se io trovo un costo O(|a|) che è lineare alla dimensione dell'array, non devo considerare i bit usati per rappresentarlo, ma solo quante celle ha l'array, ho capito bene?

Append viene chiamato tante volte quante viene chiamato bit, quindi log(n) volte, e bit ha costo log(n) ed è per questo che viene log2(n) (detto in termini molto semplicistici)?

Per il resto come al solito ti ringrazio :) Il confronto fa un bene incredibile anche al liberarsi della paranoia :P

Offline Agilulfo

  • Neo-Laureato
  • **
  • Post: 79
  • FeedBack: +25/-0
    • Mostra profilo
Re:Costi computazionali ed equazioni di ricorrenza
« Risposta #5 il: Gio 03 Gennaio, 15:44:28 - 2013 »
è che ciop costa O(4k|v|) solo all'ultima chiamata (o per essere più precisi O(4k-1|v|))
nelle chiamate precedenti costa O(4k-2|v|), O(4k-3|v|), O(4k-4|v|) e così via
se fai la somma di tutti questi costi viene O(4k|v|) (sarebbe \frac{1-4^k}{1-4}|v|)
e facendo la somma di questi costi è come se tenessi già conto del costo di cip
(invece di fare O(4k|v|)*O(k), fai \sum_{i=0}^{k-1} 4^i|v|)
il problema sta nel fatto che ciop non ha un costo "costante", ma varia durante l'esecuzione dell'algoritmo

ho sentito dire che quel tipo di domanda (in-place o no) è stato messo apposta nel compito :P (se hai tempo e se capita all'esame, metticele un paio di righe ;D)

si, e se è una matrice usi d=m*n (cosa che sai già, penso)
(anche perché in quel tipo di algoritmi di solito il numero di passi dipende solo da quante celle ha quel determinato array, e non dipende dai particolari valori che assumono i vari elementi di tale array)

spe, quel log(n) che menzioni indica la stessa cosa, nel tuo contesto (quindi non è che lo moltiplichi per sé stesso)
bit ha costo log(n), ogni cosa al suo interno verrà eseguito log(n) volte, append è all'interno di bit,
e quindi append verrà eseguito log(n) volte
l'"altro" log(n) viene da un'altra considerazione: append, che viene eseguito log(n) volte, riceve un input che cresce di 1 ogni volta, fino ad un input di dimensione log(n)
analiticamente, le dimensioni in input sono: 1, 2, 3, ..., logn-2, logn-1, logn
se ne facciamo la somma diventa \sum_{i=1}^{logn} i = \frac{(logn)(logn+1)}{2} = O(log^{2}n)

Offline heavenriver

  • Global Moderator
  • Direttore di Dipartimento
  • *****
  • Post: 1060
  • FeedBack: +103/-67
  • z = z² + c
    • Mostra profilo
    • Sito web (Curriculum Vitae)
Re:Costi computazionali ed equazioni di ricorrenza
« Risposta #6 il: Ven 04 Gennaio, 10:34:02 - 2013 »
è che ciop costa O(4k|v|) solo all'ultima chiamata (o per essere più precisi O(4k-1|v|))
nelle chiamate precedenti costa O(4k-2|v|), O(4k-3|v|), O(4k-4|v|) e così via
se fai la somma di tutti questi costi viene O(4k|v|) (sarebbe \frac{1-4^k}{1-4}|v|)
e facendo la somma di questi costi è come se tenessi già conto del costo di cip
(invece di fare O(4k|v|)*O(k), fai \sum_{i=0}^{k-1} 4^i|v|)

Il ragionamento l'ho capito, ma in che senso "si tiene già conto del costo di cip"?

Il resto mi è chiarissimo :) Ancora grazie!

Offline Agilulfo

  • Neo-Laureato
  • **
  • Post: 79
  • FeedBack: +25/-0
    • Mostra profilo
Re:Costi computazionali ed equazioni di ricorrenza
« Risposta #7 il: Ven 04 Gennaio, 12:28:09 - 2013 »
(uso k invece di log4(n/v) per abbreviare, è del tutto equivalente quando lo si va a sostituire)
il costo di cip è O(k), se all'interno di cip ci sono:
- costi costanti O(1), allora il costo totale è semplicemente O(k)*O(1) (infatti O(1) si omette ed è dato per scontato)
- costi dipendenti dalla dimensione dell'input O(k') ma sempre "fissi", allora è O(k')+O(k')+...+O(k') (O(k) volte) = O(k')*O(k) = O(k' * k)
- costi dipendenti da k come ad esempio O(4k-1|v|) ma che variano durante l'esecuzione dell'algoritmo (come puoi notare dallo sviluppo delle equazioni di ricorrenza), allora provi a esprimerlo come una sommatoria (la sommatoria è già il costo totale, perché fai la somma da 0 a k)


in altre parole, il costo di cip va a influire quante volte vengono "ripetuti" i costi al suo interno:
- nei casi semplici, moltiplichi il costo di cip per il costo di quello che c'è dentro (la moltiplicazione non è altro che una somma ripetuta)
- nei casi più complessi, usi una sommatoria per esprimere il costo totale, per poter usare qualche formula nota

Offline heavenriver

  • Global Moderator
  • Direttore di Dipartimento
  • *****
  • Post: 1060
  • FeedBack: +103/-67
  • z = z² + c
    • Mostra profilo
    • Sito web (Curriculum Vitae)
Re:Costi computazionali ed equazioni di ricorrenza
« Risposta #8 il: Sab 05 Gennaio, 11:28:41 - 2013 »
Ok... era una cosa decisamente complicata.
Grazie ancora di tutta la pazienza che ci hai messo. Speriamo che a gennaio siano più clementi! :asd: :P

Offline Xzed

  • Studente di Dottorato
  • ***
  • Post: 228
  • FeedBack: +2/-9
    • Mostra profilo
Re:Costi computazionali ed equazioni di ricorrenza
« Risposta #9 il: Dom 17 Febbraio, 16:13:39 - 2013 »
Ho un dubbio sul metodo mistero del 14 Settembre 2011.Agilulfo ha scritto che l'equazione di ricorrenza è T(n) = 3*T(n/3) + c, però il metodo non ha un caso base con costo costante, ma nel caso base chiama il metodo boh, che ha costo O(n).Quindi non dovrebbe essere T(n) = 3*T(n/3) + O(n), che risolto col master theorem dà O(nlogn)??

Offline Agilulfo

  • Neo-Laureato
  • **
  • Post: 79
  • FeedBack: +25/-0
    • Mostra profilo
Re:Costi computazionali ed equazioni di ricorrenza
« Risposta #10 il: Dom 17 Febbraio, 19:05:05 - 2013 »
la "c" in
Citazione
T(n) = 3*T(n/3) + c
non indica il costo del caso base, ma il costo interno ad ogni chiamata ricorsiva:
in questo caso questo costo è costante perché, oltre alle chiamate ricorsive, ad ogni chiamata ricorsiva non effettua altre operazioni che dipendono dalla dimensione dell'input

il metodo boh ha costo lineare in funzione della dimensione dell'input, ma boh viene chiamato solo quando l'input n è minore o uguale 3, il che rende il costo del caso base praticamente costante (Theta(3))

Offline Xzed

  • Studente di Dottorato
  • ***
  • Post: 228
  • FeedBack: +2/-9
    • Mostra profilo
Re:Costi computazionali ed equazioni di ricorrenza
« Risposta #11 il: Lun 18 Febbraio, 01:54:09 - 2013 »
Hai ragione, avevo interpretato male il metodo.Grazie per la risposta  :)

Offline BlasusIng

  • Studente
  • *
  • Post: 4
  • FeedBack: +0/-0
    • Mostra profilo
Re:Costi computazionali ed equazioni di ricorrenza
« Risposta #12 il: Lun 07 Luglio, 18:44:23 - 2014 »
ciao a tutti, vi chiedo aiuto in merito al calcolo del costo computazionale per il metodo proposto all'esame del 19 febbraio 2013. Più precisamente, ho calcolato il costo del metodo join (mi dovrebbe venire O(n^2)) ma non riesco a calcolare il costo del metodo ricorsivo. Resto in attesa, vi ringrazio in anticipo. (Qui di seguito ho inserito il testo)

static void recurse(char[] s, int[] p) { // assumere p.length == s.length
       recurse(s, p, 0, s.length-1);
}

static void recurse(char[] s, int[] p, int i, int j) {
       if(i == j) p = 1;
       else {
          int k = (i + j) / 2;
          recurse(s, p, i, k);
          recurse(s, p, k+1, j);
          join(s, p, i, k, j);
       }
}

static void join(char[] s, int[] p, int i1, int i2, int i3) {
       for(int i = i1; i <= i2; i++)
          for(int j = i2+1; j <= i3; j++)
             if(s == s[j]) {
                p++;
                p[j]++;
             }
}

Offline Damiano16

  • Studente
  • *
  • Post: 27
  • FeedBack: +0/-0
    • Mostra profilo
Re:Costi computazionali ed equazioni di ricorrenza
« Risposta #13 il: Lun 29 Febbraio, 10:57:05 - 2016 »
 Salve ragazzi,qualcuno può spiegarmi come scrivere l'equazione di ricorrenza di un algoritmo?
Quali sono i metodi da utilizzare per risolvere l'esercizio 1 dell'esame?
Grazie 1000 Emoticon :)

Offline CIP

  • Professore Associato
  • *
  • Post: 500
  • FeedBack: +36/-7
    • Mostra profilo
Re:Costi computazionali ed equazioni di ricorrenza
« Risposta #14 il: Mer 02 Marzo, 09:56:56 - 2016 »
Salve ragazzi,qualcuno può spiegarmi come scrivere l'equazione di ricorrenza di un algoritmo?
Quali sono i metodi da utilizzare per risolvere l'esercizio 1 dell'esame?
Grazie 1000 Emoticon :)
Su youtube si trovano video che spiegano le varie tecniche che è possibile utilizzare. Puoi provare con questo per esempio
“If debugging is the process of removing software bugs, then programming must be the process of putting them in.” -Edsger Dijkstra