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... se aggiungi lista.sort() io ottengo: Lista generata Max time: 0.09 Sort time: 2.52 ciao! pietro _______________________________________________ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
