sugli ordinamenti...

[manub]

Ne approfitto anche io per intavolare una discussione, spero interessante... magari non troppo, in quanto credo sia oggetto di studio di numerosi corsi di Informatica. Però, discuterne e confrontarsi fa sempre bene!

data una generica sequenza di n numeri $ a_1, a_2, ..., a_n $, dimostrare che in media il numero di confronti necessari ad ordinare tale sequenza in ordine crescente è $ \displaystyle\Omega(nlog_2n) $.

[gip]

Ne approfitto anche io per intavolare una discussione, spero interessante... magari non troppo, in quanto credo sia oggetto di studio di numerosi corsi di Informatica. Però, discuterne e confrontarsi fa sempre bene!

data una generica sequenza di n numeri $ a_1, a_2, ..., a_n $, dimostrare che in media il numero di confronti necessari ad ordinare tale sequenza in ordine crescente è $ \displaystyle\Omega(nlog_2n) $.

Più che "in media", si può dimostrare che è il lower bound...

[manub]

Ne approfitto anche io per intavolare una discussione, spero interessante... magari non troppo, in quanto credo sia oggetto di studio di numerosi corsi di Informatica. Però, discuterne e confrontarsi fa sempre bene!

data una generica sequenza di n numeri $ a_1, a_2, ..., a_n $, dimostrare che in media il numero di confronti necessari ad ordinare tale sequenza in ordine crescente è $ \displaystyle\Omega(nlog_2n) $.

Più che "in media", si può dimostrare che è il lower bound...

Nella notazione asintotica, l'omega indica appunto un limite inferiore. Forse non sono stato preciso io... sappiamo tutti che, ad esempio, un algoritmo come Insertion Sort ha un best case che è $ O(n) $. La mia richiesta era di dimostrare che qualsiasi algoritmo di ordinamento riesce ad ordinare un'arbitraria sequenza di cardinalità n in un tempo che, nel caso medio, è $ \Omega(nlog_2n) $. Spero di esser stato più chiaro ! Per semplicità, possiamo comunque assumere elementi tutti distinti...

[Pyv]

Giusto per la cronaca un insieme di INTERI si puo' ordinare in O(n lg lg n)

[MindFlyer]

Sembrava anche a me che ci fosse un tempo migliore di O(n log n)!
Comunque, trattandosi di un insieme finito di numeri, che siano interi o no non importa (infatti si possono ridurre ad interi in tempo lineare).

[gip]

Manub aveva parlato di confronti, quindi io parlavo di "comparison sorting"...

Se invece dobbiamo proprio fare gli sboroni: http://citeseer.ist.psu.edu/cache/paper ... g-in-o.pdf

[manub]

interi, numeri che entrano in una word... stiamo passando dal generico a delle particolari sequenze! anche se non sapevo che degli interi si potessero ordinare in n log log n...

comunque, la mia domanda resta la stessa... nessuno si cimenta con questi benedetti alberi di decisione?

[gip]

Allora, l'ora e' propizia per cimentarvicisi.

Partiamo dalla simpatica dimostrazione del fatto che $ O(n\log_2(n)) $ è il lower bound per gli algoritmi di sorting tramite confronto: se bisogna ordinare n elementi, l'albero di decisione ha $ n! $ (pari alle permutazioni degli stessi) foglie, e un albero con $ n! $ foglie ha profondità (corrispondente al tempo del worst case) pari ad almeno $ \log_2(n!) $; per n grandi si ha che $ n! \simeq (\frac{n}{e})^n $, quindi $ \log_2(n!) \simeq \log_2((\frac{n}{e})^n) = n\log_2(n) - e\log_2(n) $ che asintoticamente corrisponde a $ n\log(n) $.

