Hay un algoritmo conocido para encontrar el elemento más pequeño [math] k_th [/ math] en una matriz desordenada de n elementos. También podemos usar el algoritmo para encontrar la mediana, ya que la mediana será [matemática] \ frac {n + 1} {2} [/ matemática] elemento más pequeño si [matemática] n [/ matemática] es impar, y el promedio de [ matemática] \ lceil {\ frac {n + 1} {2}} \ rceil [/ math] y [math] \ lfloor {\ frac {n + 1} {2}} \ rfloor [/ math] elemento más pequeño cuando [ matemáticas] n [/ matemáticas] es par.
El algoritmo se basa en una estrategia de divide y vencerás. Así que redefinamos nuestro problema:
Problema: Dada una matriz [matemática] A = A [1,…, n] [/ matemática] de [matemática] n [/ matemática] números y un índice [matemática] k (1≤k≤n) [/ matemática] , encuentre el elemento [math] k_ {th} [/ math] más pequeño de A.
- ¿Cuál es la diferencia entre Basic Auth, Digest Auth, oAuth1.0 y oAuth2.0? ¿Cuál es un ejemplo de cada uno en el núcleo de PHP?
- ¿Cuál es su consejo para alguien que comienza su doctorado en informática teórica?
- ¿Cuál es una explicación para esta ecuación de números de punto fijo con signo?
- ¿Probar la conjetura de Goldbach ternario ayuda a probar la conjetura de Goldbach fuerte (binaria)?
- Cómo resolver [matemáticas] (n + k) ^ j = \ Theta (n ^ j) [/ matemáticas] para k, j en números reales y j> 0
Algoritmo: SELECCIONAR (A, i)
Divida los n elementos en grupos de 5 (más el resto).
Encuentre la mediana de cada grupo de 5 (de memoria). (Si el grupo restante tiene un número par de elementos, entonces rompa los lazos arbitrariamente, por ejemplo, eligiendo la mediana inferior).
Use SELECT recursivamente para encontrar la mediana (llámela x) de estos
Techo (n / 5) medianas.
Partición alrededor de x. Deje k = rango (x).
Si i = k, entonces devuelve x.
De lo contrario, si i <k, use SELECT recursivamente llamando a SELECT (A [1, …, k − 1], i).
De lo contrario, si i> k, use SELECT recursivamente llamando a SELECT (A [k + 1, …, i], i − k).
Tiempo de ejecución:
Para demostrar que nuestro algoritmo es eficiente, sería útil saber que el subarreglo activo en cada llamada recursiva sucesiva es mucho más pequeño que el subarreglo anterior. De esa manera, tenemos la garantía de que solo son necesarias relativamente pocas llamadas recursivas. Por lo tanto, determinemos un límite superior en el tamaño de [math] A ‘[/ math], el nuevo subarray activo, dado que el viejo subarray, [math] A [/ math], tenía un tamaño [math] n [/ math ]
Como en la línea [matemáticas] 7 [/ matemáticas], dejemos que [matemáticas] x [/ matemáticas] sea la mediana de las medianas. Entonces, [math] A ‘[/ math] no contiene ningún elemento mayor que [math] x [/ math], o [math] A’ [/ math] no contiene ningún elemento menor que [math] x [/matemáticas]. Sin embargo, como veremos, hay muchos elementos mayores que xy muchos elementos menores que [math] x [/ math]. En particular, cada grupo (no resto) cuya mediana es menor que [matemáticas] x [/ matemáticas] contiene al menos tres elementos menos que [matemáticas] x [/ matemáticas], y cada grupo (no resto) cuya mediana es mayor que [matemáticas] x [/ matemáticas] contiene al menos tres elementos mayores que [matemáticas] x [/ matemáticas]. Además, hay al menos [math] \ lceil {\ frac {n} {5}} \ rceil – 1 [/ math] grupos no restantes, de los cuales al menos [math] \ lfloor {\ frac {1} { 2} \ lceil {\ frac {n} {5}} \ rceil – 2} \ rfloor [/ math] tienen una mediana menor que [math] x [/ math] y al menos [math] \ lfloor {\ frac {1 } {2} \ lceil {\ frac {n} {5}} \ rceil – 2} \ rfloor [/ math] tienen una media mayor que [math] x [/ math]. Finalmente, el grupo con [matemática] x [/ matemática] como su mediana contiene dos elementos mayores que [matemática] x [/ matemática] y dos elementos menores que [matemática] x [/ matemática] (a menos que [matemática] n <5 [/ matemáticas]) Por lo tanto,
[matemática] \ text {número de elementos de A menor que x} \ geq \ frac {3n} {10} + 6 [/ matemática]
y
[matemáticas] \ text {número de elementos de A mayor que x} \ geq \ frac {3n} {10} + 6 [/ matemáticas]
Entonces obtenemos una recurrencia generalizada del problema como:
[matemáticas] \ boxed {T (n) \ leq T (\ lceil {\ frac {n} {5}} \ rceil) + T (\ frac {7n} {10} + 6) + O (n)} [ /matemáticas]
Al resolver esta recurrencia utilizando el teorema del Maestro [1], de hecho obtenemos [matemáticas] T (n) [/ matemáticas] como [matemáticas] O (n). [/ Matemáticas]
A continuación se muestra una función C ++ [2] para implementar lo mismo:
// Una función simple para encontrar la mediana de arr []. Se llama
int findMedian (int arr [], int n)
{
ordenar (arr, arr + n); // Ordenar la matriz
retorno arr [n / 2]; // Devuelve el elemento medio
}
intercambio nulo (int * a, int * b)
{
int temp = * a;
* a = * b;
* b = temp;
}
// Busca x en arr [l..r] y divide la matriz
// alrededor de x.
partición int (int arr [], int l, int r, int x)
{
// Busca x en arr [l..r] y muévelo al final
int i;
para (i = l; i <r; i ++)
if (arr [i] == x)
rotura;
swap (& arr [i], & arr [r]);
// Algoritmo de partición estándar
i = l;
para (int j = l; j <= r – 1; j ++)
{
if (arr [j] <= x)
{
swap (& arr [i], & arr [j]);
i ++;
}
}
swap (& arr [i], & arr [r]);
volver i;
}
// Devuelve el elemento k’th más pequeño en arr [l..r] en el peor de los casos
// tiempo lineal. ASUNCIÓN: TODOS LOS ELEMENTOS EN ARR [] SON DISTINTOS
int kthSmallest (int arr [], int l, int r, int k)
{
// Si k es menor que el número de elementos en la matriz
si (k> 0 && k <= r – l + 1)
{
int n = r-l + 1; // Número de elementos en arr [l..r]
// Divide arr [] en grupos de tamaño 5, calcula la mediana
// de cada grupo y guárdelo en la matriz mediana [].
int i, mediana [(n + 4) / 5]; // Habrá grupos de piso ((n + 4) / 5);
para (i = 0; i <n / 5; i ++)
mediana [i] = findMedian (arr + l + i * 5, 5);
if (i * 5 <n) // Para el último grupo con menos de 5 elementos
{
mediana [i] = findMedian (arr + l + i * 5, n% 5);
i ++;
}
// Encuentra la mediana de todas las medianas usando llamadas recursivas.
// Si mediana [] tiene solo un elemento, entonces no es necesario
// de llamada recursiva
int medOfMed = (i == 1)? mediana [i-1]:
kthSmallest (mediana, 0, i-1, i / 2);
// Particionar la matriz alrededor de un elemento aleatorio y
// obtiene la posición del elemento pivote en una matriz ordenada
int pos = partición (arr, l, r, medOfMed);
// Si la posición es la misma que k
si (pos-l == k-1)
volver arr [pos];
if (pos-l> k-1) // Si la posición es más, recurrir a la izquierda
return kthSmallest (arr, l, pos-1, k);
// De lo contrario, se repite para la submatriz derecha
return kthSmallest (arr, pos + 1, r, k-pos + l-1);
}
// Si k es más que el número de elementos en la matriz
devolver INT_MAX;
}
También escribí un programa para generar un conjunto de datos aleatorio y luego tracé un gráfico en R para demostrar la diferencia.
vector generateRandomArray (int * arr, int n)
{
vector v (n);
srand (tiempo (NULL)); // Solo por ejemplo
generar (v.begin (), v.end (), rand);
copy (v.begin (), v.end (), arr);
volver v;
}
int main ()
{
salida corriente;
fout.open (“analysis.txt”);
fout << "MEIDAN_OF_MEDIAN REGULAR_SORTING \ n";
para (int i = 1000; i <= 1000000; i + = 1000)
{
int arr [i];
vector v = generateRandomArray (arr, i);
int mediana;
clock_t start, endd;
doble msecs1, msecs2;
inicio = reloj ();
// para (int j = 0; j <50; ++ j)
mediana = (kthSmallest (arr, 0, i – 1, i / 2) + kthSmallest (arr, 0, i-1, i / 2 + 1)) / 2.0;
endd = reloj ();
msecs1 = (((double) (endd – start)) * 1000) / CLOCKS_PER_SEC;
inicio = reloj ();
// para (int j = 0; j <50; ++ j) {
sort (v.begin (), v.end ());
mediana = (v [i / 2] + v [i / 2 – 1]) / 2.0; //}
endd = reloj ();
msecs2 = (((double) (endd – start)) * 1000) / CLOCKS_PER_SEC;
cout << i << "" << msecs1 << "" << msecs2 << "\ n";
fout << msecs1 << "" << msecs2 << "\ n";
}
devuelve 0;
}
El código escrito en R para generar una trama.
require (ggplot2)
analysis <- read.table ('analysis2.txt', header = TRUE)
INPUT_VALUE <- as.vector (seq (1,313))
INPUT_VALUE <- as.data.frame (INPUT_VALUE)
analysis_df <- data.frame (INPUT_VALUE, análisis)
ggplot (analysis_df, aes (INPUT_VALUE, y = value, color = variable)) +
geom_smooth (aes (y = MEIDAN_OF_MEDIAN, col = “MEIDAN_OF_MEDIAN”)) +
geom_smooth (aes (y = REGULAR_SORTING, col = “REGULAR_SORTING”))
La trama se da a continuación:
Input_Size está en una escala de x1000
Con valores de entrada suficientemente menores, tenemos casi el mismo rendimiento, pero tan pronto como las entradas aumentan, la diferencia se ve claramente.
Espero que haya ayudado.
Saludos 🙂
Notas al pie
[1] Teorema maestro (análisis de algoritmos) – Wikipedia
[2] K’th Elemento más pequeño / más grande en matriz sin clasificar | Set 3 (peor tiempo lineal del caso) – GeeksforGeeks
