Qual è l'algoritmo più veloce per trovare un elemento con più alta frequenza in una matrice

Question

Ho due array di ingresso X e Y. voglio tornare quell'elemento di matrice X che si verifica con più alta frequenza in serie Y.

Il il modo ingenuo di fare ciò richiede che per ogni elemento x dell'array X, io ricerchi linearmente l'array Y per il suo numero di occorrenze e poi restituisca quell'elemento x che ha la frequenza più alta. Ecco l'algoritmo pseudo:

max_frequency = 0 
max_x = -1    // -1 indicates no element found 
For each x in X 
    frequency = 0 
    For each y in Y 
     if y == x 
      frequency++ 
    End For 
    If frequency > max_frequency 
     max_frequency = frequency 
     max_x = x 
    End If 
End For 
return max_x 

Poiché ci sono due cicli annidati, tempo complessità di questo algoritmo sarebbe O (n^2). Posso farlo in O (nlogn) o più velocemente?

Answer 1

utilizzare una tabella hash chiavi di mappatura per i conteggi. Per ogni elemento dell'array, fai come counts[element] = counts[element] + 1 o equivalente della tua lingua.

Al termine, eseguire il ciclo attraverso i mapping nella tabella hash e trovare il valore max.

Answer 2

Potrebbe fare un quicksort e quindi attraversarlo con una variabile che conta quanti numeri sono in fila + che numero è. Che dovrebbe darvi nlogn

Answer 3

Merge Ordinando Sulla base di divide et impera Concetto ti dà O (nlogn) complessità

Answer 4

In alternativa, se si dispone di strutture dati aggiuntive, si cammina l'array Y, per ciascun numero che aggiorna la frequenza in una tabella hash. Questo richiede tempo O(N(Y). Quindi cammina X trovando quale elemento in X ha la frequenza più alta. Questo richiede tempo O(N(X)). Complessivamente: tempo lineare e poiché è necessario esaminare ogni elemento di entrambi e Y in qualsiasi implementazione almeno una volta (MODIFICA: Questo non è propriamente vero in tutti i casi/tutte le implementazioni, come jwpat7 punti, anche se è vero nel caso peggiore), non puoi farlo più velocemente di così.

Answer 5

la complessità temporale degli algoritmi comuni sono elencati di seguito:

Algorithm  | Best | Worst | Average 
--------------+-----------+-----------+---------- 
MergeSort  | O(n lg n) | O(n lg n) | O(n lg n) 
InsertionSort | O(n) | O(n^2) | O(n^2) 
QuickSort  | O(n lg n) | O(n^2) | O(n lg n) 
HeapSort  | O(n lg n) | O(n lg n) | O(n lg n) 
BinarySearch | O(1) | O(lg n) | O(lg n) 

In generale, quando si attraversa attraverso un elenco di soddisfare un certo criterio, davvero non si può fare meglio di tempo lineare. Se è necessario ordinare l'array, direi stick con Mergesort (molto affidabile) per trovare l'elemento con la più alta frequenza in un array.

Nota: Si presuppone che si desideri utilizzare un algoritmo di ordinamento. Altrimenti, se ti è consentito utilizzare qualsiasi struttura dati, andrei con una struttura di tipo hashmap/hashtable con tempo di ricerca costante. In questo modo, ti basta abbinare le chiavi e aggiornare la coppia chiave-valore di frequenza. Spero che questo ti aiuti.

Answer 6

L'approccio suggerito sarà O (n^2) se entrambe le liste sono lunghe n. Quel che è più probabile è che gli elenchi possono avere lunghezze diverse, quindi la complessità temporale può essere espressa come O (mn).

È possibile separare il problema in due fasi: 1. Ordine gli elementi unici da Y per la loro frequenza 2. Trova il primo elemento da questa lista che esiste in X

Mentre questo suona come una domanda compiti a casa Ti lascerò pensare a quanto velocemente puoi fare questi passi individuali. La somma di questi costi ti darà il costo complessivo dell'algoritmo. Esistono molti approcci che saranno meno costosi del prodotto delle due lunghezze di lista attualmente disponibili.

Answer 7

1a fase: Ordinare sia X e Y. Supponendo che le lunghezze corrispondenti siano m e n, la complessità di questo passaggio sarà O(n log n) + O(m log m).

2a Fase: conteggia ogni X _i in Y e tiene conteggio massimo finora. Ricerca di X _i in ordinato Y è O(log n). Totale 2 ° passo complessità è:

complessità totale: O(n log n) + O(m log m) + O(m log n), o Simpified: O(max(n,m) log n)

Answer 8

Ordina X e Y. poi fare merge sort. Contare le frequenze da Y ogni volta che incontra lo stesso elemento in X.

Così complessità, O (nlogn) + O (mlogm) + O (m + n) = O (klogk) dove n, m = lunghezza di X, Y; k = max (m, n)