Ciò premesso, abbiamo invece che il tempo dell'average case è dato dalla media delle profondità delle foglie del nostro albero; ci basta dimostrare che anche tale profondità media è $ \geq \log_2(n!) $. Dimostriamo quindi (per induzione sulla profondità) che in generale in un albero binario con f foglie la profondità media $ p $ delle foglie è almeno $ \log_2(f) $. Caso base: l'albero binario elementare di profondità 1 e con 1 foglia ha $ p = 1 \geq \log_2(n) $ e lo stesso vale per l'albero binario elementare di profondità 1 e con 2 foglie. Passo induttivo: partendo da alberi di prondità n (per i quali valga la tesi), ci sono due modi per costruire alberi di profondità n+1; il primo consiste semplicemente nell'aggiungere in cima un nodo, da cui discenda un solo albero di profondità n; così facendo si ha che il numero di foglie rimane invariato, mentre la profondità di ogni foglia aumenta di 1, per cui la profondità media non può che aumentare ed essere quindi ancora $ \geq \log_2(n!) $; il secondo caso consiste nell'aggiungere in cima un nodo, da cui discendano due differenti alberi di cui uno di profondità n e uno di profondità $ \leq n $; in questo caso, detti $ f_1 $ e $ f_2 $ i numeri di foglie del primo e del secondo albero, e dette $ p_1 $ e $ p_2 $ le profondità medie del primo e del secondo albero, si ha che la profondità media dell'albero complessivo è $ \frac {f_1\cdot p_1 + f_2\cdot p_2}{f_1+f_2} + 1 \geq \frac {f_1\cdot \log_2(f_1) + f_2\cdot \log_2(f_2)}{f_1+f_2} + 1 $$ = \frac {f_1\cdot \log_2(f_1) + f_2\cdot \log_2(f_2) + f_1 + f_2}{f_1+f_2} $$ = \frac {f_1\cdot \log_2(2 \cdot f_1) + f_2\cdot \log_2(2 \cdot f_2)}{f_1+f_2} $; l'ultima espressione ricavata, per $ f_1+f_2 $ costante, ha minimo quando $ f_1=f_2=f_f $ (per dimostrarlo basta sostituire le variabili con le nuove variabili $ \frac{f_1+f_2}{2} $ e $ \frac{f_1-f_2}{2} $ e poi annullare la derivata parziale rispetto a $ \frac{f_1-f_2}{2} $), ma in questo caso $ \frac {f_1\cdot \log_2(2 \cdot f_1) + f_2\cdot \log_2(2 \cdot f_2)}{f_1+f_2} = $$ \frac {f_f\cdot \log_2(2 \cdot f_f) + f_f\cdot \log_2(2 \cdot f_f)}{f_f+f_f} = \log(2 \cdot f_f) = $$ \log(f_1+f_2) $, mentre in tutti gli altri casi è $ \frac {f_1\cdot \log_2(2 \cdot f_1) + f_2\cdot \log_2(2 \cdot f_2)}{f_1+f_2} > \log(f_1+f_2) $; si ha quindi in definitiva che la profondità media dell'albero complessivo è $ \geq \log(f_1+f_2) $, ossia è ancora una volta maggiore del logaritmo del numero complessivo delle foglie. Questo termina la dimostrazione.

Ciao!

[manub]

