algorithm - keywords - meta tags seo 2018

¿La partición es más fácil que la clasificación? (8)

El tiempo requerido para realizar una partición posiblemente imperfecta utilizando una función hash será O (n + bucketcount) [no O (n * bucketcount)]. Hacer que el conteo de cubos sea lo suficientemente grande como para evitar todas las colisiones será costoso, pero si la función hash funciona bien, debería haber un pequeño número de valores distintos en cada cucharón. Si uno puede generar fácilmente múltiples funciones hash estadísticamente independientes, uno podría tomar cada grupo cuyas teclas no coinciden con la primera y usar otra función hash para particionar el contenido de ese grupo.

Suponiendo un número constante de grupos en cada paso, el tiempo será O (NlgN), pero si uno establece el número de grupos en algo como sqrt (N), el número promedio de pases debería ser O (1) y el Trabajar en cada pasada O (n).

Esta es una pregunta que ha estado pensando en mi mente por algún tiempo ...

Supongamos que tengo una lista de elementos y una relación de equivalencia en ellos, y la comparación de dos elementos lleva tiempo constante. Quiero devolver una partición de los elementos, por ejemplo, una lista de listas vinculadas, cada una de las cuales contiene todos los elementos equivalentes.

Una forma de hacerlo es extender la equivalencia a una ordenación de los artículos y ordenarlos (con un algoritmo de clasificación); entonces todos los elementos equivalentes serán adyacentes.

¿Pero se puede hacer de manera más eficiente que con la clasificación? ¿La complejidad del tiempo de este problema es menor que la de la clasificación? ¿Si no, porque no?

Este es un problema clásico en las estructuras de datos, y sí, es más fácil que la clasificación. Si desea también poder buscar rápidamente a qué conjunto pertenece cada elemento, lo que desea es la estructura de datos de conjunto disjunto, junto con la operación de búsqueda de unión. Vea aquí: http://en.wikipedia.org/wiki/Disjoint-set_data_structure

La clasificación basada en la comparación generalmente tiene un límite inferior de O (n log n).

Suponga que recorre su conjunto de elementos y colóquelos en grupos con elementos con el mismo valor comparativo, por ejemplo, en un conjunto de listas (por ejemplo, utilizando un conjunto de hash). Esta operación es claramente O (n), incluso después de recuperar la lista de listas del conjunto.

--- EDITAR: ---

Esto por supuesto requiere dos suposiciones:

Existe un algoritmo hash de tiempo constante para cada elemento a particionar.
El número de cubos no depende de la cantidad de entrada.

Por lo tanto, el límite inferior de partición es O (n).

La partición es más rápida que la clasificación, en general, debido a que no tiene que comparar cada elemento con cada elemento potencialmente clasificado ya clasificado, solo tiene que compararlo con las claves ya establecidas de su partición. Eche un vistazo de cerca a la RadixSort . El primer paso de la clasificación de radix es particionar la entrada en función de alguna parte de la clave. La clasificación por radix es O (kN). Si su conjunto de datos tiene claves delimitadas por una longitud k determinada, puede clasificarlo por O (n). Si sus datos son comparables y no tienen una clave limitada, pero elige una clave limitada con la que particionar el conjunto, la complejidad de la clasificación del conjunto sería O (n log n) y la partición sería O (n) .

Parece que estás haciendo dos preguntas diferentes de una vez aquí.

1) Si solo permite verificaciones de igualdad, ¿hace la partición más fácil que si tuviéramos algún pedido? La respuesta es no. Necesita comparaciones con Omega (n ^ 2) para determinar la partición en el peor de los casos (todas diferentes, por ejemplo).

2) Si se permite el pedido, ¿es más fácil la partición que la clasificación? La respuesta de nuevo es no. Esto se debe al problema de la distinción del elemento . Lo que dice que para determinar si todos los objetos son distintos, se requieren comparaciones de Omega (nlogn). Dado que la clasificación se puede realizar en tiempo O (nlogn) (y también tiene límites inferiores Omega (nlogn)) y resuelve el problema de la partición, asintóticamente son igualmente difíciles.

Si elige una función hash arbitraria, los objetos iguales no necesitan tener el mismo hash, en cuyo caso no ha realizado ningún trabajo útil al ponerlos en una tabla hash.

Incluso si se crea un hash de este tipo (se garantiza que los objetos iguales tienen el mismo hash), se espera que la complejidad del tiempo sea O (n) para los hashes correctos, y el peor de los casos es Omega (n ^ 2).

Si se utiliza el hashing o la clasificación completamente depende de otras restricciones que no estén disponibles en la pregunta.

¡Las otras respuestas también parecen estar olvidando que su pregunta es (principalmente) sobre la comparación de la partición y la clasificación!

Si no le importa el orden final de los conjuntos de equivalencia, la partición en conjuntos de equivalencia podría ser más rápida. Sin embargo, depende del algoritmo y la cantidad de elementos en cada conjunto.

Si hay muy pocos elementos en cada conjunto, entonces también puede ordenar los elementos y luego encontrar los elementos iguales adyacentes. Un buen algoritmo de clasificación es O (n log n) para n elementos.

Si hay algunos conjuntos con muchos elementos en cada uno, puede tomar cada elemento y compararlos con los existentes. Si pertenece a uno de ellos, agréguelo, de lo contrario, cree un nuevo conjunto. Esto será O (n * m) donde n es el número de elementos, y m es el número de conjuntos de equivalencia, que es menor que O (n log n) para n grande y m pequeña, pero peor es que m tiende a n .

Un algoritmo combinado de clasificación / partición puede ser más rápido.

Si puede definir una función hash para los elementos, así como una relación de equivalencia, entonces debería poder realizar la partición en tiempo lineal, suponiendo que calcular el hash sea tiempo constante. La función hash debe asignar elementos equivalentes al mismo valor hash.

Sin una función hash, tendría que comparar cada elemento nuevo que se insertará en las listas particionadas con el encabezado de cada lista existente. La eficiencia de esa estrategia depende de cuántas particiones habrá eventualmente.

Digamos que tiene 100 elementos, y finalmente se dividirán en 3 listas. Luego, cada elemento debería compararse con un máximo de otros 3 elementos antes de insertarlo en una de las listas.

Sin embargo, si esos 100 elementos finalmente se dividirían en 90 listas (es decir, muy pocos elementos equivalentes), es una historia diferente. Ahora su tiempo de ejecución está más cerca de ser cuadrático que lineal.

Si se debe usar un comparador, entonces el límite inferior es compar (n log n) comparaciones para ordenar o particionar. La razón es que todos los elementos deben ser inspeccionados Ω (n), y un comparador debe realizar comparaciones de log n para que cada elemento identifique o coloque ese elemento de manera única en relación con los otros (cada comparación divide el espacio en 2, y así para un espacio de tamaño n, se necesitan log n comparaciones.)

Si cada elemento puede asociarse con una clave única que se deriva en un tiempo constante, entonces el límite inferior es Ω (n), para clasificar la partición ant (cf RadixSort )