Dom 18 Agosto, 07:42:42 - 2019

Autore Topic: Costi esame del 15/07/2010  (Letto 3673 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline Cafendra

  • Neo-Laureato
  • **
  • Post: 59
  • FeedBack: +3/-2
    • Mostra profilo
Costi esame del 15/07/2010
« il: Mar 03 Aprile, 17:45:46 - 2012 »
Ragazzi qualcuno di voi i saprebbe dare la risposta al Problema 1 parte a,b,c dell'esame di Algoritmi e Strutture dati del 15/07/2010??

Link : http://www.dis.uniroma1.it/~fiii/esame/AA%202009-10/4.appello--15-07-2010/algoritmi/fiii20100715.pdf

Grazie

Agilulfo

  • Visitatore
Re: Costi esame del 15/07/2010
« Risposta #1 il: Mar 03 Aprile, 20:52:58 - 2012 »
n = numero di elementi = dimensione dell'input

a) n ricorsioni con un ciclo interno che gira n, n-1, n-2, ..., 2, 1 volte --> n(n-1)/2 (=somma dei primi n numeri interi)
quindi O(n^2)

b) ad ogni passo ci sono 2 chiamate ricorsive, ciascuna relativa a metà array (l'altezza dell'albero di ricorsione è log in base 2 di n)
quindi O(2^log2(n)) = O(n)

c) size() è O(1) per entrambe le implementazioni (ci sarà un campo intero con la dimensione)
per ArrayList la get(i) è O(1), quindi il costo di somma3 è O(n)
per LinkedList la get(i) costa O(n) nel caso peggiore, quindi il costo di somma3 è O(n^2), volendo si può usare il ragionamento del punto a) dove la get(0) costa 1, la get(1) costa 2, ... la get(n-2) costa n-1 e la get(n-1) costa n :P

Offline Cafendra

  • Neo-Laureato
  • **
  • Post: 59
  • FeedBack: +3/-2
    • Mostra profilo
Re: Costi esame del 15/07/2010
« Risposta #2 il: Mer 04 Aprile, 15:05:48 - 2012 »
Ok, le parti a e b le ho capite.
per quanto riguarda la parte c)

Somma3(list.....) chiama somma3Aux che costa o(n) e quindi il costo è o(n)
Somma3(Array) chiama somma3(List...) che a sua volta chiama somma3Aux che costa o(n), quindi la prima chiamata costa o(1) la seconda o(n) costo o(n), perché dici o(n^2)??


Grazie mille per la risposta.

Agilulfo

  • Visitatore
Re: Costi esame del 15/07/2010
« Risposta #3 il: Mer 04 Aprile, 18:53:48 - 2012 »
se noti, _somma3Aux prende come parametro una List (la classe astratta), quindi il costo di tale metodo dipende dalla particolare implementazione di List (ArrayList o LinkedList) che gli passi (O(n) e O(n^2) rispettivamente)

immagino, mi corregga in caso il prof ::), che sul testo ci sia un errore
Codice: [Seleziona]
public static int somma3(ArrayList<Integer> lista) {
  return somma3(lista);
}

dovrebbe essere return _somma3Aux(lista), altrimenti il metodo richiamerebbe sé stesso ricorsivamente, senza terminare non essendoci passo base, fino allo stack overflow :P


ah, riguardo alla LinkedList penso che i costi siano 1 + 2 + ... + (n/2-1) + n/2 + (n/2+1) + ... + 2 + 1 visto che mi pare sia implementata come una lista doppiamente collegata (puoi iniziare a scorrere sia dall'inizio che dalla fine):
comunque è sempre O(n^2), visto che è la somma dei numeri naturali fino a n/2 moltiplicata per 2


edit:
Somma3(Array) chiama somma3(List...)
se qui intendi che somma3(ArrayList...) chiama somma3(LinkedList...), in Java (o in altri linguaggi OO) non penso sia possibile fare un cast tra sottoclassi (ArrayList e LinkedList) della stessa superclasse (List) (anche perché "dentro" sono implementati in modo diverso)
« Ultima modifica: Mer 04 Aprile, 19:05:36 - 2012 da Agilulfo »

Offline Cafendra

  • Neo-Laureato
  • **
  • Post: 59
  • FeedBack: +3/-2
    • Mostra profilo
Re: Costi esame del 15/07/2010
« Risposta #4 il: Gio 05 Aprile, 18:38:49 - 2012 »
Grazie mille, ti chiedo un'ulteriore aiuto su un'altro esempio di esame sul quale ho dei dubbi :

http://www.dis.uniroma1.it/~fiii/esame/AA%202008-09/5.appello--14-09-2009/20090914.pdf

io l'ho pensato così :
 a) k=n+m (componenti vettore array1 e array2), ora chiama marge(array1,array2,ris) costo del merge O(k log k), poi chiama quicksort  su ris che risulta essere ordinato e costa quindi O(nlogn). costo totale O(K LOG K).

b) chiama due volte quicksort su due array differenti costo O(n^2) poi chiama merge.  costo totale O(n^2).

giusto?

ti ringrazio .
« Ultima modifica: Gio 05 Aprile, 19:20:53 - 2012 da Cafendra »

Agilulfo

  • Visitatore
Re: Costi esame del 15/07/2010
« Risposta #5 il: Gio 05 Aprile, 21:17:08 - 2012 »
a) merge ha costo O(n+m) (nota che è merge, non mergesort), il quicksort costa O((n+m)^2) nel caso peggiore
quindi O((n+m)^2)

This algorithm [a tuned quicksort] offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.
many, non all :P


b) quicksort su array1 O(n^2), quicksort su array2 O(m^2), merge O(n+m)
quindi O(n^2 + m^2 + n + m) = O(n^2 + m^2)


c) mergesort è O(k logk) anche nel caso peggiore
quindi a) O((n+m)log(n+m) + n + m) = O(nlog(n+m) + mlog(n+m) + n + m) = O(nlog(n+m) + mlog(n+m))
e b) O(nlogn + mlogm + n + m) = O(nlogn + mlogm)

Offline Cafendra

  • Neo-Laureato
  • **
  • Post: 59
  • FeedBack: +3/-2
    • Mostra profilo
Re: Costi esame del 15/07/2010
« Risposta #6 il: Ven 06 Aprile, 11:36:07 - 2012 »
Grandissimo.

Offline Cafendra

  • Neo-Laureato
  • **
  • Post: 59
  • FeedBack: +3/-2
    • Mostra profilo
Re:Costi esame del 15/07/2010
« Risposta #7 il: Gio 12 Aprile, 20:42:58 - 2012 »
Vediamo questo :

http://www.dis.uniroma1.it/~fiii/esame/AA%202009-10/3.appello--10-06-2010/algoritmi/fiii20100610.pdf


secondo me :
a)
0(n)  e O(2^x)
b)O(nlogn) O((2^x)^(2^X))
c)O(n*nlogn)  ??

e questo :
http://www.dis.uniroma1.it/~fiii/esame/AA%202009-10/staordinario--23-04-2010/algoritmi/fiii20100423.pdf
a) O(n)
b) O(2*logn) = O(n)
c)O(n^2)

Grazie





« Ultima modifica: Gio 12 Aprile, 20:50:42 - 2012 da Cafendra »

Agilulfo

  • Visitatore
Re:Costi esame del 15/07/2010
« Risposta #8 il: Ven 13 Aprile, 00:33:44 - 2012 »
Vediamo questo :
http://www.dis.uniroma1.it/~fiii/esame/AA%202009-10/3.appello--10-06-2010/algoritmi/fiii20100610.pdf
secondo me :
a)
0(n)  e O(2^x)
b)O(nlogn) O((2^x)^(2^X))
c)O(n*nlogn)  ??


a) credo O(log10(n)) che ad ogni ciclo il valore n viene diviso per 10
in funzione della dimensione dell'input log10(2^x) = log2(2^x)/log2(10) = O(x)


b) il ciclo interno fa n, n-1, n-2, ..., n/2+1, n/2 per n/2 volte (ciclo esterno), come se fosse
SUM(k=n/2 to n)(k) = SUM(k=1 to n)(k) - SUM(k=1 to n/2)(k) = ... = O(n^2)
l'input è un vettore, quindi la lunghezza dell'array è la dimensione dell'input (niente calcoli con i bit :P )


c) il costo è quadratico (metodo2) rispetto all'input dato dall'output del metodo1, quindi O((log(n))^2) (ho messo direttamente log invece di log10 che tanto facendo un cambio di base la costante a dividere "scompare" asintoticamente)
in funzione della dimensione dell'input O(x^2)





e questo :
http://www.dis.uniroma1.it/~fiii/esame/AA%202009-10/staordinario--23-04-2010/algoritmi/fiii20100423.pdf
a) O(n)
b) O(2*logn) = O(n)
c)O(n^2)
Grazie


a) come te

b) come te (immagino che quel * sia in effetti un ^)
giusto per divertirci la relazione di ricorrenza è T(n) = 2*T(n/2) + O(1) che risolta viene proprio O(n)

c) ok  ;)




ah, se qualcosa non è chiaro potrei anche aver fatto errori, non prendere tutto quello che scrivo per soluzioni corrette al 100% :P
« Ultima modifica: Ven 13 Aprile, 00:35:31 - 2012 da Agilulfo »

Offline Cafendra

  • Neo-Laureato
  • **
  • Post: 59
  • FeedBack: +3/-2
    • Mostra profilo

Agilulfo

  • Visitatore
Re:Costi esame del 15/07/2010
« Risposta #10 il: Mar 17 Aprile, 14:43:39 - 2012 »
ci provo :P

cip() finisce di girare quando (4^k)*|v| = n (sarebbe >=, ma vabe, tanto ci metteremmo l'intero superiore quando andiamo sui logaritmi e asintoticamente è al max meno di 4 volte più grande di n)

quindi passando ai logaritmi k = log4(n/|v|) = numero di volte che fa 2 volte ciop(), il quale costa |a| dove a è l'array che gli viene passato, costo prima parte = O(|v|*log4(n/|v|))

per la seconda parte, a cucu(), che costa O(z) dove z è la dimensione dell'array passato, viene passato in input un array con dimensione massima 4*n (pensa al caso dell'array v poco più piccolo di n, e questo viene quadruplicato un'altra volta prima di arrivare al passo base), quindi O(n)

complessivamente O(|v|*log4(n/|v|) + n)

per il punto b) credo basti sostituire gli n con 2^x, credo :P

c) ciop() raddoppia l'array e replica il suo contenuto in tutte le celle, quindi cip() fornirà in input a cucu() un array grande 16 (4<10 e 16>10) con tutti gli elementi uguali a 1, poi cucu() fa la somma degli elementi e quindi in output avrai l'array w di lunghezza 1 con valore in w[0] = 16


edit: ah un attimo, ciop() esegue su un array sempre più grande, quindi è sbagliata quella parte :P intanto ci penso :D

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|))
« Ultima modifica: Mar 17 Aprile, 15:16:34 - 2012 da Agilulfo »

Offline Cafendra

  • Neo-Laureato
  • **
  • Post: 59
  • FeedBack: +3/-2
    • Mostra profilo
Re:Costi esame del 15/07/2010
« Risposta #11 il: Mar 17 Aprile, 18:02:24 - 2012 »

Agilulfo

  • Visitatore
Re:Costi esame del 15/07/2010
« Risposta #12 il: Mar 17 Aprile, 21:46:44 - 2012 »
ad occhio O(m*n) e O(k) dove k=m*n

Offline Cafendra

  • Neo-Laureato
  • **
  • Post: 59
  • FeedBack: +3/-2
    • Mostra profilo
Re:Costi esame del 15/07/2010
« Risposta #13 il: Gio 19 Aprile, 18:34:34 - 2012 »

Offline s4lv0

  • Studente
  • *
  • Post: 9
  • FeedBack: +0/-2
    • Mostra profilo
Re:Costi esame del 15/07/2010
« Risposta #14 il: Lun 23 Aprile, 14:39:36 - 2012 »
anche io sono curioso, questo non è facilissimo...
Non dovremmo identificare con parametri diversi  il numero di righe/colonne della matrice grande e il numero di righe/colonne della matrice piccola?