sei sicuro che l'albero come l'hai costruito tu nel caso induttivo sia ancora un albero di decisione? ci sono dei vincoli forti, sugli alberi di decisione per l'ordinamento... non credo che tu possa trattarli come alberi binari qualunque! la mia idea era un'altra, comunque aspetto che qualcun altro anche legga il tuo lavoro e dica cosa ne pensa io per dimostrarlo avrei cercato di calcolare la lunghezza media del cammino tra la radice ed un nodo... e avrei fatto vedere che, minimizzando questa lunghezza (ovvero scegliendo l'albero di decisione fatto in modo tale che questa lunghezza media sia minima), essa resta comunque asintoticamente sopra nlogn.

[gip]

sei sicuro che l'albero come l'hai costruito tu nel caso induttivo sia ancora un albero di decisione?

Di sicuro è vero il viceversa, cioè che un albero di decisione è un albero binario, quindi ho trattato il caso più generale...

[manub]

sei sicuro che l'albero come l'hai costruito tu nel caso induttivo sia ancora un albero di decisione?

Di sicuro è vero il viceversa, cioè che un albero di decisione è un albero binario, quindi ho trattato il caso più generale...

Beh sì, un albero di decisione è binario, quindi quello che hai detto tu è giusto. Però nutro ancora dei dubbi sul caso medio... definire un caso medio prevede definire una probabilità, non trovi? La mia idea era quella di dimostrare che la lunghezza media del percorso in un albero di decisione (tale che esso abbia la minore profondità possibile) è sempre superiore a nlogn. Se definisci come Pe il percorso esterno dell'albero, puoi dire che la lunghezza media di un cammino dell'albero, assumendo che i cammini siano tutti equiprobabili, sia Pe/n! - a questo punto si ragiona vedendo qual è l'albero che minimizza questa quantità (n! è costante, quindi cambia semplicemente Pe) e ci si ragiona su. Un albero che minimizza Pe, fissata un altezza g, è un albero completo. Sfruttando la definizione di albero completo si calcola il numero di foglie ad altezza h e quelle ad altezza h-1. Dato che Pe = h * N_h + (h-1)N_h-1 (dove N_h denota il numero di foglie ad altezza h), sostituendo i valori calcolati per N_h e N_h-1 nella formula Pe/n! si ottiene un limite inferiore per l'altezza media.

[Chrysalis]

Ciao a tutti... conoscevo anch'io più o meno il teorema per cui un algoritmo di ordinamento per confronto non può avere prestazioni temporali mogliori di
n(log(n)), quello che avete appena dimostrato. Ma ciò di cui parla Pyv, ovvero che si può ordinare unn insieme in un tempo n (log log n)?? Che algoritmo è??
Grazie mille

[CUCU]

Ne approfitto anche io per intavolare una discussione, spero interessante... magari non troppo, in quanto credo sia oggetto di studio di numerosi corsi di Informatica. Però, discuterne e confrontarsi fa sempre bene!

data una generica sequenza di n numeri $ a_1, a_2, ..., a_n $, dimostrare che in media il numero di confronti necessari ad ordinare tale sequenza in ordine crescente è $ \displaystyle\Omega(nlog_2n) $.

intendi nel caso peggiore, ed inoltre devi specificare che è il caso degli ordinamenti per CONFRONTI, perchè per esempio è possibile ordinare interi di lunghezza fissa in tempo O(n) nel caso peggiore.

Dimostriamo pertanto che per ogni algoritmo di ordinamento per confronti esiste una sequenza che viene ordinata in tempo Omega(nlogn).

Dimostrazione
Consideriamo l'albero di decisione di un generico algoritmo.
Dimostreremo il teorema provando che ogni albero di decisione che ordina n elementi (non necessariamente interi) ha altezza Omega(nlogn).

L'albero deve avere almeno n! (fattoriale di n) foglie perchè ci sono n! permutazioni di n elementi.
Un albero binario (gli alberi di decisione sono binari perchè per ipotesi del teorema l'algoritmo ordina per CONFRONTI) di altezza k ha un numero di foglie <= 2^k.

Allora si ha:
2^k >= n!
(passando ai logaritmi binari)
k >= log(n!)
(dal fatto che log(n!)= sumlogi )
k>= sumlogi
(dal fatto che log i è monotona crescente)
k>= sumlogi >= Integrale [da 0 ad n] logxdx = nlog(n)-n=nlog(n/2).
Ora nlog(n/2)>=(nlogn)/2 per n>=4.
Dalla definizione di Omega (ricordiamo che nella definizione di Omega(g(n)) la costante che moltiplica g(n) può essere un reale a differenza della notazione Big-Oh) segue quindi che nlog(n/2) appartiene ad Omega(nlogn).

Abbiamo così mostrato che l'altezza dell'albero è >= di una funzione che appartiene ad Omega(nlogn).
Ciò conclude la dimostrazione.

[CUCU]

Allora, l'ora e' propizia per cimentarvicisi.

Partiamo dalla simpatica dimostrazione del fatto che $ O(n\log_2(n)) $ è il lower bound per gli algoritmi di sorting tramite confronto: se bisogna ordinare n elementi, l'albero di decisione ha $ n! $ (pari alle permutazioni degli stessi) foglie, e un albero con $ n! $ foglie ha profondità (corrispondente al tempo del worst case) pari ad almeno $ \log_2(n!) $; per n grandi si ha che $ n! \simeq (\frac{n}{e})^n $, quindi $ \log_2(n!) \simeq \log_2((\frac{n}{e})^n) = n\log_2(n) - e\log_2(n) $ che asintoticamente corrisponde a $ n\log(n) $.

Ciò premesso, abbiamo invece che il tempo dell'average case è dato dalla media delle profondità delle foglie del nostro albero; ci basta dimostrare che anche tale profondità media è $ \geq \log_2(n!) $. Dimostriamo quindi (per induzione sulla profondità) che in generale in un albero binario con f foglie la profondità media $ p $ delle foglie è almeno $ \log_2(f) $. Caso base: l'albero binario elementare di profondità 1 e con 1 foglia ha $ p = 1 \geq \log_2(n) $ e lo stesso vale per l'albero binario elementare di profondità 1 e con 2 foglie. Passo induttivo: partendo da alberi di prondità n (per i quali valga la tesi), ci sono due modi per costruire alberi di profondità n+1; il primo consiste semplicemente nell'aggiungere in cima un nodo, da cui discenda un solo albero di profondità n; così facendo si ha che il numero di foglie rimane invariato, mentre la profondità di ogni foglia aumenta di 1, per cui la profondità media non può che aumentare ed essere quindi ancora $ \geq \log_2(n!) $; il secondo caso consiste nell'aggiungere in cima un nodo, da cui discendano due differenti alberi di cui uno di profondità n e uno di profondità $ \leq n $; in questo caso, detti $ f_1 $ e $ f_2 $ i numeri di foglie del primo e del secondo albero, e dette $ p_1 $ e $ p_2 $ le profondità medie del primo e del secondo albero, si ha che la profondità media dell'albero complessivo è $ \frac {f_1\cdot p_1 + f_2\cdot p_2}{f_1+f_2} + 1 \geq \frac {f_1\cdot \log_2(f_1) + f_2\cdot \log_2(f_2)}{f_1+f_2} + 1 $$ = \frac {f_1\cdot \log_2(f_1) + f_2\cdot \log_2(f_2) + f_1 + f_2}{f_1+f_2} $$ = \frac {f_1\cdot \log_2(2 \cdot f_1) + f_2\cdot \log_2(2 \cdot f_2)}{f_1+f_2} $; l'ultima espressione ricavata, per $ f_1+f_2 $ costante, ha minimo quando $ f_1=f_2=f_f $ (per dimostrarlo basta sostituire le variabili con le nuove variabili $ \frac{f_1+f_2}{2} $ e $ \frac{f_1-f_2}{2} $ e poi annullare la derivata parziale rispetto a $ \frac{f_1-f_2}{2} $), ma in questo caso $ \frac {f_1\cdot \log_2(2 \cdot f_1) + f_2\cdot \log_2(2 \cdot f_2)}{f_1+f_2} = $$ \frac {f_f\cdot \log_2(2 \cdot f_f) + f_f\cdot \log_2(2 \cdot f_f)}{f_f+f_f} = \log(2 \cdot f_f) = $$ \log(f_1+f_2) $, mentre in tutti gli altri casi è $ \frac {f_1\cdot \log_2(2 \cdot f_1) + f_2\cdot \log_2(2 \cdot f_2)}{f_1+f_2} > \log(f_1+f_2) $; si ha quindi in definitiva che la profondità media dell'albero complessivo è $ \geq \log(f_1+f_2) $, ossia è ancora una volta maggiore del logaritmo del numero complessivo delle foglie. Questo termina la dimostrazione.

Ciao!

ah, allora qui si parla davvero di lower bound sul tempo MEDIO.
avevo dato per scontato che si intendesse il caso peggiore.
Però come ha già detto un altro utente, questa non è una dimostrazione corretta perchè siamo nell'ipotesti che l'albero sia di decisione, e quindi, per esempio, non ci sono nodi con un solo figlio.

[CUCU]

uffa
avevo scritto 3 pagine di dimostrazione (che però non era completa) clicco su anteprima, e trovo la pagina vuota!
mi secca riscrivere tutto.
ma accenno alla dimostrazione.
Basta dimostrare che ogni albero binario, con la proprietà che ogni nodo non terminale ha due figli, ha altezza media >=logf, dove f è il numero di foglie. Infatti , dal momento che f>=n! segue che l'altezza media è una funzione in Omega(nlogn).

Lo si dimostra per induzione sul numero di foglie.
Al passo induttivo si nota che H(T)=H(T1)f1+H(T2)f2+1, (dove con H(A) intedo l'altezza media di un albero A e con T1 e T2 i sottoalberi di T con rispettivamente f1 ed f2 foglie con f=f1+f2) e applicando l'ipotesi induttiva si ha
H(T)>=f1logf1+f2logf2.
Si può supporre che f1=f/2+k e f2=f/2-k per qualche k (ma si dovrebbe modificare la dimostrazione per contemplare il caso che n sia dispari).
Con questa riscrittura si vede che la funzione H(T) ha minimo quando k=0 nel cui caso H(T)>=logf.


Spero che qualcuno verifichi e formalizzi il tutto.