Algoritmos aleatorios | Conjunto 3 (1/2 mediana aproximada)

Recomendamos encarecidamente consultar los siguientes artículos como requisito previo para ello.

Algoritmos aleatorios | Conjunto 1 (Introducción y Análisis)
Algoritmos Aleatorizados | Conjunto 2 (Clasificación y Aplicaciones)

En esta publicación, se analiza un algoritmo de Monte Carlo.

Declaración del problema: Dada una array no ordenada A[] de n números y ε > 0, calcule un elemento cuyo rango (posición en A[] ordenado) esté en el rango [(1 – ε)n/2, (1 + ε) n/2].
Para ½ Algoritmo mediano aproximado &epsilom; es 1/2 => el rango debe estar en el rango [n/4, 3n/4]

Podemos encontrar el k-ésimo elemento más pequeño en O(n) tiempo esperado y O(n) tiempo en el peor de los casos .

¿Qué pasa si queremos en menos de O (n) tiempo con un error probable bajo permitido?
Los siguientes pasos representan un algoritmo que es O((Log n) x (Log Log n)) tiempo y produce un resultado incorrecto con probabilidad menor o igual a 2/n ² .

1. Elija aleatoriamente k elementos de la array donde k = c log n (c es una constante)
2. Inserte luego en un conjunto.
3. Ordenar elementos del conjunto.
4. Devuelve la mediana del conjunto, es decir, (k/2) elemento del conjunto

C

/* C++ program to find Approximate Median using    1/2 Approximate Algorithm */ #include<bits/stdc++.h> using namespace std;    // This function returns the Approximate Median int randApproxMedian(int arr[],int n) {     // Declaration for the random number generator     random_device rand_dev;     mt19937 generator(rand_dev());        // Random number generated will be in the range [0,n-1]     uniform_int_distribution<int> distribution(0, n-1);        if (n==0)         return 0;        int k = 10*log2(n); // Taking c as 10        // A set stores unique elements in sorted order     set<int> s;     for (int i=0; i<k; i++)     {         // Generating a random index         int index = distribution(generator);            //Inserting into the set         s.insert(arr[index]);     }        set<int> ::iterator itr = s.begin();        // Report the median of the set at k/2 position     // Move the itr to k/2th position     advance(itr, (s.size()/2) - 1);        // Return the median     return *itr; }    // Driver method to test above method int main() {     int arr[] = {1, 3, 2, 4, 5, 6, 8, 7};     int n = sizeof(arr)/sizeof(int);     printf("Approximate Median is %d\n",randApproxMedian(arr,n));     return 0 }

Java

/* Java program to find Approximate Median using    1/2 Approximate Algorithm */ import java.util.Iterator; import java.util.Random; import java.util.TreeSet;       class Test {     static int arr[] = new int[]{1, 3, 2, 4, 5, 6, 8, 7} ;            // This function returns the Approximate Median     static int randApproxMedian(int n)     {         // Declaration for the random number          Random r = new Random();                    if (n==0)             return 0;                    double k1 = 10*Math.log(n); // Taking c as 10                 int k = (int)k1;                    // A treeset stores unique elements in sorted order         TreeSet s = new TreeSet<Integer>();         for (int i=0; i<k; i++)         {             // Generating a random index             // Random number generated will be in the range [0,n-1]             int index = r.nextInt(n);                     //Inserting into the set             s.add(arr[index]);         }                 Iterator<Integer> itr = s.iterator();                    int temp = s.size()/2 - 1;                    for (int i = 0; i < temp; i++) {             itr.next();         }                 // Return the median         return itr.next();     }         // Driver method to test the above function     public static void main(String[] args) {                System.out.println("Approximate Median is " + randApproxMedian(arr.length));            } }

Producción:

Approximate Median is 4

Complejidad de tiempo:
Usamos un conjunto proporcionado por STL en C++. En STL Set, la inserción de cada elemento toma O (log k). Entonces, para k inserciones, el tiempo necesario es O (k log k).
Ahora reemplazando k con c log n
=>O(c log n (log (clog n))) =>O (log n (log log n))

¿Cómo es la probabilidad de error menor que 2/n ² ?
El algoritmo comete un error si el conjunto S tiene al menos k/2 elementos del Cuarto Izquierdo o del Cuarto Derecho.


Es bastante fácil visualizar esta declaración ya que la mediana que reportamos será (k/2)-ésimo elemento y si tomamos k/2 elementos del cuarto izquierdo (o cuarto derecho) la mediana será del cuarto izquierdo (o el cuarto derecho).

Una array se puede dividir en 4 cuartos cada uno de tamaño n/4. Entonces P (seleccionando el cuarto izquierdo) es 1/4. Entonces, ¿cuál es la probabilidad de que al menos k/2 elementos sean del Cuarto Izquierdo o del Cuarto Derecho? Este problema de probabilidad es el mismo que se muestra a continuación:

Dada una moneda que da CARA con probabilidad de 1/4 y cruz con 3/4. La moneda se lanza k veces. ¿Cuál es la probabilidad de que obtengamos al menos k/2 CABEZAS es menor o igual a?

Explicación:

If we put k = c log n for c = 10, we get 
P <= (1/2)2log n
P <= (1/2)log n2
P <= n-2

Probabilidad de seleccionar al menos k/2 elementos del cuarto izquierdo) <= 1/n ²
Probabilidad de seleccionar al menos k/2 elementos del cuarto izquierdo o derecho) <= 2/n ²

Por lo tanto, el algoritmo produce un resultado incorrecto con probabilidad menor o igual a 2/n ² .


Referencias: www.cse.iitk.ac.in/users/sbaswana/CS648/Lecture-2-CS648.pptx

Este artículo es una contribución de Chirag Agarwal . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo electrónico a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.