Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Algoritmi, 9 CFU => Topic started by: Daréios89 on 31-08-2011, 21:50:35



Title: Quesiti su heap e induzione
Post by: Daréios89 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..