¿Es posible la ordenación de enteros en O (n) en el modelo transdicotómico?

Que yo sepa, no existe un algoritmo de peor caso que resuelva el siguiente problema: $O(n)$

Dada una secuencia de longitud consiste en enteros finitos, encuentre la permutación donde cada elemento es menor o igual que su sucesor. $n$

¿Pero hay una prueba de que no existe, en el modelo de cómputo transdicotómico ?

Tenga en cuenta que no estoy limitando el rango de los enteros. Tampoco estoy limitando las soluciones a los tipos de comparación.

complexity-theory sorting computation-models lower-bounds orlp
fuente

Hasta donde yo sé, ¡podría haber un algoritmo de tiempo

para SAT! Por tanto, la respuesta es no.

O (n)

$O(n)$

Lembik

AFAIK, esto sigue siendo un problema abierto.

Juho

No sé si puede haber una respuesta significativa hasta que especifique qué modelo de cálculo está utilizando, dado que no está limitando su computadora a comparaciones e intercambios. Con solo RAM y comparaciones de dos números, un argumento de entropía da un límite de tiempo

, incluso para computadoras transdicotómicas. Trivialmente, si en lugar de intercambios y comparaciones, la clasificación es una operación elemental, se puede hacer en

. Si insertar un número entero en el lugar correcto es una operación elemental,

Ω (n \cdot l o g (n))

$\Omega(n\cdot log(n))$

Θ (1)

$\Theta(1)$

Θ (n)

$\Theta(n)$ . ¿Tenía en mente un modelo específico de intercambio más allá de la comparación?

Lieuwe Vinkhuijzen

@LieuweVinkhuijzen Mi pregunta especifica el modelo de cómputo transdicotómico. En inglés simple: un modelo de cómputo donde el tamaño de la palabra de la máquina es lo suficientemente grande como para contener cualquier número entero del problema. Entonces, comparar dos enteros es O (1), pero también lo es sumar, multiplicar, etc. En este modelo de computación, el límite entrópico ya ha sido superado, ver Han, Yijie (2004), "Clasificación determinista en O (n log log n) tiempo y espacio lineal" .

orlp

@orlp ya veo; Si aprovecha la estructura de los enteros, puede superar el límite entrópico. No sabía sobre la clasificación de enteros; ¡Me aseguraré de leer sobre ese tema!

Lieuwe Vinkhuijzen

Respuestas:

Los enteros se pueden clasificar de manera estable en tiempo con espacio adicional. $O(n)$ $O(1)$ Más precisamente, si tiene enteros en el rango , se puede ordenar en tiempo O (n). $n$ $[1, n^c]$

Esto solo se demostró hace un par de años por un equipo que incluía al fallecido Mihai Pătrașcu (lo que no debería sorprender a nadie que esté familiarizado con su trabajo). Es un resultado notable que me sorprende que más personas desconozcan, porque significa que el problema de ordenar enteros está (teóricamente) resuelto.

Existe un algoritmo práctico (dado en el documento anterior) si se le permite modificar claves. Básicamente, puede comprimir enteros ordenados más de lo que puede comprimir enteros no clasificados, y el espacio adicional que gana es exactamente igual a la memoria adicional necesaria para ordenar los radix. También proporcionan un algoritmo poco práctico que admite claves de solo lectura.

Seudónimo
fuente

Por lo que puedo entender del resumen, esto no es general: solo puede ordenar palabras para

de tamaño en

. Mi pregunta menciona explícitamente enteros ilimitados.

\log n

$\log n$

O (n)

$O(n)$

orlp

@orlp El tercer algoritmo en el artículo habla sobre enteros de longitud ilimitada.

Seudónimo

Tal vez lo estoy leyendo mal, pero solo puedo ver una descripción de un método para reducir el uso de memoria de algoritmos de clasificación de enteros ilimitados. Citando del resumen (énfasis mío): "Otra pregunta interesante es el caso de la arbitraria . Aquí presentamos una transformación de recuadro negro de cualquier algoritmo de clasificación RAM a un algoritmo de clasificación que usa solo espacio adicional O (1) y tiene el mismo tiempo de ejecución ". $c$

orlp

Perdóname, pero en su estado actual, esta respuesta no responde a la pregunta en absoluto . Me explícitamente mencionado que los números enteros son no acotadas . Esta respuesta resuelve un problema completamente diferente.

orlp

El punto final ya no está en una fuente pequeña :)

orlp

-1

Para enteros, puede usar la clasificación Radix . Crea cubos y luego ordena una lista de números en donde es un límite superior del tamaño en bits de cualquier número entero, $O(bn)$ $b$ $n$ el número de elementos para ordenar.

Si no hay un límite superior en el tamaño de sus enteros, entonces no creo que haya ningún algoritmo de clasificación de tiempo lineal conocido.

RFC 2549
fuente

¡Bienvenidos! Lo que dices es completamente cierto, pero no creo que responda la pregunta. La pregunta solicita específicamente una prueba de que el algoritmo requerido no existe en un modelo particular de computación; simplemente decir que no se conoce tal algoritmo no prueba que no exista ninguno.

David Richerby

En realidad, siendo b una constante en nuestro problema, considero que este algoritmo está en o (n)

RFC 2549

b

$b$

n

$n$

O (n)

$O(n)$

o (n)

$o(n)$

Sí, definitivamente un error tipográfico;) en su pregunta, como supones que un número encaja en una palabra de longitud b, se convierte en una constante.

RFC 2549

Eso no hace que la longitud de las palabras sea una constante. (De lo contrario, no habría ninguna razón para asumir explícitamente "que las operaciones en palabras individuales toman tiempo constante por operación".