Análisis de la sinergia de dos algoritmos en comparación con su simulación en paralelo.

Considere los siguientes dos algoritmos para buscar en una matriz ordenada de $n$ elementos:

A) búsqueda de interpolación y búsqueda binaria simulada en paralelo, y

B) busque a través de pasos de interpolación alternos y pasos binarios.

Ambos algoritmos son de peor complejidad de caso $2\lg n+1$ (y complejidad promedio $2\lg\lg n$ para una distribución razonable). ¿Existe un modelo de complejidad que permita separar esos dos algoritmos (que expresan cuándo uno es mejor que el otro)? En particular, ¿hay algún ejemplo en el que la simulación en paralelo supere al algoritmo de búsqueda mixta?

--- Algunos antecedentes básicos ---

1) Interpolación para el elemento en una matriz ordenada T entre la posición i y j hace una comparación en la posición g = i + ( j - i ) / ( T [ j ] - T [ i ] ) * ( x - T [ i ] ) y reduce el intervalo de búsqueda a [ i , g ] o ] g , j $x$$T$$i$$j$$g=i+(j-i)/(T[j]-T[i])*(x-T[i])$$[i,g]$$]g,j]$de acuerdo con el resultado (en oposición a la búsqueda binaria, que compara $x$ con el elemento en la posición $(i+j)/2$ )

$2\lg n+1$$A$$B$$f(n)$$g(n)$$A$$B$$2\min\{f(n),g(n)\}\in O(\min{f(n),g(n)})$$2\lg n+1$ también, porque el intervalo de búsqueda se reduce al menos en dos cada dos comparaciones.

En Willard's Searching Unindexed and Nonuniformly Generated Files in Time$\log \log N$ , hace referencia a una versión preliminar (del documento vinculado) titulada "Algoritmos de búsqueda sorprendentemente eficientes para archivos generados de manera no uniforme" que aparece en la 21ª Conferencia de Allerton sobre Control de la Comunicación y Computación en 1983, pp. 656-662. No puedo encontrar este documento en la web, pero en la versión posterior (vinculada) anterior, dice que el documento anterior muestra que la sinergia entre la búsqueda binaria y de interpolación puede reducir el tiempo de búsqueda a para ciertos -distribuciones uniformes de claves de registro.$o(\log n)$

Específicamente, llame a un PDF regular si hay modo que para o y y para . Para los datos producidos por archivos PDF normales, la búsqueda de interpolación toma tiempo esperado, mientras que la búsqueda binaria toma tiempo esperado. Sin embargo, intercalarlos lleva el tiempo esperado .$\mu$$b_1, b_2, b_3, b_4$$\mu(x) = 0$$x < b_1$$x > b_2$$\mu(x) \geq b_3 > 0$$|\mu\prime(x)| < b_4$$b_1 \leq x \leq b_2$$\Omega(\log n)$$\Theta(\log n)$$O(\sqrt{\log n})$

También le puede interesar el "procesamiento paralelo de Willard y Reif " puede ser perjudicial: el comportamiento inusual de la búsqueda de interpolación " , que muestra que" el procesamiento paralelo antes de la última iteración literal en la búsqueda de un archivo ordenado no indexado casi no tiene utilidad ".