Articles

¿Qué es la clasificación?


Mejor respuesta

En informática, un algoritmo de clasificación es un algoritmo que coloca los elementos de una lista en un orden determinado. Los órdenes más utilizados son el orden numérico y el orden lexicográfico. La clasificación eficiente es importante para optimizar la eficiencia de otros algoritmos (como los de búsqueda y combinación) que requieren que los datos de entrada estén en listas ordenadas. La clasificación también suele ser útil para canonicalizar datos y producir resultados legibles por humanos. Más formalmente, la salida de cualquier algoritmo de ordenación debe satisfacer dos condiciones:

  • La salida está en orden no decreciente (cada elemento no es más pequeño que el elemento anterior de acuerdo con el orden total deseado);
  • La salida es una permutación (un reordenamiento, pero conservando todos los elementos originales) de la entrada.

Además, los datos de entrada a menudo se almacenan en una matriz, que permite el acceso aleatorio, en lugar de una lista, que solo permite el acceso secuencial; aunque muchos algoritmos se pueden aplicar a cualquier tipo de datos después de una modificación adecuada.

Los algoritmos de clasificación a menudo se denominan una palabra seguida de la palabra «ordenar», y gramaticalmente se usan en inglés como frases nominales, para ejemplo en la oración, «es ineficaz utilizar la ordenación por inserción en listas grandes», la frase ordenación por inserción se refiere al algoritmo de ordenación por inserción por inserción.

Respuesta

Ordenar mil millones de objetos es definitivamente al alcance si puede mantenerlos en la memoria. Necesita comparar O (n log n), ¿verdad? Si no puede, puede ordenar lo que cabe en la memoria de su computadora (o computadoras si tiene un sistema distribuido) y combinar los resultados. En un momento de la década de 1990, una clasificación de combinación modificada tuvo el récord mundial de velocidad, y un super lineal por CPU acelera.

Sin embargo, otra cosa que haces es cuando N crece (o en realidad cuando algo se vuelve lento para entradas razonables) observas más de cerca lo que realmente necesitas.

¿Por qué necesita ordenar los objetos? Si solo está buscando duplicados, ¡hay formas mucho más rápidas! Si desea procesar el 5\% inferior (o superior), hay algoritmos O (n) que pueden particionar en función de la publicación. ordenar la posición!

Cuando las cosas se ponen lentas, miras lo que está haciendo, y antes de averiguar si ese es el algoritmo más rápido, haz lo que sea, averigua si eso es realmente lo correcto. (Excepción: si el «lo que sea» más rápido es un delgado ya depurado que puede simplemente abofetear, entonces puede ser mejor hacer eso … como si lo encontrara Al probar si una matriz contiene algún elemento muchas veces, puede ser más sencillo reemplazar la matriz con un conjunto y ver si ahora es lo suficientemente rápido como para que no te importe que si hicieras otras seis horas de investigación podrías eliminar la mitad de los cheques, o lo que sea).

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *