Algoritmo determinista de tiempo lineal para verificar si una matriz es una versión ordenada de la otra

Considere el siguiente problema:

Entrada: dos matrices y de longitud , donde está en orden. $A$ $B$ $n$ $B$

Consulta: ¿ y contienen los mismos elementos (con su multiplicidad)? $A$ $B$

¿Cuál es el algoritmo determinista más rápido para este problema?
¿Se puede resolver más rápido que ordenarlos? ¿Se puede resolver este problema en tiempo lineal determinista?

algorithms reference-request sorting Albert Hendriks
fuente

FWIW el enfoque probabilístico es hashing con una función hash independiente del orden. Carter y Wegman escribieron uno de los documentos originales sobre esto ( sciencedirect.com/science/article/pii/0022000081900337 ), pero no he visto nada en las citas de ese documento que sugiera un algoritmo determinista (hasta ahora).

KWillets

La afirmación que cita es sobre el modelo de máquina de Turing, que es solo de interés teórico. Los algoritmos generalmente se analizan con respecto al modelo de RAM.

Yuval Filmus

Ah, entonces ese es el modelo que estoy buscando. Ajusté la pregunta.

Albert Hendriks

¿Por qué no sumas los elementos de la matriz y luego comparas la suma? Con respecto a su título, es lineal y responde a la pregunta '¿es una matriz la versión ordenada de otra? '. Soy consciente de que no es el modelo de máquina de Turing, sino una solución práctica.

atayenel

@AlbertHendriks Usted (muy probablemente) no puede ordenar una matriz en en una máquina Turing. Algunos límites inferiores en SAT (por ejemplo, cs.cmu.edu/~ryanw/automated-lbs.pdf ) son en realidad para la máquina RAM, perdón por mi comentario anterior engañoso.

O (n \log n)

$O(n\log n)$

Yuval Filmus

Respuestas:

No ha especificado su modelo de cálculo, por lo que asumiré el modelo de comparación.

Considere el caso especial en el que la matriz se toma de la lista En palabras, el ésimo elemento es o . $B$

{1, 2} \times {3, 4} \times \dots \times {2 n - 1, 2 n} .

$\{1,2\} \times \{3,4\} \times \cdots \times \{2n-1,2n\}.$

i

$i$

2 i - 1

$2i-1$

2 i

$2i$

I afirman que si el algoritmo llega a la conclusión de que y contienen los mismos elementos, que el algoritmo ha comparado cada elemento en a su contraparte en . De hecho, se supone que el algoritmo llega a la conclusión de que y contienen los mismos elementos, pero nunca compara el primer elemento de a su contraparte en . Si cambiamos el primer elemento, entonces el algoritmo procedería exactamente de la misma manera, aunque la respuesta sea diferente. Esto demuestra que el algoritmo debe comparar el primer elemento (y cualquier otro elemento) a su contraparte en . $A$ $B$ $B$ $A$ $A$ $B$ $B$ $A$ $A$

Esto significa que si y contienen los mismos elementos, a continuación, después de verificar esta el algoritmo conoce el orden de clasificación de . Por lo tanto, debe tener al menoshojas diferentes, por lo que lleva tiempo . $A$ $B$ $A$ $n!$ $\Omega(n\log n)$

Yuval Filmus
fuente

Pensé que esto implicaría que

en general, pero aparentemente el modelo de comparación es diferente con eso.

P = Ω (n \log n)

$P = \Omega(n\log n)$

Albert Hendriks el

@AlbertHendriks, es el mismo modelo utilizado para mostrar n lg n límite inferior para la clasificación. Significa que si la única operación que puede realizar es la comparación, entonces no puede hacerlo mejor. Creo que esto responde a tu pregunta.

Kaveh

[Cntd] ¡no tenemos límites más fuertes incluso para clasificar! y si puede ordenar más rápido que n lg n, entonces puede usarlo para resolver el problema más rápido que n lg n.

Kaveh

@AlbertHendriks, ¿conoce los algoritmos de tiempo lineal para ordenar enteros? Búscalo en CLRS. Su caso podría ser uno de los casos en que podemos ordenar en tiempo lineal.

