Mostrare che non esiste alcun algoritmo di ordinamento per confronti il cui tempo di
esecuzione è lineare (cioè O(n)) per almeno metà degli n! input di lunghezza n.
Qualcuno di voi sa dirmi qualcosa????
sort lineare in metà dei casi
Re: Problema!!!!
Questo se non sbaglio si dimostra per lower baund. In pratica per ordinare n elementi con un algoritmo per confronti occorrono un limite inferiore di Ω(n log n) confronti.darklin ha scritto:Mostrare che non esiste alcun algoritmo di ordinamento per confronti il cui tempo di
esecuzione è lineare (cioè O(n)) per almeno metà degli n! input di lunghezza n.
Qualcuno di voi sa dirmi qualcosa????
PS: toglimi una curiosità: che sei all'università di Salerno e devi fare l'esame di ASD con De Santis?
dim
Il lower-bound si ricava costruendo
un albero binario delle decisioni, e'
un problema abbastanza standard.
Sia $ S= (x_1, x_2, ..., x_n) $ la sequenza
da ordinare, l'albero binario $ T $ ha come radice
il confronto $ x_1 \leq x_2 $,
e per figli i vari sottocasi dei possibili confronti.
Le foglie dell'albero (i.e. i nodi senza figli),
sono le possibili permutazioni di $ S $.
Ora, vogliamo stimare il numero di confronti
necessari (i.e. l'altezza $ h $ dell'albero)
per decidere l'ordine della sequenza
Vi sono $ n! $ possibili permutazioni di $ S $,
dunque $ T $ ha $ n! $ foglie.
Ricordando che $ T $ ha altezza $ h $,
dovra' essere $ n! \leq 2^h $.
Per Stirling $ n! = (\frac{n}{e})^n\sqrt{2\pi n}(1+O(\frac{1}{n})) $,
essendo il logaritmo monotono crescente
segue $ h\geq n log(n) $.
un albero binario delle decisioni, e'
un problema abbastanza standard.
Sia $ S= (x_1, x_2, ..., x_n) $ la sequenza
da ordinare, l'albero binario $ T $ ha come radice
il confronto $ x_1 \leq x_2 $,
e per figli i vari sottocasi dei possibili confronti.
Le foglie dell'albero (i.e. i nodi senza figli),
sono le possibili permutazioni di $ S $.
Ora, vogliamo stimare il numero di confronti
necessari (i.e. l'altezza $ h $ dell'albero)
per decidere l'ordine della sequenza
Vi sono $ n! $ possibili permutazioni di $ S $,
dunque $ T $ ha $ n! $ foglie.
Ricordando che $ T $ ha altezza $ h $,
dovra' essere $ n! \leq 2^h $.
Per Stirling $ n! = (\frac{n}{e})^n\sqrt{2\pi n}(1+O(\frac{1}{n})) $,
essendo il logaritmo monotono crescente
segue $ h\geq n log(n) $.
eheh abbiamo gli stessi dubbi... devo fare anche io l'esame questo 19 con De Santis... quest'anno il prof si è messo male in testa, speriamo in una prova faciledarklin ha scritto:si!!!!!!!!!!marò cn quella np completezza mi sta facendo uscire pazzo..quindi per questa basta che dimostro che per un problema del genere ci vuole ..nlogn..
anke tu devi fare l'esame cn de sanctis?
gli alberi rosso-neri me li sto vedendo oggi, comunque se ho capito bene la domanda dovresti trovare la risposta nel lemma 2 dell'unico pacco di slide che il prof ha messo a disposizione in tutto il corso. Le slide le trovi sul suo rozzo sito...darklin ha scritto:è si..anke io il 19 vado..allor ci vediamo quel giorno..cmq alberi rosso neri cm stai messo?ho fatto una domanda ma nessuno mi ha risp..qual'è il maggior e minor numero di nodi intern di un albero di altezza h?domanda di apppello
cmq grazie per la risp..
nonodarklin ha scritto:ma li impari gli algoritmi di inserimento e cancellazione ,rotazione..di alberi rosso neri..negli appelli nn sn mai usciti se ho visto bene..al massimo tempo di esecuzione e proprietà di alberi o dimost di altezza nera..2log(n+1)....ste cose qua..
che dici?
solo proprietà e quelle 2 dimostrazioni e poi devi saper fare quell'esercizio che ti da i nodi e devi creare l'albero.
ora sto scappando stasera quando torno ti passo msndarklin ha scritto:si ho capit che un sottoalbero contiene al massimo 2bh(x)-1 nodi interni..il problema è che nell'appello lui ha chiesto numero massimo e minimo di nodi..cmq se hai msn possiamo aggiungerci così magari qualcosa che sai tu e qualcosa che so io facciamo l'appello
ti ho mandato un mp con il contatto msndarklin ha scritto:si ho capit che un sottoalbero contiene al massimo 2bh(x)-1 nodi interni..il problema è che nell'appello lui ha chiesto numero massimo e minimo di nodi..cmq se hai msn possiamo aggiungerci così magari qualcosa che sai tu e qualcosa che so io facciamo l'appello