COSTO ALGORITMO

[xber-gigi]

Salve ragazzi!
Help!
Come si calcola il costo di un algoritmo???

[misterx]

uhm.......

forse dipende da quanto è costato in ricerche: milioni, miliardi ?

se ipotizzi poi che chi ne beneficerà potrà farci dei bei soldoni, magari è meglio "brevettarlo" ?

quanto è costato il jpeg che è free ???

magari alla fine è costato solo sacrosanta passione :)



certo che se scrivi un algoritmo che simula la reale riproduzione di cellule cancerogene di qualunque tipo, la questione si fa assai delicata

[xber-gigi]

Originariamente inviato da misterx
uhm.......

forse dipende da quanto è costato in ricerche: milioni, miliardi ?

se ipotizzi poi che chi ne beneficerà potrà farci dei bei soldoni, magari è meglio "brevettarlo" ?

quanto è costato il jpeg che è free ???

magari alla fine è costato solo sacrosanta passione :)

MA NO!!!! :muro: NON INDENDEVO QUESTO!!!
Parlo di costo di un algoritmo riguardo la parte teorica della programmazione!

[maxithron]

Dipende anche molto dal linguaggio utilizzato perchè il costo può variare in base alle "ore" o in base alle "righe" scritte.

[misterx]

allora

tu hai scritto un algoritmo ?

[PGI]

Originariamente inviato da xber-gigi
Parlo di costo di un algoritmo riguardo la parte teorica della programmazione!

Forse intendi l'efficienza di un algoritmo?

[xber-gigi]

Originariamente inviato da PGI
Forse intendi l'efficienza di un algoritmo?

Intendo la complessità di tempo di un algoritmo.

[maxithron]

Originariamente inviato da xber-gigi
Intendo la complessità di tempo di un algoritmo.

dove per "complessità di tempo" ti riferisci al tempo che hai impiegato per svilupparlo?

[PGI]

Originariamente inviato da xber-gigi
Intendo la complessità di tempo di un algoritmo.

Allora mi tiro indietro prima di dire qualche stupidaggine. Non so cosa sia.

[lexleo]

Originariamente inviato da xber-gigi
Intendo la complessità di tempo di un algoritmo.

Allora..se non ricordo male la 'complessità' di un algoritmo viene rappresentata con il simbolo teta-grande e viene calcolata prendendo la massima complessità tra le istruzioni che compongono l'algoritmo..ad esempio l'istruzione assegnamento di una variabile ha complessità 1, un ciclo iterativo da 1 a n ha complessità n..
Spero di essere stato chiaro anche se lo dubito...:rolleyes: :rolleyes:

[ghego]

dipende ogni algoritmo ha complessita diversa
un insertion sort ha un teta grande (n^2), per mergesort di n(logn) ad esempio

cmq con O (o grande) determini il tempo massimo, omega il minore e teta il tempo medio di esecuzione.

poi dipende dalla ricorsivita del programma.

[xber-gigi]

Originariamente inviato da lexleo
Allora..se non ricordo male la 'complessità' di un algoritmo viene rappresentata con il simbolo teta-grande e viene calcolata prendendo la massima complessità tra le istruzioni che compongono l'algoritmo..ad esempio l'istruzione assegnamento di una variabile ha complessità 1, un ciclo iterativo da 1 a n ha complessità n..
Spero di essere stato chiaro anche se lo dubito...:rolleyes: :rolleyes:

Esatto!:winner:
Tu mi hai capito! Era questo quello che volevo dire!

Ma sapresti farmi un piccolo esempio semplice?!?!
Anche se ho capito vorrei un esempio della complessità finale di un esempio di algoritomo!

[lexleo]

:D :D :D :D :D :D :D :D
se non ti spiace uso il C++ per l'esempio

....
sum = 0; // teta-grande = 1
for (j=1; j<=n; j++)
for (i=1; i<=j; i++)
sum++; // teta-grande = n2 (n al quadrato)
for (k=0; k<n; k++)
A[k] = k; // teta-grande = n
...

La complessità dell'algoritmo è quindi teta-grande = n2 (n al quadrato)

