Algoritmos aleatorios | Conjunto 1 (Introducción y Análisis)

¿Qué es un algoritmo aleatorio?

Un algoritmo que utiliza números aleatorios para decidir qué hacer a continuación en cualquier parte de su lógica se denomina algoritmo aleatorio. Por ejemplo, en Randomized Quick Sort, usamos un número aleatorio para elegir el siguiente pivote (o barajamos aleatoriamente la array). Y en el algoritmo de Karger , elegimos una arista al azar. 

¿Cómo analizar algoritmos aleatorios?

Algunos algoritmos aleatorios tienen una complejidad temporal determinista. Por ejemplo, esta implementación del algoritmo de Karger tiene una complejidad temporal O(E). Dichos algoritmos se denominan Algoritmos de Monte Carlo y son más fáciles de analizar en el peor de los casos. 
Por otro lado, la complejidad temporal de otros algoritmos aleatorios (aparte de Las Vegas) depende del valor de la variable aleatoria. Estos algoritmos aleatorios se denominan algoritmos de Las Vegas.. Estos algoritmos se analizan típicamente para el peor caso esperado. Para calcular el tiempo esperado en el peor de los casos, se deben considerar todos los valores posibles de la variable aleatoria utilizada en el peor de los casos y se debe evaluar el tiempo que toma cada valor posible. El promedio de todos los tiempos evaluados es la complejidad de tiempo esperada en el peor de los casos. Los hechos a continuación son generalmente útiles en el análisis de tales algoritmos. 
Linealidad de la expectativa  
Número esperado de intentos hasta el éxito. 

Por ejemplo, considere a continuación una versión aleatoria de QuickSort. 

Un pivote central es un pivote que divide la array de tal manera que un lado tiene al menos 1/4 elementos. 

// Sorts an array arr[low..high]
randQuickSort(arr[], low, high)

1. If low >= high, then EXIT.

2. While pivot 'x' is not a Central Pivot.
  (i)   Choose uniformly at random a number from [low..high]. 
        Let the randomly picked number number be x.
  (ii)  Count elements in arr[low..high] that are smaller 
        than arr[x]. Let this count be sc.
  (iii) Count elements in arr[low..high] that are greater 
        than arr[x]. Let this count be gc.
  (iv)  Let n = (high-low+1). If sc >= n/4 and
        gc >= n/4, then x is a central pivot.

3. Partition arr[low..high] around the pivot x.

4. // Recur for smaller elements
   randQuickSort(arr, low, sc-1) 

5. // Recur for greater elements
   randQuickSort(arr, high-gc+1, high) 

Lo importante en nuestro análisis es que el tiempo que toma el paso 2 es O(n). 

¿Cuántas veces se ejecuta el bucle while antes de encontrar un pivote central?  
La probabilidad de que el elemento elegido al azar sea pivote central es 1/n. 

Por lo tanto, la cantidad esperada de veces que se ejecuta el ciclo while es n (ver esto para más detalles) 

Por lo tanto, la complejidad temporal esperada del paso 2 es O(n). 

¿Qué es la complejidad temporal general en el peor de los casos?  
En el peor de los casos, cada partición divide la array de manera que un lado tiene n/4 elementos y el otro lado tiene 3n/4 elementos. La altura del árbol de recursividad en el peor de los casos es Log _3/4 n, que es O (Log n). 

T(n) < T(n/4) + T(3n/4) + O(n)
T(n) < 2T(3n/4) + O(n)

Solution of above recurrence is O(n Log n) 

Tenga en cuenta que el algoritmo aleatorio anterior no es la mejor manera de implementar la ordenación rápida aleatoria. La idea aquí es simplificar el análisis, ya que es simple de analizar. 
Por lo general, la ordenación rápida aleatoria se implementa seleccionando aleatoriamente un pivote (sin bucle). O mezclando elementos de array. La complejidad de tiempo esperada en el peor de los casos de este algoritmo también es O (n Log n), pero el análisis es complejo, el propio profesor del MIT menciona lo mismo en su conferencia aquí . 

Algoritmos aleatorios | Conjunto 2 (Clasificación y Aplicaciones) 

Referencias:  
http://www.tcs.tifr.res.in/~workshop/nitrkl_igga/randomized-lecture.pdf 

Este artículo es una contribución de Ashish Sharma . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.