dopo una risposta non ricevuta dal professore, mi accingo a chiedere qui..
quale è la differenza tra il "selection sort" e il "bubble sort", essendo entrambi algoritmi di ricerca, entrambi basati sullo scambio fra loro di elementi presenti in un vettore??
aiutino sugli algoritmi..
Ven, 14/11/2008 - 22:53
Sab, 15/11/2008 - 01:31
#2
grazie 1000!
la tua risposta è davvero molto chiara...
solo una cosa: che significa "O(n^2)" ??
Sab, 15/11/2008 - 08:08
#3
Ciao
O sta per funzione asintotica e (n^2) sta per quadratica.
P.S. Comunque queste sono domande da fare a WikiPedia
http://it.wikipedia.org/wiki/Selection_sort
http://it.wikipedia.org/wiki/Bubble_sort
se no cosa si sbattono a fare (e magari cacciamogli un po' di grana).
Ciao Ciao, Moreno
Sab, 15/11/2008 - 12:58
#4
Quote:
Moreno ha scritto:
Ciao
O sta per funzione asintotica e (n^2) sta per quadratica.
Per essere piu' precisi la notazione O (o grande) sta ad indicare che la complessita' di tempo (o di spazio) di un algoritmo richiede alpiu' f(n) risorse di tempo di esecuzione (o di spazio di memoria):
g(n)=O(f(n)) <=> g(n)<=f(n) per ogni n
Poi c'e' la notazione o (o piccolo): come prima ma in questo caso e' una limitazione inferiore:
g(n)=O(f(n)) <=> g(n)>=f(n) per ogni n
Sab, 15/11/2008 - 14:08
#5
Quote:
wal7er ha scritto:
Per essere piu' precisi la notazione O (o grande) sta ad indicare che la complessita' di tempo (o di spazio) di un algoritmo richiede alpiu' f(n) risorse di tempo di esecuzione (o di spazio di memoria):
g(n)=O(f(n)) <=> g(n)<=f(n) per ogni n
Poi c'e' la notazione o (o piccolo): come prima ma in questo caso e' una limitazione inferiore:
g(n)=O(f(n)) <=> g(n)>=f(n) per ogni n
Per essere ancora piu` precisi, O(f(n)) denota un insieme di funzioni, non una sola. Quindi sarebbe da usare "g(n) appartiene a O(f(n))" (rimpiazzo "appartiene a" con il comando LaTeX \in). Solo che abusando della notazione, si usa g(n) = O(f(n)).
Anche la definizione di O, o, e Theta (c'e` anche la notazione Theta) non e` precisa.
A livello algoritmico, date due funzioni f,g dai naturali ai naturali, la definizione esatta di O e`: g(n) \in O(f(n)) se e solo se esistono C e N naturali tali che per ogni n > N, g(n) <= Cf(n).
La definizione per o e`: g(n) \in o(f(n)) se e solo se esistono C e N naturali tali che per ogni n > N, g(n) >= Cf(n).
Infine, la definizione di Theta e`: g(n) \in Theta(f(n)) se e solo se g(n) \in o(f(n)) e g(n) \in O(f(n)).
Ad esempio, dato un qualsiasi algoritmo di ordinamento per confronto, la sua complessita` e o(n log(n)).
L'heap-sort e merge-sort appartengono a Theta(n log(n)), quindi asintoticamente sono meglio di quicksort, la cui complessita` e` O(n^2), pur essendo piu` performante di mergesort nel caso medio.
Sab, 15/11/2008 - 18:48
#6
Va be', adesso ci mettiamo a fare una lezine sulla complessita' asintotica ... 
Era solo per dare una spiegazione "al volo", poi, se deve preparare l'esame di algoritmi, consultera' il libro di testo per i dettagli. :idea: :idea:
Sab, 15/11/2008 - 18:51
#7
esatto..
devo affrontare solo il primo esonero di Fondamenti di Informatica..non preparare un esame sugli algoritimi.
comunque la vostra preparazione è davvero impressionante!
bravi!
adesso apro un altro post su cui ho un'altra perplessità..
Sab, 15/11/2008 - 19:14
#8
E non siamo stati neanche precisi... :-P :-P
Entrambi lavorano per confronto, entrambi sono O(n^2).
L'unica differenza (a parte il nome) e` sul modo con cui spostano gli elementi: in bubbleSort scorri l'array non ancora ordinato da sinistra a destra confrontando ogni elemento con il precedente e invertendoli se fuori ordine. In selectionSort, al contrario, scorri da sinistra a destra e tieni traccia di qual e` l'elemento massimo nel sottoarray gia` visitato. Al termine della visita, scambi il massimo con l'ultimo elemento dell'array ancora da ordinare.
Alla fin fine, selectionSort ha delle costanti minori rispetto a bubbleSort, pur essendo entrambi quadratici, dato che fai al piu` n scambi (mentre bubbleSort ne fai al piu` n^2).
openSUSE 12.1 on Acer Aspire 1810tz - LXDE ultima versione dal repo x11:/lxde