Encontrar el valor mediano de un conjunto creciente

Question

Me encontré con una pregunta de algoritmo interesante en una entrevista. Di mi respuesta, pero no estoy seguro de si hay alguna idea mejor. Así que doy la bienvenida a todos para que escriban algo sobre sus ideas.

Tiene un juego vacío. Ahora los elementos se ponen en el conjunto uno por uno. Suponemos que todos los elementos son enteros y son distintos (de acuerdo con la definición de conjunto, no consideramos dos elementos con el mismo valor).

Cada vez que se agrega un nuevo elemento al conjunto, se solicita el valor mediano del conjunto. El valor mediano se define igual que en matemáticas: el elemento medio en una lista ordenada. Aquí, especialmente, cuando el tamaño del conjunto es par, asumiendo el tamaño del conjunto = 2 * x, el elemento mediano es el elemento x-ésimo del conjunto.

Un ejemplo: Comience con un conjunto vacío, cuando se añade 12, la mediana es 12, cuando se añade 7, la mediana es 7, cuando 8 se añade, la mediana es 8, cuando 11 se añade, la mediana es 8, cuando se añade 5, la mediana es 8, cuando se añade 16, la mediana es 8, ...

en cuenta que, primero, se añaden elementos de ajustar de uno en uno y segundo, no sabemos los elementos que van a agregarse.

Mi respuesta.

Dado que se trata de encontrar una mediana, es necesario ordenarla. La solución más fácil es usar una matriz normal y mantener ordenada la matriz. Cuando aparece un elemento nuevo, use la búsqueda binaria para encontrar la posición del elemento (log_n) y agregue el elemento a la matriz. Como es una matriz normal, se necesita cambiar el resto de la matriz, cuya complejidad de tiempo es n. Cuando se inserta el elemento, podemos obtener inmediatamente la mediana, utilizando el tiempo de la instancia.

La complejidad del tiempo es peor: log_n + n + 1.

Otra solución es utilizar la lista de enlaces. La razón para usar la lista de enlaces es eliminar la necesidad de cambiar la matriz. Pero encontrar la ubicación del nuevo elemento requiere una búsqueda lineal. Agregar el elemento toma tiempo instantáneo y luego tenemos que encontrar la mediana pasando por la mitad de la matriz, que siempre lleva n/2 veces.

La PEOR complejidad del tiempo es: n + 1 + n/2.

La tercera solución es utilizar un árbol de búsqueda binario. Usando un árbol, evitamos cambiar la matriz. Pero usar el árbol de búsqueda binaria para encontrar la mediana no es muy atractivo. Por lo tanto, cambio el árbol de búsqueda binaria de forma que siempre sea el caso de que el subárbol izquierdo y el subárbol derecho estén equilibrados. Esto significa que, en cualquier momento, el subárbol izquierdo y el subárbol derecho tienen el mismo número de nodos o el subárbol derecho tiene un nodo más que en el subárbol izquierdo. En otras palabras, se garantiza que en cualquier momento, el elemento raíz sea la mediana. Por supuesto, esto requiere cambios en la forma en que se construye el árbol. El detalle técnico es similar a la rotación de un árbol rojo-negro.

Si el árbol se mantiene correctamente, se garantiza que la PEOR complejidad del tiempo sea O (n).

De modo que los tres algoritmos son todos lineales al tamaño del conjunto. Si no existe un algoritmo sublineal, los tres algoritmos pueden considerarse las soluciones óptimas. Como no difieren mucho entre sí, la mejor es la más fácil de implementar, que es la segunda, mediante la lista de enlaces.

Entonces, lo que realmente me pregunto es si habrá un algoritmo sublineal para este problema y, de ser así, cómo será. Alguna idea chicos?

Steve.

Answer 1

Su análisis de complejidad es confuso. Digamos que se agregan n ítems en total; queremos generar la corriente de n medianas (donde el i-ésimo en la secuencia es la mediana de los primeros i elementos) de manera eficiente.

Creo que esto se puede hacer en O (n * lg n) tiempo utilizando dos colas de prioridad (por ejemplo, montón binario o fibonacci); una cola para los elementos por debajo de la mediana actual (por lo que el elemento más grande está en la parte superior) y la otra para los elementos que están encima (en este montón, el más pequeño está en la parte inferior). Tenga en cuenta que en los montones de fibonacci (y otros), la inserción es O (1) amortizada; solo aparece un elemento que es O (lg n).

