La clasificación es crítica para muchas tareas. Señalaré solo algunos, pero son característicos del tipo de cosas para las que utiliza la clasificación.
Ejemplo 1: dado un conjunto de un millón de registros de datos, elimine o combine los duplicados.
Si los registros de datos se ordenan según el criterio de unicidad principal, la eliminación de los duplicados se puede hacer fácilmente recorriendo la lista y encontrando grupos de registros consecutivos que se comparan igual usando ese criterio.
- ¿Cómo se debe describir y hablar sobre la recursividad cuando se hace pizarra o se programa un par?
- Cómo averiguar si existen dos elementos en una matriz ordenada cuya suma es igual a algún número predefinido
- Cómo evitar los caracteres repetitivos de una cadena
- ¿Cómo podría encontrar la métrica correcta que se utilizará para los vecinos más cercanos u otros algoritmos basados en similitudes?
- ¿Por qué Lua está diseñado de tal manera que obtener el tamaño de una tabla es O (n) en el tamaño de la tabla?
Ejemplo 2: Compare dos grandes conjuntos de elementos y descubra en qué difieren.
Probemos esto a mano. Aquí hay dos listas ordenadas al azar de 15 números:
3 16 13 9 15 12 2 10 14 8 7 1 6 4 11
14 1 5 6 13 12 3 11 15 4 7 8 10 2 16
¿Me puede decir qué número de la lista 1 falta en la lista 2 y viceversa? Bastante difícil, ¿eh? Y eso con solo 15 números.
Ahora, intentemos de nuevo. Aquí tenemos las mismas dos listas en orden:
1 2 3 4 6 7 8 9 10 11 12 13 14 15 16
1 2 3 4 5 6 7 8 10 11 12 13 14 15 16
No es difícil repasar las listas en paralelo y seleccionar las diferencias, ¿verdad? Lo mismo es cierto para un programa de computadora. Usando la notación big-O, comparar cada elemento de una lista con cada elemento de otra lista es una operación O ([matemática] n ^ 2 [/ matemática]) mientras que comparar las listas ordenadas es una operación O (n). Eso significa que el costo de comparar las listas sin ordenar aumenta con el cuadrado del número de elementos, mientras que el costo de comparar las listas ordenadas crece linealmente. Piensa en lo que eso significa cuando consideras una lista de un millón de elementos. Las mismas fórmulas big-O se aplican al Ejemplo 1.
Ejemplo 3: Utilizando las mismas listas que en el Ejemplo 2, averigüe si el número 5 aparece en cada lista. Para las listas no ordenadas, debe mirar cada elemento hasta que encuentre el 5 o llegue al final de la lista. En promedio, para una lista de n elementos, se necesitarán comparaciones [matemáticas] n / 2 [/ matemáticas] para encontrar lo que está buscando si existe y n comparaciones si no existe. Sin embargo, con la lista ordenada, puede usar la búsqueda binaria: mire el elemento del medio, si es más de 5, siga buscando en la primera mitad de la lista; si es menos de 5, sigue buscando en la segunda mitad de la lista; sigue dividiendo la lista por la mitad hasta que la encuentres o no te quede nada. Al usar la búsqueda binaria, se garantiza que encontrará su respuesta o fallará en las comparaciones [math] log2 (n) [/ math] (4 comparaciones como máximo para nuestra lista de 15 elementos). La próxima vez que use un diccionario (en papel), considere lo difícil que sería usarlo si las palabras no estuvieran ordenadas alfabéticamente.
Por supuesto, para obtener estos beneficios de rendimiento, debe pagar el costo de ordenar la lista, que generalmente es [matemática] O (n * log (n)) [/ matemática], aunque algunos algoritmos de clasificación son más rápidos para ciertos tipos de datos Sin embargo, es muy común construir listas y reutilizarlas con frecuencia, sin cambios. En ese caso, paga el costo de ordenar solo una vez (u ocasionalmente), pero obtiene los beneficios una y otra vez.
