OliForum Matematico

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????

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????

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.

PS: toglimi una curiosità: che sei all'università di Salerno e devi fare l'esame di ASD con De Santis?

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?

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) $.

darklin 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?

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 facile

è 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..

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..

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...

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 :lol :

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?

darklin 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?

nono
solo proprietà e quelle 2 dimostrazioni e poi devi saper fare quell'esercizio che ti da i nodi e devi creare l'albero.

darklin 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 :lol :

ora sto scappando stasera quando torno ti passo msn

darklin 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 :lol :

ti ho mandato un mp con il contatto msn