Kaveh

Los enteros se pueden ordenar en

(ver nada.kth.se/~snilsson/fast-sorting ), o en el tiempo esperado

O (n \log \log n)

$O(n\log\log n)$

(verieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1181890), o incluso en tiempo lineal si el tamaño de la palabra es lo suficientemente grande (ver LNCS 8503, p. 26ff).

O (n \sqrt{\log \log n})

$O(n\sqrt{\log\log n})$

Yuval Filmus

$O(\log n)$ $O(1)$ $n^{O(1)}$

$a_1,\ldots,a_n$ $b_1,\ldots,b_n$ $1/n$

\prod_{i = 1}^{n} (x - a_{i}) = \prod_{i = 1}^{n} (x - b_{i}) .

$\prod_{i=1}^n (x-a_i) = \prod_{i=1}^n (x-b_i).$

p

$p$

x_{0}

$x_0$

\prod_{i = 1}^{n} (x_{0} - a_{i}) \equiv \prod_{i = 1}^{n} (x_{0} - b_{i}) (\mod p) .

$\prod_{i=1}^n (x_0-a_i) \equiv \prod_{i=1}^n (x_0-b_i) \pmod{p}.$ Si las matrices son iguales, la prueba siempre pasará, así que concentrémonos en los casos en que las matrices son diferentes. En particular, algún coeficiente de no es cero. Como tienen una magnitud , este coeficiente tiene una magnitud , por lo que tiene como máximo primo factores de tamaño . Esto significa que si elegimos un conjunto de al menos primos de tamaño al menos (digamos), entonces para un primo aleatorio de este conjunto se mantendrá con una probabilidad de al menos que

\prod_{i = 1}^{n} (x - a_{i}) - \prod_{i = 1}^{n} (x - b_{i})

$\prod_{i=1}^n (x-a_i) - \prod_{i=1}^n (x-b_i)$

a_{i}, b_{i}

$a_i,b_i$

n^{O (1)}

$n^{O(1)}$

2^{n} n^{O (n)} = n^{O (n)}

$2^n n^{O(n)} = n^{O(n)}$

O (n)

$O(n)$

Ω (n)

$\Omega(n)$

n^{2}

$n^2$

p

$p$

n^{2}

$n^2$

p

$p$

1 - 1 / n

$1-1/n$

\prod_{i = 1}^{n} (x - a_{i}) - \prod_{i = 1}^{n} (x - b_{i}) ≢ 0 (\mod p) .

$\prod_{i=1}^n (x-a_i) - \prod_{i=1}^n (x-b_i) \not\equiv 0 \pmod{p}.$ Un módulo aleatorio será testigo de esto con probabilidad (ya que un polinomio de grado como máximo tiene como máximo raíces).

x_{0}

$x_0$

p

$p$

1 - n / p \geq 1 - 1 / n

$1-n/p \geq 1-1/n$

n

$n$

n

$n$

En conclusión, si elegimos una aleatoria de tamaño aproximadamente entre un conjunto de al menos primos diferentes, y un módulo aleatorio , entonces cuando las matrices no contienen los mismos elementos, nuestra prueba fallará con probabilidad . Ejecutar la prueba lleva tiempo ya que ajusta a un número constante de palabras de máquina. $p$ $n^2$ $n^2$ $x_0$ $p$ $1-O(1/n)$ $O(n)$ $p$

Usando pruebas de primalidad de tiempo polinomial y dado que la densidad de primos de tamaño aproximadamente es , podemos elegir un primo aleatorio en el tiempo . La elección de un módulo aleatorio puede implementarse de varias maneras, y se hace más fácil ya que en nuestro caso no necesitamos un aleatorio completamente uniforme . $n^2$ $\Omega(1/\log n)$ $p$ $(\log n)^{O(1)}$ $x_0$ $p$ $x_0$

En conclusión, nuestro algoritmo se ejecuta en el tiempo , siempre genera SÍ si las matrices contienen los mismos elementos, y genera NO con probabilidad si las matrices no contienen los mismos elementos. Podemos mejorar la probabilidad de error de para cualquier constante . $O(n)$ $1-O(1/n)$ $1-O(1/n^C)$ $C$

