algorithm - verbo - ¿Ordenar en tiempo lineal?

tag questions estructura

Question

Dado un conjunto de entrada de n enteros en el rango [0..n ^ 3-1], proporcione un algoritmo de clasificación de tiempo lineal.

Esta es una revisión de mi prueba el jueves, y no tengo idea de cómo abordar este problema.

Answer 1

Cuando las personas dicen "algoritmo de clasificación", a menudo se refieren al "algoritmo de clasificación de comparación", que es cualquier algoritmo que solo depende de poder preguntar "¿es esto más grande o más pequeño que eso?". Entonces, si se limita a hacer esta única pregunta sobre los datos, nunca obtendrá más que n * log (n) (esto es el resultado de hacer una búsqueda de log (n) de los n ordenamientos posibles factoriales de un conjunto de datos) .

Si puede escapar a las restricciones del "tipo de comparación" y hacer una pregunta más sofisticada sobre un dato, por ejemplo, "¿cuál es la base de 10 radix de estos datos?", Entonces puede encontrar cualquier número de algoritmos de ordenación de tiempo lineal, simplemente toman más memoria.

Este es un intercambio de espacio de tiempo. La ordenación de Comparason toma poco o nada de ram y se ejecuta en tiempo N * log (n). la ordenación de radix (por ejemplo) se ejecuta en la memoria O (n) time AND O (log (radix)).

Answer 2

Echa un vistazo a la clasificación de radix .

Answer 3

Es realmente simple, si n = 2 y los números son únicos:

• Construya una matriz de bits (2 ^ 31-1 bits => ~ 256MB). Inicialízalos a cero.
• Lea la entrada, para cada valor que vea establecer el bit respectivo en la matriz en 1.
• Escanee la matriz, para cada bit configurado, genere el valor respectivo.

Complejidad => O (2n)

De lo contrario, use Radix Sort:

Complejidad => O (kn) (con suerte)

Answer 4

Piensa en los números como números de tres dígitos donde cada dígito va de 0 a n-1. Ordene estos números con el tipo de raíz. Para cada dígito hay una llamada al recuento de ordenación que está tomando el tiempo Theta (n + n), de modo que el tiempo total de ejecución corresponde a Theta (n).

Answer 5

También eche un vistazo a los géneros relacionados también: tipo de ordenamiento encasillado o tipo de conteo , así como clasificación de radix como lo menciona Pukku.

Answer 6

Un conjunto de un rango limitado de números se puede representar mediante un mapa de bits de RANGE bits. En este caso, un mapa de bits de 500 mb, por lo que para cualquier cosa que no sean listas enormes, estarás mejor con Radix Sort. A medida que encuentre el número k, configure el mapa de bits [k] = 1. Lista de recorrido transversal único, O (N).

Answer 7

al igual algo es posible:

M;// unsorted array
lngth; //number items of M
for(int i=0; i < lngth; i++)sorted[M[i]];

Solo es posible algo para la complejidad lineal, pero tiene complejidad O (k * N) por ram (N - elementos de matriz de números, k - elemento de len)

Answer 8

wikipedia muestra bastantes algoritmos de clasificación diferentes y sus complejidades. es posible que desee comprobarlos