[ Programmazione ] Come si calcola il costo e il tempo di un algoritmo??

[cimmiv]

Vorrei capire in pratica come si fanno a calcolare sul libro c'è tanto fumo e niente arrosto !! Non spiega nel dettaglio come fare ... Mi potete Aiutare ??

[Daniels118]

Ma intendi quello di esecuzione o di realizzazione?

[toyman90]

Originariamente inviato da cimmiv

Vorrei capire in pratica come si fanno a calcolare sul libro c'è tanto fumo e niente arrosto !! Non spiega nel dettaglio come fare ... Mi potete Aiutare ??

e poi in che linguaggio? Un esempio in java:

long oraInizio= System.nanoTime();
// qui il tuo algoritmo
long tempoTrascorso = System.nanoTime() - oraInizio;

in java puoi anche decidere che al posto dei nanosecondi la precisione sia in millisecondi:

System.currentTimeMillis();

[tomminno]

Originariamente inviato da cimmiv

Vorrei capire in pratica come si fanno a calcolare sul libro c'è tanto fumo e niente arrosto !! Non spiega nel dettaglio come fare ... Mi potete Aiutare ??

Sinceramente il tempo di un algoritmo non l'ho mai sentito, generalmente si parla di complessità computazionale e spaziale.
L'unico modo in cui il tempo entra nella definizione di algoritmo è che deve essere finito.

[Daniels118]

Ma anche qui ci sarebbe da chiedersi se il tempo in cui deve essere finito è quello di esecuzione o di consegna

La complessità è tipicamente una funzione della dimensione dei dati da elaborare.
La forma di tale funzione deve essere determinata ragionando sull'algoritmo stesso.

Le forme più comuni sono queste:
1: la complessità non dipende da nulla (es. accedere ad un elemento di un array);
n: la complessità è direttamente proporzionale alla dimensione dei dati; questa complessità corrisponde in genere ad un ciclo for (es. calcolare il massimo di un array);
n*m*l...; quando ci sono diversi cicli for annidati, ognuno dei quali si ripete rispettivamente n, m, l... volte;
n^x; come il precedente, ma con n=m=l=...
n*log(n): due cicli for annidati, ma quello interno riduce le sue iterazioni per ogni iterazione di quello esterno.

Escludendo algoritmi banali, la complessità computazionale è generalmente abbastanza difficile da calcolare, soprattutto quando le iterazioni dipendono non dal numero, ma dal valore dei dati (che ovviamente non è noto a priori).
Per lo stesso motivo di un algoritmo vengono calcolate anche le complessità nei casi "migliore", "peggiore" e "medio".