Pages: [1] 2   Go Down
Print
Author Topic: Aggiunta di elemento in heap  (Read 3450 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
flashato90
Apprendista Forumista
**
Offline Offline

Posts: 122


WWW
« on: 26-09-2011, 21:31:14 »

Sia A un heap di lunghezza n. Supponiao che sia aggiunto un elemento nella posizione n+1. Qual è  la complessita del miglior algoritmo che verifica se tale array è ancora un heap?

Secondo me basta vedere se l'elemento aggiunto è minore (o maggiore) del padre(dipende che sia un minHeap o maxHeap)...quindi direi O(1).

Ma vedendo alcuni esercizi passati alcuni ritengano che la risp sia O(n)... perche?Huh??
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #1 on: 26-09-2011, 21:52:29 »

Mh.....sembrerebbe così.....le risposte quali potrebbero essere? O(n).....non credo proprio.
Logged

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

Posts: 57



« Reply #2 on: 26-09-2011, 22:10:14 »

Secondo me e' necessario solo il confronto col padre.
Chiede di verificare se sia ancora una heap, non fare in modo che lo rimanga.

Per me e' O(1)
Logged
flashato90
Apprendista Forumista
**
Offline Offline

Posts: 122


WWW
« Reply #3 on: 26-09-2011, 22:16:57 »

O(1)
O(log n)
O(log^2(n))
O(n)

E invece a questo quesito come risponderesti:

Sia R un albero RB . Supponiamo di voler trovare un nodo rosso(se esiste) ad altezza massima (NB: non puo essere la radice perchè è nera). Qual è la complessitò del miglior algoritmo possibile?

O(1)
O(log n)
O(n)
O(nlog n)

Secondo me è O(1) perchè dobbiamo guardare solamente ad altezza massima che sarebbe il livello sotto la radice...se non si trova li vuol dire che non esiste perchè gli altri livelli non saranno ad altezza massima.
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #4 on: 26-09-2011, 22:23:12 »

Alla prima risponderei O(1). Per la seconda dici costante, perchè?

Quote
perchè dobbiamo guardare solamente ad altezza massima che sarebbe il livello sotto la radice

No....l' altezza massima si trova scendendo più giù....più vai sotto più aumenta l' altezza.

P.S C' è questo applet interessante sugli alberi RB.

http://www.ece.uc.edu/~franco/C321/html/RedBlack/redblack.html
« Last Edit: 26-09-2011, 22:24:53 by Daréios89 » 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: 26-09-2011, 22:37:40 »

Scusa ma semmai piu scendo e più aumenta la profondità... e l'altezza diminuisce... non è così?
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #6 on: 26-09-2011, 22:48:56 »

Per quanto riguarda l'altezza h di un albero binario è data dalla massima profondità raggiunta dalle sue foglie. Quindi, l'altezza misura la massima distanza di una foglia dalla radice dell'albero.


            O
         /      \
      O         O
    /   \      /   \
  O     O  O     O

Qual è l' altezza di questo albero?
« Last Edit: 26-09-2011, 22:54:22 by Daréios89 » Logged

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

Posts: 57



« Reply #7 on: 26-09-2011, 23:21:47 »

Il fatto che dobbiamo TROVARE un nodo SE ESISTE implica che dobbiamo controllare tutti gli elementi.
Se quel nodo non esiste siamo costretti a visitare tutti i nodi.
Io direi O(n).
« Last Edit: 26-09-2011, 23:24:03 by Misa » Logged
flashato90
Apprendista Forumista
**
Offline Offline

Posts: 122


WWW
« Reply #8 on: 26-09-2011, 23:34:32 »

effettivamente si... io avevo interpretato il testo diversamente...
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #9 on: 27-09-2011, 09:50:01 »

Il fatto che dobbiamo TROVARE un nodo SE ESISTE implica che dobbiamo controllare tutti gli elementi.
Se quel nodo non esiste siamo costretti a visitare tutti i nodi.
Io direi O(n).


Se dovessimo visitare tutti i nodi dell' albero, in teoria partiamo dalla radice e seguiamo tutti i percorsi che vanno dalla radice alle foglie, quindi...in teoria io avrei una procedura che costa \theta(\log(n)) (percorso fino ad una foglia) che si ripete n volte, quindi secondo me al massimo sarebbe \theta(n\log(n)).
Comunque da quell' applet che ho linkato, mi è sembrato di vedere che quando è presente un nodo rosso ad altezza massima, lo si trova nel primo percorso più lungo dalla radice alle foglie, quindi mi verrebbe da dire la risposta b). Provate anche voi l' applet...
Logged

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

Posts: 57



« Reply #10 on: 27-09-2011, 10:48:22 »

Se dovessimo visitare tutti i nodi dell' albero, in teoria partiamo dalla radice e seguiamo tutti i percorsi che vanno dalla radice alle foglie, quindi...in teoria io avrei una procedura che costa \theta(\log(n)) (percorso fino ad una foglia) che si ripete n volte, quindi secondo me al massimo sarebbe \theta(n\log(n)).

Non sono d'accordo. Una semplice visita INORDER di un albero binario costerebbe \theta(n). Basterebbe un "contatore di profondita'" e un controllo del colore, cosi' potremmo ritornare il nodo rosso con profondita' massima.
« Last Edit: 27-09-2011, 10:50:03 by Misa » Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #11 on: 27-09-2011, 12:06:42 »

Già hai ragione la visita inorder ha quel costo, e considerando che non è detto che io mi ritrovi subito a percorre il percorso più lungo dalla radice alle foglie, mi sa che hai ragione tu, \theta(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 #12 on: 27-09-2011, 12:47:52 »

E se invece volessimo verificare che un array sia un heap? Qual' è la complessità del miglio algoritmo?
O(1)
O(log n)
O(n)
O(nlog n)

...Huh? O(n) Huh?
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #13 on: 27-09-2011, 13:56:50 »

E se invece volessimo verificare che un array sia un heap? Qual' è la complessità del miglio algoritmo?
O(1)
O(log n)
O(n)
O(nlog n)

...Huh? O(n) Huh?

Bè tu come lo verificheresti? Con qualche procedura suppongo.....
Logged

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

Posts: 57



« Reply #14 on: 27-09-2011, 15:02:45 »

E se invece volessimo verificare che un array sia un heap? Qual' è la complessità del miglio algoritmo?
O(1)
O(log n)
O(n)
O(nlog n)

...Huh? O(n) Huh?

Io farei cosi':
Per ogni nodo interno k (quindi per un numero totale di nodi pari a floor(n/2)) verificherei che A[k] >= max(A[2k],A[2k+1])

Direi O(n)
« Last Edit: 27-09-2011, 15:04:20 by Misa » Logged
Pages: [1] 2   Go Up
Print
Jump to: