Il giorno ven, 03/09/2010 alle 21.44 +0200, Pietro Zambelli ha scritto: > In data venerdì 3 settembre 2010 21:10:11, Giuseppe Amato ha scritto: > > >Ma il problema vero è che il sort ha costo più che lineare, mentre il > > > > > >max ha costo lineare > > > > Non mi sono mai occupato di max finding quindi non so se è più veloce o > > meno, ho cercato qualcosa, ma con scarsi risultati, mi puoi indicare > > qualche risorsa dove trovare informazioni? > > > > Però mi sono occupato di sorting e il caso O(n) è uno dei peggiori > > (utilizzando algoritmi shell sort o quick sort), mentre O(log(n)) è più > > probabile ed è comunque minore di O(n) (200x2e6=2e8, > > 200xlog(2e6)=~1300,2e6xlog(200)=~4e6). > > > > Ma ripeto potrei sbagliare, allora ho scritto il semplice script di seguito > > e vi consiglio di provarlo e confrontare i risultati. > > > > > > > > #------------ > > > > import time > > > > import random > > > > > > > > n=2000000 > > > > lista=[] > > > > for i in range(n): > > > > lista.append(random.randint(0,10000000)) > > > > > > > > print 'Lista generata' > > > > start=time.clock() > > > > max(lista) > > > > print 'Max time:',time.clock()-start > > > > > > > > start=time.clock() > > > > print 'Sort time:',time.clock()-start > > > > #----------------- > > > > > > > > Il sort vince sempre, va pari se invece di interi si devono confrontare > > classi. Ma il nostro amico doveva valutare interi se non ho capito male. > > manca l'ordinamento della lista...
Ah, ecco... (il bello è che io l'avevo aggiunto, ma sbadatamente _prima_ di "start=time.clock()"...) > se aggiungi lista.sort() io ottengo: > > Lista generata > Max time: 0.09 > Sort time: 2.52 > ... che in effetti è dell'ordine di grandezza di... In [1]: 0.09 * log(2000000, 2) Out[1]: 1.8838411712391756 ciao Pietro _______________________________________________ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
