Sospecho que hay una manera si puede guardar localizando el otro extremo de un rango de valores repetidos más rápido que iterando a través de esa sublista¿Es posible eliminar duplicados de una lista ordenada en menos de O (n) tiempo?
En general, no. Imagine una lista de N duplicados. Tendría que hacer eliminaciones de N-1, por lo tanto, O (N).
Si especifica una estructura de datos particular con mejor que O (1) eliminación de elementos, entonces podría haber un mejor camino para ciertos tipos de entradas.
Incluso si puede eliminar eficientemente un rango de elementos en O (1), y tarda O (1) tiempo en encontrar un duplicado - imagine una lista donde hay N/2 pares de duplicados. Aún tendrá que hacer N/2 búsquedas y eliminar N/2 rangos, ambos de los cuales son O (N).
(también hay un poco de ambigüedad como el título de la pregunta es 'eliminar duplicados', pero el cuerpo es específico para la eliminación de un rango)
Si la lista resultante de su especie tiene la siguiente representación - Cada nodo tiene un valor, y un recuento de ocurrencia para eso, luego eliminar las duplicaciones para un valor establecerá trivialmente el recuento a 1 para ese nodo. (A skip list probablemente tenga características similares, asumiendo un ambiente decente recogido de basura donde no hay costo para reclamar memoria), entonces eso sería O (1) para una duplicación. Si necesita eliminar todos los duplicados de la lista, todavía sería O (N).
Imagine una lista de N duplicados. Tendría que hacer remociones N-1, por lo tanto O (N) - No, si conoce el principio y el final del rango de duplicados, entonces solo tiene una eliminación. –
@Jakub, el resto podría cortarse en O (1). Liberarlo correctamente dará O (n). – ruslik
@ruslik: defina correctamente. Una simple comprobación de la igualdad del primer y último elemento es una correcta en mi humilde opinión. –
Yo iría por un enfoque 'binario de búsqueda' para encontrar extremos de los rangos:
Supongamos que tenemos una lista ordenada de n elementos.
¿Estás hablando de una lista vinculada o una matriz ordenada? –
¿Cómo no van a hacer O (N) operaciones si la lista es N/2 lotes de duplicados? –
@Blagovest a una matriz una sola eliminación es O (n) .. – ruslik
En general no existe, porque siempre puede construir un caso en el que tiene O (n) (una lista sin duplicados). Sin embargo, si comienza a hacer suposiciones sobre los datos (por ejemplo, que hay como mucho log n elementos distintos), puede obtener algo mejor (aunque no estoy seguro en este caso particular).
Esto, por supuesto, supone que tiene alguna forma de hacer "eliminaciones masivas" eficientes, lo que significa que puede eliminar cualquier rango de elementos iguales en O (1), independientemente de su tamaño.
No puedo estar
como para la comparación de todos los elementos con el otro que tenemos que hacer n * (n-1) = n2-n comparaciones ... `
¿Qué quiere decir con "la lista "¿?" En una lista enlazada, el cruce es inevitablemente O (N). Si solo quiere decir "alguna estructura de datos lineal", puede usar una búsqueda binaria en una estructura de datos que admita un recorrido binario o aleatorio (por ejemplo, un árbol o una matriz). –
si el algoritmo de clasificación tiene complejidad de tiempo O (nlogn) y puede eliminar los duplicados en O (1) tiempo, la complejidad general seguirá siendo O (nlogn). –
Para aclarar quiero decir una estructura de datos lineal que admite acceso aleatorio, pero no un árbol. Vamos a llamarlo una matriz. –