[maxithron]

Arghhh!!!! :ops:

Meno male che lexleo ha capito!!!

Continuavo a pensare che ti riferissi a:

"Ho scritto un algoritmo, quanti euri mi devo far dare?"

[lexleo]

Originariamente inviato da maxithron
Arghhh!!!! :ops:

Meno male che lexleo ha capito!!!

Continuavo a pensare che ti riferissi a:

"Ho scritto un algoritmo, quanti euri mi devo far dare?"


:eheh: :eheh: :eheh:

[xber-gigi]

Originariamente inviato da lexleo
:D :D :D :D :D :D :D :D
se non ti spiace uso il C++ per l'esempio

....
sum = 0; // teta-grande = 1
for (j=1; j<=n; j++)
for (i=1; i<=j; i++)
sum++; // teta-grande = n2 (n al quadrato)
for (k=0; k<n; k++)
A[k] = k; // teta-grande = n
...

La complessità dell'algoritmo è quindi teta-grande = n2 (n al quadrato)

bhe si preferirei il C con un esempio pratico numerico ed elemenare!
tnx!

[Luc@s]

Originariamente inviato da maxithron
Continuavo a pensare che ti riferissi a:

"Ho scritto un algoritmo, quanti euri mi devo far dare?"

Anche io !

[verloc]

Solo nel mondo dei sogni (USA) si può brevettare un algoritmo.
Nel resto del mondo inteligente(UE) NO.

In Italia si possono brevettare solo prodotti industriali o software(quasi-mai) che determinano un salto tecnologico nello specifico campo di ricerca.

Mettetevi l'animo in pace. :D


Ps.Tutti gli algoritmi stanno nello stesso posto:il mondo delle idee,
basta solo scovarli.

[Frank1962]

io sapevo per esempio che il sistema di compressione LZW fosse brevettato e chi lo usasse, anche in europa, dovesse pagare!

per esempio so che photoshop deve pagare le royaltys per averlo implementato in photoshop per comprimere le immagini tiff (che se non non potrebbero essere compresse dato il carattere del formato tiff)

edit: ma poi io non ho mai capito ....ma che differenza c'è tra copyright (per esempio quello dei videogiochi, programmi, ecc..) e il brevetto?

[cionci]

Anche il GIF compresso usa LZW...

http://burnallgifs.org/

Comunque torniamo in topic...

[bsummer]

Supponi di avere un array di 1000 elementi e volerlo ordinare

un metodo può essere