Esto se denominaría un algoritmo de "selección de mediana en línea", aunque Wikipedia solo habla de la selección min/max en línea. He aquí un approximate algorithm, y una lower bound en la selección de la mediana en línea determinista y aproximada (algoritmo de un medio de límite inferior no más rápido es posible!)

Si hay un pequeño número de valores posibles en comparación con n, es probable que puede romper la comparación- límite inferior basado como puede para ordenar.

Answer 2

Para encontrar la mediana en tiempo lineal puedes probar esto (me vino a la mente). Necesita almacenar algunos valores cada vez que agrega un número a su conjunto, y no necesitará clasificación. Aquí va.

typedef struct 
{ 
     int number; 
     int lesser; 
     int greater; 
} record; 

int median(record numbers[], int count, int n) 
{ 
     int i; 
     int m = VERY_BIG_NUMBER; 

     int a, b; 

     numbers[count + 1].number = n: 
     for (i = 0; i < count + 1; i++) 
     { 
       if (n < numbers[i].number) 
       { 
         numbers[i].lesser++; 
         numbers[count + 1].greater++; 
       } 
       else 
       { 
         numbers[i].greater++; 
         numbers[count + 1].lesser++; 
       } 
       if (numbers[i].greater - numbers[i].lesser == 0) 
         m = numbers[i].number; 
     } 

     if (m == VERY_BIG_NUMBER) 
     for (i = 0; i < count + 1; i++) 
     { 
       if (numbers[i].greater - numbers[i].lesser == -1) 
         a = numbers[i].number; 
       if (numbers[i].greater - numbers[i].lesser == 1) 
         b = numbers[i].number; 

       m = (a + b)/2; 
     } 

     return m; 
} 

Lo que esto hace es, cada vez que se agrega un número para el conjunto, ahora debe cuántos "menor que el número" números tienen, y el número de "mayor que su número de" números tienen. Por lo tanto, si tiene un número con el mismo "menor que" y "mayor que", significa que su número se encuentra en el medio del conjunto, sin tener que ordenarlo. En el caso de que tenga una cantidad par de números, puede tener dos opciones para una mediana, por lo que solo devuelve la media de esos dos. Por cierto, este es el código C, espero que esto ayude.

Answer 3

Aunque wrang-wrang ya respondió, deseo describir una modificación de su método de árbol de búsqueda binaria que es sub-lineal.

• Usamos un árbol de búsqueda binaria que es equilibrado (AVL/Rojo-Negro/etc), pero no súper equilibrado como usted describió. Entonces, agregar un ítem es O (log n)
• Una modificación al árbol: para cada nodo también almacenamos el número de nodos en su subárbol. Esto no cambia la complejidad. (Para una hoja de este conteo sería 1, para un nodo con dos hijos de hoja esto sería 3, etc)

Ahora podemos acceder al elemento más pequeño Kth en O (log n) el uso de estas razones:

def get_kth_item(subtree, k): 
    left_size = 0 if subtree.left is None else subtree.left.size 
    if k < left_size: 
    return get_kth_item(subtree.left, k) 
    elif k == left_size: 
    return subtree.value 
    else: # k > left_size 
    return get_kth_item(subtree.right, k-1-left_size) 

Una mediana es un caso especial de K-ésimo elemento más pequeño (dado que conoce el tamaño del conjunto).

Así que, en general, es otra solución O (log n).

Answer 4

Recibí la misma pregunta de la entrevista y se me ocurrió la solución de dos montones en la publicación de wrang-wrang. Como él dice, el tiempo por operación es O (log n) en el peor de los casos.El tiempo esperado también es O (log n) porque tiene que "mostrar un elemento" 1/4 del tiempo asumiendo entradas aleatorias.

Posteriormente lo pensé más y descubrí cómo obtener el tiempo esperado constante; de hecho, el número esperado de comparaciones por elemento se convierte en 2 + o (1). Puedes ver mi informe al http://denenberg.com/omf.pdf.

Por cierto, las soluciones discutidas aquí requieren espacio O (n), ya que debe guardar todos los elementos. Un enfoque completamente diferente, que requiere solo espacio O (log n), le da una aproximación a la mediana (no a la mediana exacta). Lo siento, no puedo publicar un enlace (estoy limitado a un enlace por publicación) pero mi artículo tiene punteros.

