Dopo aver visto come funziona la ricorsione in Scheme dobbiamo valutare un altro aspetto molto rilevante: il costo. Non tutto ciò che logicamente funziona funziona poi all’atto pratico. Ad esempio, se ripescate la funzione ricorsiva della Funzione di Fibonacci e provate a farla partire noterete che già con numeri relativamente bassi (come 100) il …
Posts Tagged ‘complessità’
Posted in 
Tags: 
Algoritmica – Ordinamento – Bubble Sort
December 10th, 2008 
THeK3nger 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 domestica, ma avremo molte difficoltà nell’ordinare in ordine di età gli abitanti di Roma …
Algoritmica – Ordinamento – Selection Sort
December 8th, 2008 THeK3nger 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 nostra ricerca dell’algoritmo ottimo di sorting oggi guarderemo il Selection Sort.
for i = 0 to …
Algoritmica – Ordinamento – Insertion Sort
December 4th, 2008 THeK3nger 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 più semplici: insertion sort.Insertion Sort :
def insertion_sort(x, n) :
for i = 1 …
