¿Cómo encuentras todos los enteros en una matriz ordenada de tamaño N que aparecen n / k veces?

Question

Intento encontrar la solución a este problema: ¿Cómo encontrar todos los enteros en una matriz ordenada de tamaño N que aparecen n / k veces en menos que o (klogn)?

Solo pude encontrar esta pregunta , donde se proporcionó la solución O (Klogn).

Answer 1

Vamos a empezar con el caso $ k= 2 $ y asume que el algoritmo se basa en comparación.

Afirmo que cualquier algoritmo que encuentra incluso un solo elemento que aparece $ n / 2 $ veces debe conocer un índice $ i $ de tal manera que $ a [i + 1]= a [i + n / 2] $ . De hecho, suponga que este no es el caso, y asumamos por simplicidad que las entradas de $ a $ son números reales. Digamos que el algoritmo conoce los siguientes valores: $$ A [I_1]=CDOTS= A [J_1] Es consistente con el conocimiento del algoritmo que $ a [i_1-1] y así sucesivamente, y con un poco Es un esfuerzo que podemos organizar que no haya ningún elemento que aparezca $ n / 2 $ veces.

Considere ahora el $ n / 2 + 1 $ matrices del siguiente formulario: hay una ejecución de $ n / 2 $ Muchos $ 0 $ s Empezando en alguna posición $ j \ in \ {1, \ ldots, n / 2 + 1 \} $ , y el resto de los elementos son únicos. En cada matriz de este tipo, hay una opción única para el índice $ i $ mencionado anteriormente. Por lo tanto, el árbol de decisiones que representa al algoritmo tiene al menos $ n / 2 + 1 $ hojas, por lo que debe tener profundidad $ \ Omega (\ log n) $ .

---

En el caso general, el algoritmo debe conocer un índice $ i $ de tal que $ a [i + 1]= A [i + n / k] $ para cada elemento que se emite. Podemos particionar la matriz en $ k / 2 $ partes de tamaño $ 2n / k $ y considere $ (n / k + 1) ^ k $ ejemplos como antes, donde el $ r $ el elemento Apareciendo $ n / k $ Times está en el $ r $ th Part. Esto le da un límite inferior de $ \ omega (k \ log (n / k)) $ , que coincide con su límite superior para casi todos los valores de $ k $ .

(los algoritmos probablemente se pueden mejorar ligeramente para dar un límite superior coincidente).