K numeri più grandi in A

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
carmnu
Messaggi: 9
Iscritto il: 13 giu 2007, 10:33

K numeri più grandi in A

Messaggio da carmnu » 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:

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)
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?

Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand » 13 giu 2007, 18:07

Penso che lo si possa fare in 3 passi: trovi il k-esimo più grande in tempo lineare con algoritmi classici, poi trovi i k più grandi in tempo lineare, semplicemente confrontandoli con il k-esimo, infine ordini questi elementi in O(k log k). In totale si richiede O(n + k log k) tempo.

carmnu
Messaggi: 9
Iscritto il: 13 giu 2007, 10:33

Messaggio da carmnu » 13 giu 2007, 18:26

rand ha scritto:Penso che lo si possa fare in 3 passi: trovi il k-esimo più grande in tempo lineare con algoritmi classici, poi trovi i k più grandi in tempo lineare, semplicemente confrontandoli con il k-esimo, infine ordini questi elementi in O(k log k). In totale si richiede O(n + k log k) tempo.
Si stavo proprio postando ora quest'altra soluzione a cui sono arrivato anche io e che ha un tempo computazionale proprio come quello richiesto, ovvero O(n + k log k).

Grazie!

kikketto
Messaggi: 3
Iscritto il: 04 lug 2007, 00:18

Messaggio da kikketto » 04 lug 2007, 00:21

ciao ragazzi ma se si devono trovare i k numeri più grandi in A con tempo O(n) come si puo risolvere??

Grazie anticipatamente
Francesco!!!

darklin
Messaggi: 10
Iscritto il: 23 mag 2007, 21:04

Messaggio da darklin » 13 lug 2007, 17:08

kikketto nn preoccuparti..de sancits nn mette un'altra volta lo stesso esercizio:d...

kikketto
Messaggi: 3
Iscritto il: 04 lug 2007, 00:18

Messaggio da kikketto » 14 lug 2007, 14:53

darklin ha scritto:kikketto nn preoccuparti..de sancits nn mette un'altra volta lo stesso esercizio:d...
ciao darklin allora perche non mi posti la risposta dell'esercizio????

:D :lol: :wink: :wink:


grazie!!!!!!

Rispondi