<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv=Content-Type content="text/html; charset=iso-8859-1">
<meta name=Generator content="Microsoft Word 12 (filtered medium)">
<style>
<!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.MsoPlainText, li.MsoPlainText, div.MsoPlainText
{mso-style-priority:99;
mso-style-link:"Testo normale Carattere";
margin:0cm;
margin-bottom:.0001pt;
font-size:10.5pt;
font-family:Consolas;}
span.TestonormaleCarattere
{mso-style-name:"Testo normale Carattere";
mso-style-priority:99;
mso-style-link:"Testo normale";
font-family:Consolas;}
span.StileMessaggioDiPostaElettronica19
{mso-style-type:personal-compose;
font-family:"Calibri","sans-serif";
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page Section1
{size:612.0pt 792.0pt;
margin:70.85pt 2.0cm 2.0cm 2.0cm;}
div.Section1
{page:Section1;}
-->
</style>
<!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang=IT link=blue vlink=purple>
<div class=Section1>
<p class=MsoPlainText>>Ma il problema vero è che il sort ha costo più che
lineare, mentre il<o:p></o:p></p>
<p class=MsoNormal>>max ha costo lineare<o:p></o:p></p>
<p class=MsoNormal><o:p> </o:p></p>
<p class=MsoNormal>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?<o:p></o:p></p>
<p class=MsoNormal>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).<o:p></o:p></p>
<p class=MsoNormal>Ma ripeto potrei sbagliare, allora ho scritto il semplice
script di seguito e vi consiglio di provarlo e confrontare i risultati.<o:p></o:p></p>
<p class=MsoNormal><o:p> </o:p></p>
<p class=MsoNormal>#------------<o:p></o:p></p>
<p class=MsoNormal><span lang=EN-US>import time<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US>import random<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US><o:p> </o:p></span></p>
<p class=MsoNormal><span lang=EN-US>n=2000000<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US>lista=[]<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US>for i in range(n):<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US>
lista.append(random.randint(0,10000000))<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US><o:p> </o:p></span></p>
<p class=MsoNormal><span lang=EN-US>print 'Lista generata'<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US>start=time.clock()<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US>max(lista)<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US>print 'Max time:',time.clock()-start<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US><o:p> </o:p></span></p>
<p class=MsoNormal>start=time.clock()<o:p></o:p></p>
<p class=MsoNormal><span lang=EN-US>print 'Sort time:',time.clock()-start<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US>#-----------------<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US><o:p> </o:p></span></p>
<p class=MsoNormal>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.<o:p></o:p></p>
<p class=MsoNormal><o:p> </o:p></p>
<p class=MsoNormal>Giuseppe<o:p></o:p></p>
</div>
</body>
</html>