2010/9/3 Giuseppe Amato <giuam...@gmail.com>: > 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? >
In un array non ordinato e` necessario visitare tutti gli elementi una volta per stabilirne il massimo, quindi l'algoritmo e` O(N) in tempo e O(1) in spazio perche` ti conservi il massimo corrente. > 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). > Io non so quanto e come tu ci abbia lavorato ma se non ti sei confuso con la notazione vorrei proprio sapere come fai il sorting tu! Nello stato dell'arte degli algoritmi di sorting O(N) e` l'andamento _desiderato_! ( http://en.wikipedia.org/wiki/Sorting_algorithm ) Tipicamente gli algoritmi buonivanno come O(nlog(n)), il TimSort di Python va mediamente un po` meglio come O(log(N!)) anche se non proprio formalmente, che e` comunque molto diverso da un andamento lineare (che in questo caso e` gia` problematico) per N abbastanza grande. > Ma ripeto potrei sbagliare, allora ho scritto il semplice script di seguito > e vi consiglio di provarlo e confrontare i risultati. > > [...] > > start=time.clock() > > print 'Sort time:',time.clock()-start > > [...] > Scusa ma stampi la differenza tra due tempi... senza fare il sort? > 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. > > Il sort non puo` vincere su una array disordinato! Prova ad immagginare di avere 100 numeri in fila, a mente/mano faresti prima a trovare il massimo o a riordinarli? E` un esempio banale ma dovrebbe farti rendere conto della differenza che c'e` tra le due operazioni. Comunque si parlava di lunghezza quindi probabilmente erano stringhe. -- Andrea _______________________________________________ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
