Newsgroup: it.comp.lang.c
Titolo: bontà di un algoritmo

Ciao
leggevo di "tempo logaritmico" che indicava il costo in tempo che un 
algoritmo può impiegare nella sua esecuzione....cosa si intende in pratica?
grazie


Detto con le mani, dato un parametro N (per esempio la
dimensione di una matrice quadrata) il tempo che impiega
l'algorimo è proporzionale al logaritmo di N. La costante
di proporzionalità potrà essere enorme per un piccolo
microcontrollore o piccolissima per un mainframe, ma il
confronto ha senso tra algoritmi diversi sulla stessa
macchina.
ciao
Apx.
-- 
Vorrei morire dormendo come mio nonno
e non urlando come i suoi passeggeri.


Oltre a questo, soprattutto è un buon indicatore di quanto è
"scalabile" un'algoritmo al crescere/decrescere dei dati in input. Un
NlogN e un N^2 saranno più o meno uguali per un N piccolo, ma al
crescere di N la differenza è importante...
Ciao!

 algoritmo può impiegare nella sua esecuzione....cosa si intende in pratica?
[...]
Solo un chiarimento, il tempo logaritmico non è un parametro assoluto
che ti permette di misurare il costo computazionale di un algoritmo.
Con questo voglio dire che il tempo di esecuzione *puo'* essere loga-
ritmico come puo' anche non esserlo. Detto N il parametro che influenza
significativamente il tempo di calcolo (e di solito è proporzionale
alla dimensione dell'insieme dei dati da elaborare), gran parte degli
algoritmi hanno un tempo di esecuzione proporzionale a una delle
seguenti funzioni:
        1: tempo costante
    log N: il programma rallenta leggermente (log N raddoppia
           quando N diventa N^2), vedi Link 1 in fondo
        N: tempo di esecuzione lineare, è la cosiddetta situzione
           "ottimale" per un algoritmo che deve elaborare N dati in input.
  N log N: se N vale 10^7, N log N è circa 10^8, vedi Link 2 in fondo 
   N^2, N^3: sono algoritmi applicabili solo a problemi piccoli, sono
           molto "costosi"
      2^N: se N raddoppia, il tempo viene elevato al quadrato: pochi
           algoritmi hanno questo tempo di esecuzione, in generale sono
           soluzioni per piccoli problemi altrimenti irrisolubili
Link 1:
http://www.wolframalpha.com/input/?i=Plot[Log[N],+{N,+0,+1000}]&a=*FunClash.Log-_*Log10.Log-
Link 2:
http://www.wolframalpha.com/input/?i=Plot[N*Log[N],+{N,+0,+1000}]&a=*FunClash.Log-_*Log10.Log-
[copia tutto l'indirizzo, non cliccare sulla parte in blu]
Libro consigliato:
http://www.ibs.it/code/9788871921518/sedgewick-robert/algoritmi-c.html
-- 
Non puoi insegnare qualcosa ad un uomo. You cannot teach a man anything.
Lo puoi solo aiutare   --  Galileo  Galilei  --   You can only help him
a scoprirla dentro di sé.                        discover it in himself.
Vincenzo Mercuri

            soluzioni per piccoli problemi altrimenti irrisolubili
Sigh... magari fossero pochi! ;)
Quasi quasi mi verrebbe da dire che "quasi tutti i problemi
interessanti" hanno quel problema qui. Ovviamente e' un'esagerazione, ma
direi che e' piu' vicino la mia esagerazione (ovvero considerare non
interessanti i problemi non EXPTIME-P) rispetto che dire che "pochi
algoritmi" sono EXPTIME. Purtroppo sono *tantissimi*. 
E nemmeno parlando di quelli con worse cattivo e average buono
(simplex). ;)
-- 
-riko
http://www.enrico-franchi.org/
http://rik0-techtemple.blogspot.com/

 algoritmi" sono EXPTIME. Purtroppo sono *tantissimi*.
Io ho parlato di pochi algoritmi, non pochi problemi. Le due cose non
coincidono. *Pochi* algoritmi EXPTIME sono applicabili nella pratica.



Io direi che è il contrario: il problema è interessante appunto perché
(ancora) non esiste un algoritmo migliore! :-D
Ciao!

 (ancora) non esiste un algoritmo migliore! :-D
