No estoy de acuerdo con otras respuestas. O (n.log (n)) es solo un límite estricto para las clasificaciones in situ y la clasificación de datos de entrada con propiedades de dispersión desconocidas.
Pero si las condiciones son correctas, puede usar, por ejemplo, la clasificación Radix (también conocida como clasificación postal por código postal) para clasificarlas con un costo muy cercano a O (n) .
Acabo de dar la idea (en realidad estoy describiendo la primera etapa de la ordenación relacionada pero más simple de Bucket sort). Imagine que cada palabra comienza con una letra diferente y tiene tantas palabras como letras en el alfabeto, solo leer la palabra una vez permitirá colocarla en el lugar correcto. Por supuesto, esta idea también funciona si tomamos las primeras dos o tres letras en lugar de solo la primera.
- ¿Cuál es la diferencia entre la recursión normal y la recursiva de la cola con ejemplos?
- ¿Cómo es posible que el hashing sea imposible de revertir? ¿Hay alguna prueba?
- ¿Qué algoritmo se usa para escanear?
- Cómo aprender algoritmos y estructuras de datos como estudiante de secundaria
- ¿Cómo se usa la programación dinámica para resolver la pregunta Problema TRT (Trato para las vacas) en Sphere Online Judge (SPOJ)?
Si B es el número de cubos y tiene una buena dispersión de los datos de entrada, la complejidad del tipo se convierte en O (B + n log (n / B)) (esto se debe a que si varias palabras chocan en el mismo segmento, aún deben ser ordenado).
Para fines prácticos, la parte log (n / B) puede verse como una pequeña constante si sabemos que los datos tienen buenas propiedades de dispersión. Por supuesto, la complejidad ahora depende de la longitud promedio de los datos de entrada. Es muy eficiente para conjuntos de datos pequeños (incluso mejor si tiene muchas palabras de entrada idénticas), menos eficiente para palabras más largas.
¿Por qué ordenar por correo? Porque la idea es exactamente la que usan las oficinas de correos cuando clasifican por código postal.
Otra opción podría ser usar un algoritmo de ordenamiento paralelo. Al hacerlo, incluso puede obtener una complejidad de clasificación mejor que O (n) , generalmente O (n / p. Log (n)) donde p es el número de procesadores disponibles. Pero también se le debe advertir que dicho algoritmo también suele tener un alto costo constante y que la complejidad no lo es todo.
