Algoritmo di voto di maggioranza, ci sono n persone e m candidati ma m è noto

Question

Algoritmo di voto di maggioranza, ci sono n persone e m candidati ma m è noto

#1 da (2 voti)

1

La domanda è lunga, quindi la parafrasa brevemente

D: Ci sono n persone che votano per scegliere il presidente del comitato. Ogni persona può votare per una persona che ha un ID univoco (è un numero intero positivo e il voto sarà archiviato in array). La sedia sarà quella con il maggior numero di voti. Algoritmo di progettazione per determinare chi è la sedia e quale sarebbe la complessità temporale? Quindi se ci sono m < n candidati per la sedia e sappiamo il valore di m, quale sarebbe l'algoritmo per determinare chi è la sedia e la sua complessità temporale?

(Modifica: okay no all'algoritmo boyer-moore)

Per la seconda parte, non sono sicuro del perché il fatto di conoscere il valore di m faccia la differenza. L'ultima parte della domanda sembra che ci sia un modo più efficiente di risolvere il problema quando m è noto.

algorithms sorting

posta johnkiko 20.10.2016 - 05:26

fonte

1 risposta

Leggi altre domande sui tag algorithms sorting

Pattern per gestire diversi tipi di file Conversione di una grande base di codice PHP da mysql_ a PDO [closed]

score 2 · Accepted Answer

C'è una soluzione banale al problema mentre lo chiedi: crea una serie di contatori per i candidati, e per ogni voto incrementa il contatore di quel candidato; alla fine del voto, scansiona l'elenco e trova il valore più alto. O (n) complessità temporale sotto l'assunto n > > m (che sarebbe un prerequisito per rendere realisticamente fattibile un sistema di voto), o O (n + m) se non puoi assumere m è piccolo. O (m) archiviazione.

Se i tuoi id candidati non sono assegnati in modo sequenziale, la soluzione è un po 'più difficile, ma puoi semplicemente usare una tabella hash per mappare gli ID ai loro indici nella matrice. Questo non influisce sulla complessità poiché le hashtables hanno una ricerca tipica di O (1).

L'unica ragione per cui desideri realisticamente qualcosa di diverso da questa implementazione è se ti aspetti che "m" sia grande, ma sarebbe una situazione molto insolita.