Newsgroup: it.scienza.informatica
Titolo: analisi degli algoritmi di ordinamento

Salve a tutti.
Per poter sostenere un esame universitario devo produrre un elaborato
contenente l'analisi sperimentale della complessità di un algoritmo:
il mergesort. Sto cercando da alcuni giorni, in rete, indicazioni sui
test da effettuare per valutare algoritmi di ordinamento applicati a
diversi valori di n con n numero di chiavi da ordinare, ma non riesco
a trovarne. 
Se qualcuno avesse qualche indicazione da darmi...
Non mi interessano i dettagli sui test da effettuare, mi basterebbe
sapere quali sono così da poter cercare informazioni più agevolmente. 


Intendi caso peggiore, caso migliore, caso medio?
In ogni libro sugli algoritmi ci sono tutte le complessità degli algoritmi
più usati, e MergeSort è certamente tra questi. Probabilmente trovi anche
tutte le informazioni che ti servono.
Mi sembra che Mergesort sia con tempo quadratico, ma forse ricordo male.
--
Alessandro Monti




Si, per questo non ho problemi. Solo che devo effettuare anche
un'analisi sperimentale, ovvero realizzare un programma che effettui
dei test sul mergesort e ne valuti le prestazioni in base al numero di
chiavi da ordinare. Grazie comunque
					Giova

 Mi sembra che Mergesort sia con tempo quadratico, ma forse ricordo male.
Sono fresco fresco d'esami: io ho scritto che Mergesort ha complessita' n
log n
sia nel caso migliore che in quello peggiore.
Questo in teoria. In pratica e' piu' veloce Quicksort, anche se ha un caso
migliore di n log n
 e uno peggiore di n quadrato. La differenza la fa il caso medio!
ciao
Dangermouse

  e uno peggiore di n quadrato. La differenza la fa il caso medio!
Di solito si. Ricontrollerò, ma mi sembra strano che MergeSort abbia caso
peggiore n logn.
Sicuro di aver passato l'esame? :-)
--
Alessandro Monti

Prova a consultare il "Algoritmi e Strutture Dati" edito da McGraw Hill : ho
studiato le tematiche affrontate là sopra per un esa quattro anni fa, e mi
pare ci fossero le indicazioni che cerchi.
Lorentz

 chiavi da ordinare. Grazie comunque
Beh, di solito il caso migliore è quello con l'insieme già ordinato, e
quello peggiore con l'ordine inverso.
Per il caso medio, basta inizializzare a random un po' di volte e poi
mediare :-)
Ovviamente devi inserire nel codice dei contatori per verificare il numero
di confronti e il numero di scambi.
--
Alessandro Monti

a trovarne. 
Puoi provare in rete su questo sito:
http://hissa.ncsl.nist.gov/~black/CRCDict
Ma non vedo perche` non usare un libro di testo sugli algoritmi, ad
esempio l'Aho-Hopcroft-Ullman.
ciao
Stefano

 Sicuro di aver passato l'esame? :-)
Io l'esame l'ho passato, sono sicuro. ;-)
-- 
 Ciao, Luca.
 Reply to 
luca....@tiscalinet.it
 UIN : 43385135

peggiore n logn.
Mergesort e` O(nlog(n)) (log in base 2) e viene di solito
utilizzato per ordinare i dati contenuti in un grosso file
(sufficientemente grosso da non poter essere portato in memoria
tutto in una volta).
Paolo
-----------------------------------------------------------------
  Paolo Marotta
  Computer Science, University of Pisa
  home:   
http://www.cli.di.unipi.it/~marotta
-----------------------------------------------------------------

 Leiserson, Rivest).
Allora ricordo male, non voleva essere una provocazione. Io l'esame l'ho
passato tanto tempo fa, e non mi avevano chiesto il Merge-Sort :)
Comunque il log dovrebbe avere base 2 se spezzi il file in 2, 3 se lo spezzi
in 3, ecc, no?
--
Alessandro Monti

in 3, ecc, no?
Non sono un informatico, ma insomma. Non importa che base usi. Basta
che sia maggiore di 1. Vedi le definizioni di O(), theta(), ecc.
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
What's purple and commutes? An abelian grape.

 
Beh, mi sembra evidente, io ho citato quello indicato nel testo, ma e'
cmq adattarlo, e la complessita' cambia.


 
Beh, mi sembra evidente, io ho citato quello indicato nel testo, ma e'
cmq adattarlo, e la complessita' cambia."
Buon per te Luca che la cosa e' evidente....
Ma che e' uno scherzo? La complessita' e' definita a meno di fattori costanti
e fra il log in base 2 e quello in base qualunque esiste un rapporto costante!
Please rivedersi un po' di matematica elementare...
E poi che c'entra aver passato un esame? Se uno non ha capito un tubo puo'
aver preso anche 30 con lode e bacio sul culo ma non ha capito nulla lo 
stesso!!! 
Cheers
Yuri

 
Esatto, dato che il fattore di conversione fra una base di log e
un'altra e' una costante, che nei calcoli di O(*) non viene considerata.
LG
-- 
************************************************************************** 
Leandro Gelasi
V Year Computer Science Engineering at Siena University
email : 
gela...@lucy.ing.unisi.it
Gilles Villeneuve will live forever
**************************************************************************

 
Si, ok, in genere per indicare la complessita' non si specifica la base,
noi si parlava del caso particolare in cui si implementi il merge sort
dividendo per 2, o 3, ...


 e fra il log in base 2 e quello in base qualunque esiste un rapporto costante!
[...]
Chiedo venia per la str###ata che ho scritto, dev'essere colpa
dell'influenza :-~|


e fra il log in base 2 e quello in base qualunque esiste un rapporto costante!
Vero, ma specificare non significa certo essere meno precisi dato
oltretutto che la base 2 rappresenta il caso peggiore.
Tutto cio` e` cmq poco importante.


 Please rivedersi un po' di matematica elementare...
Sarà fatto.
--
Alessandro Monti


No. I risultati me li danno lunedi' prossimo :-(!
Comunque mergesort non me l'hanno chiesto :-)
Mi hanno chiesto heapsort!
ciao
Dangermouse