Yuval Filmus
fuente

Si bien este algoritmo es aleatorio, explica cómo implementar las ideas en algunas de las otras respuestas para que realmente funcionen. También tiene una ventaja sobre el enfoque de tabla hash: está en su lugar.

Yuval Filmus

Creo que al OP no le gustan los algoritmos probabilísticos ya que no le gustó el algoritmo de tiempo lineal esperado usando una tabla hash.

Kaveh

Kaveh tienes razón. Pero, por supuesto, esta solución también es interesante y debe mantenerse, resuelve el caso de los algoritmos probabilísticos. Además, creo que usa el modelo que estoy buscando.

Albert Hendriks

Me pregunto si la notación O (1 / n) es correcta. Por supuesto, sé lo que quieres decir, pero creo que, según la definición de big-O, esto es equivalente a O (1).

Albert Hendriks el

De ningún modo. Es una cantidad limitada por para suficientemente grande . Esa es una mejor garantía que .

C / n

$C/n$

n

$n$

O (1)

$O(1)$

Yuval Filmus

-3

Propondré otro algoritmo (o al menos un esquema de dicho algoritmo)

El esquema asume que los valores (supuestos " enteros ") están dentro de un rango (¿estrecho?) Entre $[min,max]$

En el tiempo escaneando las dos matrices, podemos encontrar los valores y para ambas y su multiplicidad, si estas difieren, las matrices no son permutaciones entre sí $O(n)$ minmax
Reste el valor minde todos los valores de ambas matrices (aquí no se tiene en cuenta el hecho de que una matriz ya está ordenada, presumiblemente esto se puede mejorar)
Suponga que los valores en las matrices representan masas y aplicamos una aceleración / velocidad a cada uno de magnitud (esto puede mejorarse a una magnitud de en ciertos casos) $1$ $c > 1$
mueva las masas hasta que alcancen el valor máximo max-min, esto tiene una complejidad de . Esto permite encontrar los mismos valores y su multiplicidad, si estos difieren, las matrices no son permutaciones entre sí. De lo contrario, decida que las matrices son permutaciones entre sí. $O((max-min)n)$

tenga en cuenta que el esquema de algoritmo anterior puede ser (determinísticamente) bastante rápido en muchas situaciones prácticas.

El esquema de algoritmo anterior es una variación de un algoritmo de clasificación de tiempo lineal que emplea " masas en movimiento ". La intuición física detrás del algoritmo de clasificación de " masas en movimiento " es la siguiente:

Suponga que el valor de cada elemento representa su magnitud de masa e imagine organizar todos los elementos en una línea y aplicar la misma fuerza de aceleración.

Luego, cada elemento se moverá hasta una distancia relacionada con su masa, más masiva menos distancia y viceversa. Luego, para recuperar los elementos ordenados, simplemente recójalos en orden inverso por la distancia recorrida.

Este algoritmo es de tiempo lineal y determinista , pero existe la advertencia de que la cantidad de fuerza de aceleración inicial y la distancia a recorrer (o el tiempo de espera) está relacionada con la distribución de valores (es decir, las " masas ", el factor anterior). También se puede tratar de discretizar el espacio para que los elementos viajen a una cuadrícula y ganar un factor constante en la velocidad del algoritmo (y usar una rutina de clasificación rápida para ordenar diferentes elementos en la misma celda ). $max-min$

A este respecto, el algoritmo anterior es similar a los algoritmos basados en numéricos de clasificación (por ejemplo radix-tipo , conteo-especie )

Uno puede pensar que este algoritmo podría no significar mucho, pero muestra al menos una cosa. Que, " fundamentalmente ", a nivel físico, clasificar números arbitrarios es una operación de tiempo lineal en el número de elementos.

Nikos M.
fuente

En términos de recopilar los elementos en el orden inverso de la distancia recorrida, ¿eso no se traduciría en comparaciones a nivel de implementación, y en ese punto no tiene que ordenar las "distancias"?

JustAnotherSoul