K numeri più grandi in A
Inviato: 13 giu 2007, 11:16
Ciao a tutti raga, è il mio primo post per me, che sono una mezza cazetta, in questo forum di geni.
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:
k_elementi è l'array di appoggio in cui alla fine della funzione avrò i k numeri più grandi di A ordinati in modo crescente.
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?
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?
