algorithm - sacar - Encontrar la mediana de una matriz no ordenada

media mediana y moda para datos no agrupados

Question

Para encontrar la mediana de una matriz no ordenada, podemos hacer una acumulación mínima en el tiempo O (nlogn) para n elementos, y luego podemos extraer uno por uno n / 2 elementos para obtener la mediana. Pero este enfoque tomaría el tiempo O (nlogn).

¿Podemos hacer lo mismo por algún método en O (n) tiempo? Si podemos, entonces dígale o sugiera algún método.

Answer 1

Como dice wikipedia, Median-of-Medians es teóricamente o (N), pero no se usa en la práctica porque la sobrecarga de encontrar "buenos" pivotes lo hace demasiado lento.
Quickselect

Aquí está la fuente de Java para un algoritmo Quickselect para encontrar el elemento k''th en una matriz:

/**
 * Returns position of k''th largest element of sub-list.
 * 
 * @param list list to search, whose sub-list may be shuffled before
 *            returning
 * @param lo first element of sub-list in list
 * @param hi just after last element of sub-list in list
 * @param k
 * @return position of k''th largest element of (possibly shuffled) sub-list.
 */
static int select(double[] list, int lo, int hi, int k) {
    int n = hi - lo;
    if (n < 2)
        return lo;

    double pivot = list[lo + (k * 7919) % n]; // Pick a random pivot

    // Triage list to [<pivot][=pivot][>pivot]
    int nLess = 0, nSame = 0, nMore = 0;
    int lo3 = lo;
    int hi3 = hi;
    while (lo3 < hi3) {
        double e = list[lo3];
        int cmp = compare(e, pivot);
        if (cmp < 0) {
            nLess++;
            lo3++;
        } else if (cmp > 0) {
            swap(list, lo3, --hi3);
            if (nSame > 0)
                swap(list, hi3, hi3 + nSame);
            nMore++;
        } else {
            nSame++;
            swap(list, lo3, --hi3);
        }
    }
    assert (nSame > 0);
    assert (nLess + nSame + nMore == n);
    assert (list[lo + nLess] == pivot);
    assert (list[hi - nMore - 1] == pivot);
    if (k >= n - nMore)
        return select(list, hi - nMore, hi, k - nLess - nSame);
    else if (k < nLess)
        return select(list, lo, lo + nLess, k);
    return lo + k;
}

No he incluido el origen de los métodos de comparación y canje, por lo que es fácil cambiar el código para que funcione con Object [] en lugar de double [].

En la práctica, puede esperar que el código anterior sea o (N).

Answer 2

Puede usar el algoritmo Median of Medians para encontrar la mediana de una matriz no ordenada en tiempo lineal.

Answer 3

Se puede hacer usando el algoritmo Quickselect en O (n), consulte las estadísticas de orden Kth (algoritmos aleatorizados).

Answer 4

Ya he votado la respuesta @dasblinkenlight ya que el algoritmo Median of Medians resuelve este problema en el tiempo O (n). Solo quiero agregar que este problema podría resolverse en O (n) tiempo usando montones también. La creación de un montón se puede hacer en el tiempo O (n) mediante el uso de abajo hacia arriba. Eche un vistazo al siguiente artículo para una explicación detallada Tipo de montón

Supongamos que su matriz tiene N elementos, tiene que construir dos montones: Un MaxHeap que contiene los primeros N / 2 elementos (o (N / 2) +1 si N es impar) y un MinHeap que contiene los elementos restantes. Si N es impar, entonces su mediana es el elemento máximo de MaxHeap (O (1) al obtener el máximo). Si N es par, entonces su mediana es (MaxHeap.max () + MinHeap.min ()) / 2, esto también toma O (1). Por lo tanto, el costo real de toda la operación es la operación de construcción de montones que es O (n).

Por cierto, este algoritmo MaxHeap / MinHeap también funciona cuando no se conoce previamente el número de elementos de la matriz (si tiene que resolver el mismo problema para una secuencia de enteros, por ejemplo). Puede ver más detalles sobre cómo resolver este problema en el siguiente artículo Median Of integer streams

Answer 5

Quickselect funciona en O (n), esto también se usa en el paso de partición de Quicksort.

Answer 6

El algoritmo de selección rápida puede encontrar el k-ésimo elemento más pequeño de una matriz en tiempo de ejecución lineal ( O(n) ). Aquí hay una implementación en python:

import random

def partition(L, v):
    smaller = []
    bigger = []
    for val in L:
        if val < v: smaller += [val]
        if val > v: bigger += [val]
    return (smaller, [v], bigger)

def top_k(L, k):
    v = L[random.randrange(len(L))]
    (left, middle, right) = partition(L, v)
    # middle used below (in place of [v]) for clarity
    if len(left) == k:   return left
    if len(left)+1 == k: return left + middle
    if len(left) > k:    return top_k(left, k)
    return left + middle + top_k(right, k - len(left) - len(middle))

def median(L):
    n = len(L)
    l = top_k(L, n / 2 + 1)
    return max(l)