Come trovi tutti i numeri interi in una serie di dimensioni ordinate che appaiono n / k volte?

Question

Provo a trovare la soluzione a questo problema: Come trovi tutti i numeri interi in una serie ordinata di dimensioni n che appaiono n / k volte in meno che o (klogn) tempo?

Potrei trovare solo Questa domanda , dove è stata fornita la soluzione O (Klogn).

Answer 1

Iniziamo con il caso $ k= 2 $ e presumere che l'algoritmo sia basato sul confronto.

I rivendico che qualsiasi algoritmo che trovi anche un singolo elemento che appare $ N / 2 $ I tempi devono conoscere un indice $ I $ in modo tale che $ a [i + 1]= a [i + n / 2] $ . Infatti, supponiamo che questo non sia il caso, e ci supponiamo di semplicità che le voci di $ A $ sono numeri reali. Diciamo che l'algoritmo noto i seguenti valori: $$ A [i_1]=cdots= a [j_1] È coerente con la conoscenza dell'algoritmo che $ a [i_1-1] e così via, e con un po ' Sforzo che possiamo organizzare che non ci sia elemento che appare $ n / 2 $ volte.

Considera ora la $ N / 2 + 1 $ array del modulo seguente: C'è una corsa di $ n / 2 $ Molte $ 0 $ s Avvio di alcune posizioni $ j \ in \ {1, \ Ldots, n / 2 + 1 \} $ e il resto degli elementi è unico. In ogni tale array, c'è una scelta unica per l'indice $ i $ menzionato sopra. Quindi l'albero decisionale che rappresenta l'algoritmo ha almeno $ n / 2 + 1 $ foglie, e quindi deve avere profondità $ \ Omega (\ log n) $ .

---

.

Nel caso generale, l'algoritmo dovrebbe conoscere un indice $ i $ tale che $ A [I + 1]= A [I + N / K] $ per ciascun elemento che viene emesso. Possiamo partizionare l'array in $ k / 2 $ parti della taglia $ 2n / k $ e considerare $ (n / k + 1) ^ k $ esempi come prima, dove la classe $ R $ Elemento apparendo $ N / k $ I tempi è nella $ r $ parte. Questo dà un limite inferiore di $ \ omega (k \ log (n / k)) $ , abbinando il tuo limite superiore per quasi tutti i valori di $ k $ .

(gli algoritmi possono probabilmente essere migliorati in larmente per dare un limite superiore corrispondente.)