Ho una serie di altezze, con stazioni di diffusione irregolare, ad esempio arrH=[100 500 1000 2500 4500] . Durante l'esecuzione, ricevo un'altezza, h, e ho bisogno di determinare quale cella (indice) contiene l'altezza più vicina a h. Es .: h=720 -> arrH[1] .
Posso eseguire qualsiasi pre-elaborazione, creare qualsiasi dizionario / tabella hash in modalità offline.
Esiste la possibilità di ottenere O (1) durante l'esecuzione?
Grazie!
Se il valore massimo è ragionevole, è possibile farlo con una tabella di ricerca di lunghezza N dove N è il valore massimo dell'array. Quindi, ad esempio, la matrice è simile a questa:
[2,5,6,9]
Quindi crei un array simile a questo:
[0,0,0,1,2,2,3,3,3]
Le ricerche in quell'array sono O (1)
Ovviamente questo presuppone che avrai molte ricerche senza che l'array cambi, poiché penso che la creazione dell'array dovrebbe essere O (N) * O (Log (N)).
Nel caso generale (vale a dire, laddove l'ipotesi di piccola-massima altezza di Steven Burnap non regge, o in alternativa dove è necessario inserire valori a virgola mobile come input), credo che la risposta alla tua domanda sia no. Stai descrivendo un singolo passaggio attraverso un algoritmo che popola un istogramma con bin non uniformi. (Per una discussione sui vari compromessi nella costruzione dell'istogramma, vedi questa domanda di stackoverflow ).
L'ingenua implementazione di un algoritmo di istogramma-popolazione con bin non uniformi noti in precedenza viene eseguito in O (log n), con n il numero di bin, che è equivalente alla lunghezza di arrH - questa è semplicemente la ricerca binaria.
Come suggerisce il collegamento sopra, tuttavia, la ricerca di interpolazione consentirà un tempo ottimale di O (1) e un tempo medio inferiore a O (log n). Inoltre, a seconda di come non è uniforme la distribuzione del tuo cestino, puoi ottenere risultati ottimali in gran parte del tempo.
D'altro canto, poiché "costante" non significa necessariamente "piccolo", potresti benissimo fare meglio con la ricerca binaria ingenua se arrH è relativamente piccolo o la tua distribuzione bin è particolarmente patologica. Il punto di flesso in cui la ricerca di interpolazione inizia a fare sensibilmente meglio dovrebbe essere determinato tramite la profilazione.
Per farla breve: ricerca binaria - O (log n) - potrebbe essere il meglio che puoi fare, ma dai un'occhiata alla ricerca di interpolazione. Quale è meglio dipenderà intimamente dai tuoi dati.
Leggi altre domande sui tag database algorithms search