Pages: [1]   Go Down
Print
Author Topic: Quesiti su heap e induzione  (Read 422 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« on: 31-08-2011, 21:50:35 »

In una domanda mi si chiede, data una heap A di n interi dobbiamo verificare se inserendo in posizione n+1 l' elemento x, la struttura è una minheap, qual è la migliore complessità?

a)O(1)
b)O(logn)
c)O(log^2n)
d)O(n)

Come fare a rispondere? Nel senso, la struttura è già una minheap? In questo caso basterebbe controllare solo la relazione tra l' ultimo nodo e il padre, se è una minheap minheapify si dovrebbe arrestare subito e quindi sarebbe O(1). Altrimenti se devo verificare che l' intero array è una minheap perchè non lo so, dovrebbe essere la b, che io avrei a questo punto scelto.


Se invece noi abbiamo lo stesso caso(cioè sempre A) ma dobbiamo verificare se l' elemento x appartiene alla heap la complessità è:

a)O(1)
b)O(logn)
c)O(log^2n)
d)O(n)

Qui non potrebbero essere sia la b) che la d) ? Perchè essendo una heap un array in teoria io potrei dire che devo scorrere l' insieme, e quindi esaminare n elementi, da cui la risposta d), ma se consideriamo tutti i discorsi sulla heap, e che è rappresentato mediante albero, allora per cercarlo dovrei attraversare l' albero, e quindi mi verrebbe da dare la risposta b).
Opterei sempre per la d) visto che non è però un albero binario di ricerca.


Stavo provando a risolvere questa ricorrenza:

T(n)=5T(n/5)+n\log(n)

Al posto del teorema Master volevo provare per induzione che sia T(n)\leq cn\log(n)

Allora ho:

T(n)\leq 5c((\frac{n}{5}\log(\frac{n}{5}))+n\log(n)

T(n)\leq cn\log(n)-cn\log(5)+n\log(n)

Mi sembra che sbagli, ma comunque continuando non riesco ad arrivare ad una conclusione.....forse potrei considerare la base del logaritmo 5 e fare:

T(n)\leq cn\log(n)-cn+n\log(n)

Non saprei..
« Last Edit: 31-08-2011, 22:32:53 by Daréios » Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Pages: [1]   Go Up
Print
Jump to: