OliForum Matematico

Ciao gente, ho un altro piccolo quesito da proporvi

Si consideri un insieme S di n >= 2 distinti numeri interi.
•Si descriva ed analizzi un algoritmo che dato in input S, determini x,y appartenenti ad S tali che |x – y| >= |w – z| per tutti w, z appartenenti ad S. L’algoritmo deve avere una ...

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

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

nono :lol:
solo proprietà e quelle 2 ...

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

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

Penso che lo si possa fare in 3 passi: trovi il k-esimo più grande in tempo lineare con algoritmi classici, poi trovi i k più grandi in tempo lineare, semplicemente confrontandoli con il k-esimo, infine ordini questi elementi in O(k log k). In totale si richiede O(n + k log k) tempo.

Si stavo ...

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

Ciao a tutti raga, è il mio primo post per me, che sono una mezza cazetta, in questo forum di geni.
Mi piace troppo questo forum sto trovando le soluzioni per un sacco di esercizi di ASD che non sapevo fare ^^

Mi restano però alcuni dubbi su di un esercizio, eccolo:

Data una sequenza di n numeri ...