E' un punto di vista interessante, in effetti. E tutto sommato e' anche
il mio.
Avevo scritto da qualche parte la dimostrazione che P==NP, ma me la sono
persa. Vabbe', ci pensera' qualcun altro. ;)


 persa. Vabbe', ci pensera' qualcun altro. ;)
ahah, LOL!
Ciao Jack


ehehe, pensavo che la dimostrazione fosse troppo lunga per entrare nel
margine troppo stretto di quel post ;-)
Ciao!

 margine troppo stretto di quel post ;-)
Azz, abbiamo bisogno di un Andrew Wiles dell'informatica ;-)


 margine troppo stretto di quel post ;-)
:P



grazie a tutti :)

 *Pochi* algoritmi EXPTIME sono applicabili nella pratica.
Dipende cosa intendi con "applicabili nella pratica". Ovviamente cosi'
come sono non sono applicabili perche' ci va troppo. E quindi si parte
con le varie euristiche o addirittura con soluzioni approssimate, certo.
Ma non esistere e non essere fattibili e' ben diverso.


 Ma non esistere e non essere fattibili e' ben diverso.
Enrico, forse sono io che non riesco a spiegarmi, ma ti assicuro che
per me è veramente frustrante parlare del mais ed essere controbattuto
sull'ananas.
PS: esempio di non applicabilità nella pratica: l'algoritmo comincia
quando ho 29anni e finisce quando ne avrò (?) 70.


 quando ho 29anni e finisce quando ne avrò (?) 70.
Ovviamente. Ma il fatto che un algoritmo non possa essere usato e'
diverso dal non esistere. E' chiaramente un grosso problema il fatto che
molti problemi non possano essere risolti con algoritmi con costo
esponenziale. Ma questo non vuole dire che gli algoritmi non esistano (o
siano pochi). Anzi, *purtroppo* sono tanti.
Lascio poi stare i discorsi su soluzioni approssimate o euristiche
astute che nella maggior parte dei casi (o per lo meno di quelli
interessanti -- e non per dimensione, per struttura --) portano
l'algortimo a costo *medio* sui suddetti casi a costi accettabili. Ma
questo e' tutto un altro discorso.


 siano pochi). Anzi, *purtroppo* sono tanti.
Io capisco bene il tuo punto di vista e torno a dire che non ho escluso
l'eventualità che ne esistano tanti. La frase che ha originato l'obie-
zione è "pochi algoritmi hanno questo tempo di esecuzione, in generale
sono soluzioni per piccoli problemi altrimenti irrisolubili". Con "pochi
algoritmi hanno questo tempo di esecuzione" intendo dire che
_nella pratica_ pochi algoritmi sono EXPTIME, altrimenti non avrei
parlato di tempo di esecuzione, avrei potuto dire "pochi algoritmi
funzionanti", o "pochi algoritmi in uso", non era sicuramente una sen-
tenza sugli algoritmi in generale. Questo viene meglio spiegato quando
dico "soluzioni per piccoli problemi altrimenti irrisolubili", proprio
per sottolineare il fatto che la scelta di un algoritmo esponenziale è
l'ultima spiaggia nell'implementazione di una soluzione a un problema
concreto.


 concreto.
Ok. Sono d'accordo.



non c'entra col discorso ma sapete che sono un precisino.
Se si considera un algoritmo su una precisa macchina, se l'algoritmo
ci mettesse 70-29 = 41 anni, per la legge di Moore aspettando 18 mesi
correrebbe in 41/2 = 20.5 anni. Facendo due conti veloci (sicuramente
errati) avresti il risultato per i 40 anni :-)
Ciao!


LoL...si oppure immagina che tra 41 anni ci sarà un processore capace
di eseguire lo stesso algoritmo in un minuto, voglio dire è ottimo, ma
dovremmo sempre aspettare 41 anni :D


 persa. Vabbe', ci pensera' qualcun altro. ;)
 
Sì, era in Homer³
-- 
                     Dona i tuoi cicli di clock alla ricerca!
 
http://boinc.berkeley.edu/
                          --------------------
   Queste donne micidiali!  Non si puo' vivere ne' con loro ne' senza
   di loro.
   		-- Aristofane