Pages: [1]   Go Down
Print
Author Topic: Alcune domande  (Read 1657 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
flashato90
Apprendista Forumista
**
Offline Offline

Posts: 122


WWW
« on: 27-09-2011, 19:31:48 »

1):Sia T un albero binario di ricerca, con la struttura topologica di un heap. Qual'è la complessità per trasformare T in un ALBERO RB?

2): Complessità per fondere k liste ordinate utilizzando le proprietà dell'heap?
Secondo me O(n).(Non è sempre n il merge tra due insiemi ordinati?)

3):Radix sort si può utilizzare per dimostrare che n^2 - 1 elementi possono essere ordinati in...?
Secondo me in O(n).

4): qual'è la profondità minima di una foglia in un albero decisionale?
Io credo n-1 , nonchè il "cammino" che indica la sequenza già ordinata.

5): Se volessimo effettuare le visite BFS o DFS in un grafo dato con MATRICE DI ADIACENZA ... Qual'è la complessità di tale algoritmo?
Io direi che minimo dobbiamo girare tutta la matrice quindi O(n^2)... ma ciò è sufficiente?

Che cosa avreste risposto?
Logged
Misa
Matricola
*
Offline Offline

Posts: 57



« Reply #1 on: 27-09-2011, 19:40:47 »

1):Sia T un albero binario di ricerca, con la struttura topologica di un heap. Qual'è la complessità per trasformare T in un ALBERO RB?

2): Complessità per fondere k liste ordinate utilizzando le proprietà dell'heap?
Secondo me O(n).(Non è sempre n il merge tra due insiemi ordinati?)

3):Radix sort si può utilizzare per dimostrare che n^2 - 1 elementi possono essere ordinati in...?
Secondo me in O(n).

4): qual'è la profondità minima di una foglia in un albero decisionale?
Io credo n-1 , nonchè il "cammino" che indica la sequenza già ordinata.

5): Se volessimo effettuare le visite BFS o DFS in un grafo dato con MATRICE DI ADIACENZA ... Qual'è la complessità di tale algoritmo?
Io direi che minimo dobbiamo girare tutta la matrice quindi O(n^2)... ma ciò è sufficiente?

Che cosa avreste risposto?
Mia versione:

1) O(n). Essendo l'albero bilanciato, basta aggiungere il campo colore.

2) Se non abbiamo altri dati, direi O(n). Se fossero state liste di ugual dimensione si sarebbe potuto fare in O(klogk)

3) Non ci sono altri dati nella domanda?

4) log(n!) . L'albero ha n! foglie, quindi deve avere altezza almeno pari a log(n!)

5) O(n^2)
« Last Edit: 27-09-2011, 19:52:00 by Misa » Logged
flashato90
Apprendista Forumista
**
Offline Offline

Posts: 122


WWW
« Reply #2 on: 27-09-2011, 19:55:37 »

riguardo la 2 non ci sono altri dati!

non concordo sulla 4!! Non credo sia vero che se un albero ha n! foglie allora debba avere altezza log(n!)...!!!
Logged
Misa
Matricola
*
Offline Offline

Posts: 57



« Reply #3 on: 27-09-2011, 20:06:12 »

Guarda il capitolo 9.1 del cormen. Ordinamento in tempo lineare.

Hai le risposte possibili per la 2 e la 3?
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #4 on: 27-09-2011, 20:37:20 »

Quote
qual'è la profondità minima di una foglia in un albero decisionale?

Potrebbe essere \log(n)?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
flashato90
Apprendista Forumista
**
Offline Offline

Posts: 122


WWW
« Reply #5 on: 27-09-2011, 20:45:28 »

ma perchè nlog n ... considera ad esempio la sequenza a1 a2 a3 cioè l'esempio delle slide... se osservi la foglia a profondità minima si trova a n-1 ... se gli elementi fossero di piu credo sia la stessa cosa...


le risposte non le ho!
Logged
mafalda
Apprendista Forumista
**
Offline Offline

Posts: 430


CЯΣDΣЯCI SΣMPЯΣ, ΛЯЯΣПDΣЯSI MΛI!


« Reply #6 on: 30-09-2011, 10:37:16 »

Qualcuno gentilmente mi posta lo svolgimento di questa ricorrenza
T(n)=T(\frac{n}{2})+ T(\frac{n}{3})+ T(\frac{n}{6}) + n
grazie.
Logged

...๔єςเ, ๔єςเ, ๔єςเ...
Vincent
Matricola
*
Offline Offline

Posts: 75


« Reply #7 on: 30-09-2011, 10:52:13 »

questa ricorrenza è molto banale poichè se sommi i costi di n/3 e n/6 ottieni n/2 ovvero la ricorrenza si potrebbe anche scrivere come T(n) = 2T(n/2)+n ovvero la ricorrenza del merge che ha costo nlogn Wink
Logged
mafalda
Apprendista Forumista
**
Offline Offline

Posts: 430


CЯΣDΣЯCI SΣMPЯΣ, ΛЯЯΣПDΣЯSI MΛI!


« Reply #8 on: 30-09-2011, 10:56:07 »

Ok..Grazie mille 
Logged

...๔єςเ, ๔єςเ, ๔єςเ...
Pages: [1]   Go Up
Print
Jump to: