¿Cómo selecciono todos los elementos en una lista que están fuera de servicio?

Question

Esta pregunta surgió de la discusión en los comentarios de this answer.

Primero, digamos que es bastante difícil definir lo que está fuera de servicio. Tomando el ejemplo que dio Pavel Shved, en la lista [1,5,10,2,3,4,5,6,7,8,9,10,11] podemos ver "claramente" que 5 y 10 (índices 1) y 2) están fuera de servicio. Pero un algoritmo ingenuo que simplemente verifique algún tipo de lista ordenada invariante no los señalaría.

• comprobación a[i-1]<=a[i] for all 0<i<=N produciría el elemento en el índice 3 (que es 2);

• comprobando a[j]<=a[i] for all 0<=i<=N and 0<=j<=i arrojaría todos los elementos en los índices 3 a 12;

Mi pregunta es: ¿se puede pensar en un algoritmo para resolver este problema que produce la "respuesta correcta" (es decir, los índices 1 y 2)? Si es así, ¿bajo qué tiempo y complejidad de memoria se ejecutaría?

Answer 1

Probablemente el mejor enfoque para esto sería encontrar primero el longest increasing subsequence y luego considerar que todos los elementos que no forman parte de esa secuencia están fuera de servicio. El algoritmo provisto en la página vinculada se ejecuta en el tiempo O(n log n) y usa el espacio O(n) (además del de la propia lista).

Tal enfoque sería sin duda producir la respuesta correcta para su caso de ejemplo, ya que la más larga subsecuencia creciente sería la secuencia del 1 al 11 sin incluir el precio de 5 y 10.

Answer 2

Cómo debe conocer el algoritmo que le elementos considerar fuera de servicio?

Si la regla es "list [i + 1] siempre debe ser list [i] + 1", entonces sería fácil, por supuesto, memorizar que después de 1, el siguiente elemento debería ser 2, seleccionar aquellos en el medio y así sucesivamente. Pero necesita una regla precisa para que el algoritmo determine qué elementos se deben considerar "fuera de orden".

Answer 3

Como dijo Dav, longest increasing subsequence es probablemente lo mejor que puede hacer.

esto está fuera de mi cabeza, por lo que puede (probablemente no lo es: P) corregir: El obvio límite inferior para este problema es O (n) ya que al menos tiene que leer cada número una vez . Pero supongamos que hay un algoritmo que se ejecutó en O (n) tiempo. Luego puede simplemente insertar los elementos fuera de servicio en orden en tiempo lineal, pero el mejor algoritmo de comparación tiene un límite inferior de O (nLogn) por lo que es una contradicción. (de lo contrario, hay métodos de ordenación sin comparación como clasificación por cubo o raíz que usan mucha memoria o explotan el tamaño de los números que se ordenan ...)