Answer 5

1) Al igual que con las sugerencias anteriores, mantenga dos montones y guarde en caché sus respectivos tamaños. El montón izquierdo mantiene los valores por debajo de la mediana, el montón derecho mantiene los valores por encima de la mediana. Si simplemente niega los valores en el montón correcto, el valor más pequeño estará en la raíz, por lo que no es necesario crear una estructura de datos especial.

2) Cuando agrega un número nuevo, determina la nueva mediana a partir del tamaño de sus dos montones, la mediana actual y las dos raíces de los montones L & R, lo cual solo lleva tiempo constante.

3) Llame a un método de rosca privado para realizar el trabajo real para realizar la inserción y la actualización, pero regrese inmediatamente con el nuevo valor de la mediana. Solo necesita bloquear hasta que se actualicen las raíces del montón. Entonces, el hilo que hace la inserción solo necesita mantener un bloqueo en el nodo abuelo transversal a medida que atraviesa el árbol; esto implicará que puede insertar y reequilibrar sin bloquear otros hilos de inserción que trabajan en otras ramas secundarias.

Obtención de la mediana se convierte en un procedimiento de tiempo constante, por supuesto, ahora es posible que tenga que esperar la sincronización de más agrega.

Rob

Answer 6

Un árbol de equilibrado (por ejemplo, árbol R/B) con aumentada campo tamaño deben encontrar la mediana en el tiempo lg (n) en el peor caso. Creo que está en el Capítulo 14 del clásico libro de texto Algorithm.

Answer 7

Podemos distinguir un montón mínimo y máximo para almacenar números. Además, definimos una clase DynamicArray para el conjunto de números, con dos funciones: Insertar y Getmedian. El tiempo para insertar un nuevo número es O (lgn), mientras que el tiempo para obtener la mediana es O (1).

Esta solución se implementa en C++ como el siguiente:

template<typename T> class DynamicArray 
{ 
public: 
    void Insert(T num) 
    { 
     if(((minHeap.size() + maxHeap.size()) & 1) == 0) 
     { 
      if(maxHeap.size() > 0 && num < maxHeap[0]) 
      { 
       maxHeap.push_back(num); 
       push_heap(maxHeap.begin(), maxHeap.end(), less<T>()); 

       num = maxHeap[0]; 

       pop_heap(maxHeap.begin(), maxHeap.end(), less<T>()); 
       maxHeap.pop_back(); 
      } 

      minHeap.push_back(num); 
      push_heap(minHeap.begin(), minHeap.end(), greater<T>()); 
     } 
     else 
     { 
      if(minHeap.size() > 0 && minHeap[0] < num) 
      { 
       minHeap.push_back(num); 
       push_heap(minHeap.begin(), minHeap.end(), greater<T>()); 

       num = minHeap[0]; 

       pop_heap(minHeap.begin(), minHeap.end(), greater<T>()); 
       minHeap.pop_back(); 
      } 

      maxHeap.push_back(num); 
      push_heap(maxHeap.begin(), maxHeap.end(), less<T>()); 
     } 
    } 

    int GetMedian() 
    { 
     int size = minHeap.size() + maxHeap.size(); 
     if(size == 0) 
      throw exception("No numbers are available"); 

     T median = 0; 
     if(size & 1 == 1) 
      median = minHeap[0]; 
     else 
      median = (minHeap[0] + maxHeap[0])/2; 

     return median; 
    } 

private: 
    vector<T> minHeap; 
    vector<T> maxHeap; 
}; 

Para un análisis más detallado, por favor refiérase a mi blog: http://codercareer.blogspot.com/2012/01/no-30-median-in-stream.html.

Answer 8

Para mantener la explicación breve, puede aumentar de manera eficiente una BST para seleccionar una clave de un rango especificado en O (h) haciendo que cada nodo almacene el número de nodos en su subárbol izquierdo. Si puede garantizar que el árbol está equilibrado, puede reducirlo a O (log (n)). Considere el uso de una AVL que tiene un equilibrio de altura (o un árbol rojo-negro que está aproximadamente balanceado), luego puede seleccionar cualquier tecla en O (log (n)). Cuando inserta o elimina un nodo en la AVL, puede aumentar o disminuir una variable que realiza un seguimiento del número total de nodos en el árbol para determinar el rango de la mediana que puede seleccionar en O (log (n)).