Perché la lunghezza dell'elenco si riduce a sqrt (n) dopo ogni confronto nella ricerca di interpolazione?

Question

In base al libro che sto leggendo, la ricerca di interpolazione prende in genere O(loglogn).
Il libro presuppone che ogni confronto riduca la lunghezza della lista da n a sqrt(n). Bene, non è difficile capire il O(loglogn) dato questo presupposto.
Tuttavia, il libro non parla più di questo assunto tranne che dice che è corretto.

Domanda: qualcuno può dare qualche spiegazione sul motivo per cui questo è vero?

Answer 1

Dipende dal fatto che l'input è distribuito uniformemente (senza tale ipotesi, O (log n) è il meglio che si possa fare teoricamente, cioè la ricerca binaria è ottimale). Con una distribuzione uniforme, la varianza è intorno a sqrt (n), e nel caso previsto ogni iterazione colpisce all'interno della varianza del target. Quindi, come dici tu, lo spazio di ricerca va da n -> sqrt (n) a ogni iterazione.

Answer 2

Immaginate una matrice ordinata in cui ogni voce è un numero da uno a un milione. Vuoi vedere se 10000 è nella matrice. Poiché 10000 è inferiore al 99% dei numeri inferiori a un milione, se l'array ha una buona distribuzione di numeri, è probabile che una voce di 10000, se presente nell'array, sia molto vicina all'inizio. Se guardiamo a una voce dell'1% percento della via attraverso l'array e scopriamo che è superiore a 10000, abbiamo eliminato il 99% dell'array in un unico passaggio. Questo è molto meglio di una ricerca binaria, che guarda solo a metà di un intervallo, e quindi può eliminare solo al massimo metà dello spazio di ricerca alla volta. Questo è intuitivamente il motivo per cui la ricerca di interpolazione in alcuni casi può essere molto più veloce della ricerca binaria.

Per visualizzare l'analisi rigorosa del motivo per cui è previsto che sia O (log log n), è necessario leggere un manuale o un documento sull'algoritmo.