[Dati e Algoritmi] Esercizio: vincitore alle elezioni
Ciao a tutti! Sto facendo il seguente esercizio:
In un’elezione sono presenti k candidati, ciascuno identificato da un diverso numero
intero. I voti espressi dagli n elettori (n > k) sono stati raccolti in una lista S (ciascun
elemento della lista è uno dei voti espressi e ciascun voto è un numero intero che
corrisponde al candidato votato dall’elettore). Nell’ipotesi che venga dichiarato vincente il
candidato che ha ricevuto più voti, progettare un algoritmo che, in un tempo $O(n \log k)$,
dichiari il vincitore (per semplicità, in caso di pareggio si può nominare vincitore uno
qualsiasi dei candidati che hanno ricevuto più voti). La lista non può essere modificata. Se
l’algoritmo utilizza strutture dati aggiuntive, descrivere con chiarezza quali sono e come
vengono utilizzate dall’algoritmo.
Il problema è rimanere nel limite temporale.
Non avendo manco il range delle chiavi k, non ha senso pensare a un array di bucket (ordinamento con funzione hash).
Idea 1:
Provando a salvare i dati in un AVL, si può ragionare in questo modo:
1. estraggo ogni volta dalla lista dei voti e creo un nodo che ha come chiave - k, oggetto - il numero di voti che inserisco
nell'AVL
2. per inserire si fa ogni volta la ricerca, e se un nodo con chiave k è già presente - somma 1 al suo numero di voti altrimenti
aggiungi il nuovo nodo appena costruito con oggetto = 1 (voto)
3. Trova il massimo: attraversamento dell'AVL tenendo una variabile max confrontata con il numero di voti di
ogni candidato.
i passaggi 1,2: per ogni inserimento (n) un tempo logk (inserimento AVL) quindi tempo $O(n\logk)$
Il problema sorge al terzo punto: l'attraversamento è $O(k)$ (k candidati) quindi il tempo complessivo è $O(k+n\logk)$
Il k a quanto pare dipende da n e non può essere trascurato altrimenti sarebbe stato trascurato dalla consegna (e sarebbe stato O(n)) quindi molto probabilmente la mia soluzione non va bene. C'è qualcosa di meglio che non riesco a trovare.
Idea 2:
Salvo i dati in una Max Priority Queue costruita con uno Heap e uso un array ausiliario che chiamo Keys.
A differenza di prima, qui MaxPQ verrà ordinata secondo il numero di voti (chiave) mentre l'oggetto sarà il nome del candidato. La MaxPQ deve essere particolare, ricevere i dati per nodi già creati i cui riferimenti verranno salvati nell'array Keys mentre vengono inseriti, all'indice "$k_i$" del candidato (indice candidato). Di conseguenza l'array Keys potrebbe essere enorme anche se le celle occupate saranno solo "k". Questo mi consente anche di verificare mentre inserisco se c'è già un candidato inserito nella MaxPQ e se Keys[k] esiste (c'è il riferimento al nodo) allora vado al nodo e sommo un voto alla chiave e in questo modo faccio un Heapsort.
Un heapsort ha prestazioni temporali $O(logk)$. Essendo gli inserimenti o modifiche $n$ allora $O(nlogk)$
Alla fine MaxPQ avrà in cima il vincitore (o uno dei vincitori) che quando me lo restituisce come nodo, basta che v.getElement() e ho il candidato.
L'array Keys potrebbe avere tante celle vuote per colpa dei valori k che è sconosciuto. Però sono prestazioni di memoria e non temporali. Ma il ragionamento dei riferimenti ai nodi inseriti nella MaxPQ non mi convince non so nemmeno se è possibile e se quando avviene il Heapsort è possibile mantenerli uguali.
Qualcuno ha idee migliori? Magari basterebbe qualche correzione a qualcuna delle idee o miglioramento
In un’elezione sono presenti k candidati, ciascuno identificato da un diverso numero
intero. I voti espressi dagli n elettori (n > k) sono stati raccolti in una lista S (ciascun
elemento della lista è uno dei voti espressi e ciascun voto è un numero intero che
corrisponde al candidato votato dall’elettore). Nell’ipotesi che venga dichiarato vincente il
candidato che ha ricevuto più voti, progettare un algoritmo che, in un tempo $O(n \log k)$,
dichiari il vincitore (per semplicità, in caso di pareggio si può nominare vincitore uno
qualsiasi dei candidati che hanno ricevuto più voti). La lista non può essere modificata. Se
l’algoritmo utilizza strutture dati aggiuntive, descrivere con chiarezza quali sono e come
vengono utilizzate dall’algoritmo.
Il problema è rimanere nel limite temporale.
Non avendo manco il range delle chiavi k, non ha senso pensare a un array di bucket (ordinamento con funzione hash).
Idea 1:
Provando a salvare i dati in un AVL, si può ragionare in questo modo:
1. estraggo ogni volta dalla lista dei voti e creo un nodo che ha come chiave - k, oggetto - il numero di voti che inserisco
nell'AVL
2. per inserire si fa ogni volta la ricerca, e se un nodo con chiave k è già presente - somma 1 al suo numero di voti altrimenti
aggiungi il nuovo nodo appena costruito con oggetto = 1 (voto)
3. Trova il massimo: attraversamento dell'AVL tenendo una variabile max confrontata con il numero di voti di
ogni candidato.
i passaggi 1,2: per ogni inserimento (n) un tempo logk (inserimento AVL) quindi tempo $O(n\logk)$
Il problema sorge al terzo punto: l'attraversamento è $O(k)$ (k candidati) quindi il tempo complessivo è $O(k+n\logk)$
Il k a quanto pare dipende da n e non può essere trascurato altrimenti sarebbe stato trascurato dalla consegna (e sarebbe stato O(n)) quindi molto probabilmente la mia soluzione non va bene. C'è qualcosa di meglio che non riesco a trovare.
Idea 2:
Salvo i dati in una Max Priority Queue costruita con uno Heap e uso un array ausiliario che chiamo Keys.
A differenza di prima, qui MaxPQ verrà ordinata secondo il numero di voti (chiave) mentre l'oggetto sarà il nome del candidato. La MaxPQ deve essere particolare, ricevere i dati per nodi già creati i cui riferimenti verranno salvati nell'array Keys mentre vengono inseriti, all'indice "$k_i$" del candidato (indice candidato). Di conseguenza l'array Keys potrebbe essere enorme anche se le celle occupate saranno solo "k". Questo mi consente anche di verificare mentre inserisco se c'è già un candidato inserito nella MaxPQ e se Keys[k] esiste (c'è il riferimento al nodo) allora vado al nodo e sommo un voto alla chiave e in questo modo faccio un Heapsort.
Un heapsort ha prestazioni temporali $O(logk)$. Essendo gli inserimenti o modifiche $n$ allora $O(nlogk)$
Alla fine MaxPQ avrà in cima il vincitore (o uno dei vincitori) che quando me lo restituisce come nodo, basta che v.getElement() e ho il candidato.
L'array Keys potrebbe avere tante celle vuote per colpa dei valori k che è sconosciuto. Però sono prestazioni di memoria e non temporali. Ma il ragionamento dei riferimenti ai nodi inseriti nella MaxPQ non mi convince non so nemmeno se è possibile e se quando avviene il Heapsort è possibile mantenerli uguali.
Qualcuno ha idee migliori? Magari basterebbe qualche correzione a qualcuna delle idee o miglioramento
Risposte
Personalmente trovo assurdo parlare di elezione e considerare il range \(k\) come sconosciuto, e non avrei messo i voti in una lista. Nel caso in cui i candidati vadano da \(1\) a \(k\) (con \(k\) ricevuto come input) è possibile trovare il vincitore in \(O(n+k)\) con un array aggiuntivo di dimensione \(k\). Tra l'altro, essendo possibile trovare il range in tempo \(O(n)\), la complessità risulta essere \(O(n+k)\) anche nel caso in cui i valori per i candidati sono consecutivi o in cui i valori possano essere mappati in tempo costante da o per un range di questo tipo.
Dalla complessità penso che il professore pensasse all'uso di una priority queue, ma una cosa di questo tipo ha senso solo se i candidati hanno codici identificativi "difficili" e non esiste un modo efficiente per trasformare gli identificativi in un range più sensato, oppure se si voglia sapere in ogni dato momento chi sta vincendo. Personalmente trovo però che tu stia cercando di risolvere un problema più difficile di quello che è necessario risolvere.
Trovo inoltre che il tuo secondo algoritmo sia stato ulteriormente complicato. Infatti ti bastava usare un heap che conteneva coppie di interi (un identificativo e un contatore su cui l'heap era "ordinato").
Dalla complessità penso che il professore pensasse all'uso di una priority queue, ma una cosa di questo tipo ha senso solo se i candidati hanno codici identificativi "difficili" e non esiste un modo efficiente per trasformare gli identificativi in un range più sensato, oppure se si voglia sapere in ogni dato momento chi sta vincendo. Personalmente trovo però che tu stia cercando di risolvere un problema più difficile di quello che è necessario risolvere.
Trovo inoltre che il tuo secondo algoritmo sia stato ulteriormente complicato. Infatti ti bastava usare un heap che conteneva coppie di interi (un identificativo e un contatore su cui l'heap era "ordinato").
"vict85":
Trovo inoltre che il tuo secondo algoritmo sia stato ulteriormente complicato. Infatti ti bastava usare un heap che conteneva coppie di interi (un identificativo e un contatore su cui l'heap era "ordinato").
Intanto grazie per la risposta
Forse non sono stato chiaro ma intendevo infatti di usare il numero dei voti come chiave in base alla quale viene ordinato mentre l'oggetto è l'identificativo. In ogni caso la PQ non basta perché in una PQ costruita con uno Heap non riesco a modificare i nodi a parte la radice in un tempo ragionevole quando devo sommare i nuovi voti. A differenza dell'AVL qui per trovare un nodo devo attraversare l'albero quindi verrebbe O(k). I voti sono n allora $O(nk)$
Lo sento anche io che ho scritto una soluzione troppo complicata e spero di capire dove ho sbagliato o se c'è qualche modo più semplice
\(k\) NON dipende da \(n\).. È un numero del tutto indipendente. Sai comunque che \(k < n\) per cui è certamente trascurabile rispetto a \(n\,\log\,k\). La prima soluzione è quindi probabilmente quello che il tuo professore aveva in mente (se non ci fosse stata la richiesta di non modificare la lista una soluzione più semplice sarebbe stata di ordinare la lista). Nella seconda soluzione ti stai solo complicando la vita, cercare il vincitore iterando nella mappa è certamente fattibile rimanendo nella complessità richiesta.
Ma allora a questo punto se lo trascuro da una parte, lo faccio anche dal l'altra focalizzandomi su $n$ quindi $O(n\logk)=\logkO(n)=O(n)$ no? Forse non l'ha fatto per farci intuire guardano il logaritmo che ci voleva un albero di ricerca
No. È chiaro che il professore è interessato a studiare la complessità in funzione di entrambe le variabili. Elimini il primo \(k\) perché \(k < n\) e quindi \( k + n\,\log\,k < n + n\,\log\,k = n\,(1 + \log\,k) \leq C\,n\,\log\,k \) (per una opportuna costante \(C\)) da cui abbiamo che \(O(k + n\,\log\,k) = O(n\,\log\,k). \) L'altra parte non è trascurabile, a meno di supporre che \(k\) sia una costante nella nostra analisi.
Grazie mille
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo