>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.
Giuseppe
_______________________________________________
Python mailing list
Python@lists.python.it
http://lists.python.it/mailman/listinfo/python
