Ho preparato un PDF con la dimostrazione del lower bound per algoritmi di ordinamento. Può contenere ancora qualche svista ma dovrebbe essere piuttosto corretto e fornire, a chi vuole, una dimostrazione semplificata del perché non può esistere un algoritmo di … Continue reading
Insertion Sort e Selection Sort non si sono rivelati all’altezza delle nostre aspettative e noi ci ritroviamo ancora senza un algoritmo efficente per ordinare, o meglio: sappiamo ordinare le tracce di un album, oppure i CD di un apiccola collezione … Continue reading
Nell’ultimo appuntamento abbiamo visto e analizzato gli aspetti generali dell’Insertion Sort e notato che esso non è affatto un algoritmo usabile in pratica per istanze (ovvero input) molto grandi. Ovviamente l’Insertion Sort non è l’unico algoritmo di sorting esistente. Nella … Continue reading
Volevo discutere in qualche articolo alcuni problemi di algoritmica presentando alcuni algoritmi che li risolvono e analizzandone la complessità. Cominciamo questa vetrina di algoritmi con quelli che risolvono il più classico dei problemi: l’ordinamento. In particolare cominceremo vedendo uno dei … Continue reading
Follow