Algoritmi di programmazione
ciao a tutti,
non riesco a risolvere questo esercizio di algoritmi:
Sia V [1 : n] un vettore di n valori non negativi. Si progetti un algoritmo che, dato V , due interi k ; j $in$ {1,2...,n}, restituisca i k valori di V piu vicini a V [j]. L'algoritmo deve avere complessita O(n log k). Si fornisca lo pseudocodice dettagliato dell'algoritmo.
La mia soluzione è questa:
- Creo un vettore A [1 : n] dove per ogni indice i da 0 fino a n metto: A = |V [j] - V | (modulo). Così ho la "distanza" tra il valore V [j] ed ogni singolo elemento del vettore.
Questo ha complessità O (n).
- Ora ordino l'array e così avrò dagli indici 2 a k+1 i k valori più vicini a V [j].
Mi sapreste dire con quale metodo di ordinamento riesco ad ottenere una complessità di O(n log k)?
C'è qualcuno che lo risolverebbe in un altro modo?
grazie
non riesco a risolvere questo esercizio di algoritmi:
Sia V [1 : n] un vettore di n valori non negativi. Si progetti un algoritmo che, dato V , due interi k ; j $in$ {1,2...,n}, restituisca i k valori di V piu vicini a V [j]. L'algoritmo deve avere complessita O(n log k). Si fornisca lo pseudocodice dettagliato dell'algoritmo.
La mia soluzione è questa:
- Creo un vettore A [1 : n] dove per ogni indice i da 0 fino a n metto: A = |V [j] - V | (modulo). Così ho la "distanza" tra il valore V [j] ed ogni singolo elemento del vettore.
Questo ha complessità O (n).
- Ora ordino l'array e così avrò dagli indici 2 a k+1 i k valori più vicini a V [j].
Mi sapreste dire con quale metodo di ordinamento riesco ad ottenere una complessità di O(n log k)?
C'è qualcuno che lo risolverebbe in un altro modo?
grazie
Risposte
Il tuo metodo ha complessità O(n log n), che è la complessità dell'ordinamento di un array di n elementi.
Potresti usare un red-black tree. Per ogni elemento i dell'array:
Potresti usare un red-black tree. Per ogni elemento i dell'array:
[*:2h3ftr4e]se nell'albero ci sono meno di k elementi lo inserisci (O(log k));[/*:m:2h3ftr4e]
[*:2h3ftr4e]altrimenti, controlli se l'elemento è maggiore del maggiore elemento nell'albero (O(1) se mantieni un riferimento all'elemento maggiore):
[*:2h3ftr4e] se sì lo scarti (è meno vicino di tutti gli elementi già nell'albero);[/*:m:2h3ftr4e]
[*:2h3ftr4e] se no, estrai l'ultimo elemento dall'albero (O(log k)) e inserisci i (O(log k)).[/*:m:2h3ftr4e][/list:u:2h3ftr4e][/*:m:2h3ftr4e][/list:u:2h3ftr4e]
Le operazioni di inserimento, rimozione e ricerca di un red-black tree di k elementi hanno complessità O(log k). Ripeti su tutti gli elementi dell'array, la complessità finale è O(n log k).
mmm, non fa parte del programma questo tipo di albero, però questa soluzione è interessante. Praticamente sarebbe un albero AVL in cui inserisco solo k degli n elementi dell'array, giusto?
grazie comunque
grazie comunque
Sì, è un tipo di albero simile ad AVL. L'importante è che sia bilanciato, così che le varie operazioni abbiano costo logaritmico. Se inserisci solo k elementi (se ne inserisci di più, prima togli quelli in eccesso) il numero di elementi nell'albero è sempre minore o uguale a k, quindi le operazioni costano O(log k).
Esistono anche strutture più efficienti, come gli alberi di Van Emde Boas, che hanno complessità O(log log k). Però in realtà il guadagno c'è solo per valori enormi di k.
Esistono anche strutture più efficienti, come gli alberi di Van Emde Boas, che hanno complessità O(log log k). Però in realtà il guadagno c'è solo per valori enormi di k.
ok grazie,
sei stato gentilissimo
sei stato gentilissimo
Alternativamente, si possono usare i binary heap (un albero di priorità) come segue:
1. Copiare i primi \(k\) indici dell'array in un array ausiliario (\(O(k)\)).
2. Applicare l'algoritmo di costruzione in place di un max-heap all'array ausiliario (\( O(k) \)) usando la distanza tra il valore dell'array corrispondente all'indice e V[j] come "priorità".
3. Per ogni \(i\) da \(k+1\) a \( n \) confrontare la distanza corrispondente all'indice di distanza massima dal max-heap con la distanza tra V e V[j] (\ O(1) \)).
4. Se la distanza tra V e V[j] è minore di quella dell'indice massimo, estrarre l'indice massimo dal max-heap (\( O(\log\,k) \)) e inserire \(i\) nel max-heap (\( O(\log\,k) \)).
In totale è quindi \( O(n\,\log\,k)\) come richiesto... Di fatto non è particolarmente diverso dagli alberi AVL o Red-Black anche se è a mio parere potenzialmente più semplice da implementare e più veloce per \(k\) piccoli (l'albero è interamente contenuto nella cache).
1. Copiare i primi \(k\) indici dell'array in un array ausiliario (\(O(k)\)).
2. Applicare l'algoritmo di costruzione in place di un max-heap all'array ausiliario (\( O(k) \)) usando la distanza tra il valore dell'array corrispondente all'indice e V[j] come "priorità".
3. Per ogni \(i\) da \(k+1\) a \( n \) confrontare la distanza corrispondente all'indice di distanza massima dal max-heap con la distanza tra V e V[j] (\ O(1) \)).
4. Se la distanza tra V e V[j] è minore di quella dell'indice massimo, estrarre l'indice massimo dal max-heap (\( O(\log\,k) \)) e inserire \(i\) nel max-heap (\( O(\log\,k) \)).
In totale è quindi \( O(n\,\log\,k)\) come richiesto... Di fatto non è particolarmente diverso dagli alberi AVL o Red-Black anche se è a mio parere potenzialmente più semplice da implementare e più veloce per \(k\) piccoli (l'albero è interamente contenuto nella cache).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo