Come trovi tutti i numeri interi in una serie di dimensioni ordinate che appaiono n / k volte?
-
29-09-2020 - |
Domanda
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).
Soluzione
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.
.
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.)