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 A = (a1, a2, ..., an) ed un intero 1 <= k <= n, si descriva ed analizzi un algoritmo che in tempo O(n + k log k) trovi i k numeri più grandi in A ordinati dal più piccolo al più grande.
Questa è la mia soluzione
Ho pensato di sfruttare la struttura dati heap, in particolare una funzione heapsort modificata. Praticamente a partire dall'array A costruisco l'heap tramite la funzione buidheap che si dimostra prende tempo O(n).
Quindi itero il for dell'heapsort non per tutta la lunghezza dell'array ma solo per k volte:
Codice: Seleziona tutto
heapsort_modificata(A, k)
buildheap(A)
i <- length[A]
for j <- k-1 downto 0 do
k_elementi[j] <- A[i]
scambio A[1] <-> A[i]
i <- i - 1
heapsize[A] <- heapsize[A] - 1
heapfy(A,1)Il problema è che se ho fatto tutto correttamente, la funzione dovrebbe impiegare tempo O(n + k log n), O(n) per costruire l'heap tramite buildheap e poi si hanno le k chiamate alla funzione heapfy che impiega tempo log n. Giusto? C'è quel log n che mi rovina...
Che dite si può fare di meglio? Voi come procedereste?