for(i=0;i<999;i++) {
for(j=1;j<1000;j++) {
if (array[i]>array[j]) {
tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
}
}


Non consideriamo il tempo esecuzione dell'if e dei 3
assegnamenti come operazioni distinte ma facciamo finta che sia
una unica istruzione "I". Si può facilmente calcolare come "I"
venga eseguita nel caso peggiore 999*999 volte ovvero, se
poniamo N= lunghezza dell'array, (N-1)*(N-1) = (N^2)-(2N)+1.
Per valori di N molto grandi il "+1" e "-2N" diventano trascurabili
se paragonati all'(N^2).
Tale algoritmo si dirà avere complessità O(N^2) ovvero il numero
di iterazioni aumenta esponenzialmente (al quadrato) man mano
che N cresce.

Vediamo ad esempio il MergeSort, altro algoritmo di ordinamento


void merge(int[] a, int lo, int hi)
{
int i, j, k, m, n=hi-lo+1;
int[] b=new int[n];

k=0;
m=(lo+hi)/2;

for (i=lo; i<=m; i++) b[k++]=a[i];
for (j=hi; j>=m+1; j--) b[k++]=a[j];
i=0; j=n-1; k=lo;
while (i<=j)
if (b[i]<=b[j]) a[k++]=b[i++];
else a[k++]=b[j--];
}

void mergesort(int[] a, int lo, int hi) {
if (lo<hi) {
m = (lo + hi) / 2;
mergesort (a, lo, m);
mergesort (a, m+1, hi);
merge (a, lo, hi);
}
}

L'algoritmo si basa su due funzioni, la merge nella quale si
effettuano sostanzialmente N+(N/2)= 3N/2 operazioni e quindi ha
complessità O(N) mentre per la funzione ricorsiva mergesort è
facile ricavarsi che nel caso vi siano 1 o 2 elementi ha complessità
costante C mentre con N>2 vingono eseguite log N attivazioni
ricorsive. Ne deriva che la complessità totale è O(Nlog N).

[Maverick82^]

Originariamente inviato da bsummer


Vediamo ad esempio il MergeSort, altro algoritmo di ordinamento


void merge(int[] a, int lo, int hi)
{
int i, j, k, m, n=hi-lo+1;
int[] b=new int[n];

k=0;
m=(lo+hi)/2;

for (i=lo; i<=m; i++) b[k++]=a[i];
for (j=hi; j>=m+1; j--) b[k++]=a[j];
i=0; j=n-1; k=lo;
while (i<=j)
if (b[i]<=b[j]) a[k++]=b[i++];
else a[k++]=b[j--];
}

void mergesort(int[] a, int lo, int hi) {
if (lo<hi) {
m = (lo + hi) / 2;
mergesort (a, lo, m);
mergesort (a, m+1, hi);
merge (a, lo, hi);
}
}

L'algoritmo si basa su due funzioni, la merge nella quale si
effettuano sostanzialmente N+(N/2)= 3N/2 operazioni e quindi ha
complessità O(N) mentre per la funzione ricorsiva mergesort è
facile ricavarsi che nel caso vi siano 1 o 2 elementi ha complessità
costante C mentre con N>2 vingono eseguite log N attivazioni
ricorsive. Ne deriva che la complessità totale è O(Nlog N).


Per essere un pò più chiari, spero che non te la prendi bsummer ;), tutti gli algoritmi ricorsivi sono esprimibili con equazioni di ricorrenza. Quindi per calcolare il costo di un algorimo ricorsivo dobbiamo risolvere la relativa equazione. Nel caso di mergesort abbiamo che l'equazione di ricorrenza è:

K(n) = 2K(n/2) + O (n)

Cos'è 2K(n/2) ? ---> 2 è il numero di chiamate ricorsive a MergeSort e n/2 è la dimensione dell'input delle chiamate ricorsive. Infatti inel codice che ha postato bsummer abbiamo che m = (lo + hi) / 2;

Cos'è O(n)? ---> in mergesort usiamo la procedura merge, quindi dobbiamo tener conto del suo tempo di esecuzione

Ora la risoluzione di questa equazione (si possono utilizzare 3 metodi tra i quali il Master theorem, che non spiego ;) ) dà come risultato O(nlogn).

Ma perchè log n? Cosa centra? ----> in informatica i logaritmi compaiono in presenza di algoritmi che dividono l'input in due parti (come appunto mergesort, quicksort e altri...) oppure in algoritmi
basati su strutturre dati come gli alberi (l'altezza di un albero infatti
è >= log * il numero di nodi , quindi le operazioni sugli alberi sono eseguite in tempo O(logn) ). Quindi se iniziamo con un dato di dimensione n , il numero di volte che possiamo dividerlo a metà prima di ottenere 1 è log n.

Quelli come me che studiano informatica, credo che saranno daccordo nel dire che questi aspetti dell'informatica teorica sono molto utili al fine di capire come cavolo si progetta un algoritmo/software. Dalle mie parti si pensa il contrario ....... :rolleyes:

Cmq non sarebbe male inserire qualche tutorial ;)

[bsummer]

Originariamente inviato da Maverick82^
Per essere un pò più chiari, spero che non te la prendi bsummer ;)

Figurati :D
Rileggendo il mio post ammetto di essere stato fin troppo sbrigativo nel descrivere la complessità del mergesort. Hai fatto bene ad intervenire ;)

[maxithron]

Ed inoltre, per ulteriore nozione, è giusto ricordare (parlando di mergesort) che la sua proprietà fondamentale, risulta essere l'ordinare "N elementi in un tempo proporzionale a N log N(R. Sedgewick)" anche nel caso peggiore implementando l'algoritmo Heapsort.