¿Podemos obtener cualquier subsecuencia de tamaño $ \ ge \ lfloor \ frac {n} {2} \ rfloor $ en un orden ordenado de una secuencia en tiempo lineal?

Question

Dada una secuencia $ A $ de $ n $ enteros distintos, ¿existe una estrategia paraObtenga al menos una subsecuencia con el tamaño $ \ geq \ lfloor \ frac {n} {2} \ rfloor $ de la secuencia en orden ordenado en $ o (n) $ tiempo?

Por ejemplo, digamos que $ a= [4, 11, 6, 2, 9, 7] $ .Luego, una de las secuencias requeridas puede ser $ [2, 7, 11] $ , que es la versión ordenada de la subsecuencia $ [11, 2, 7] $ .Su estrategia puede dar cualquier siguiente subsecuencia en un orden ordenado.

Sí, creo que es 99.99% imposible.Pero, no lo sé con seguridad.¿Alguien puede mostrar que no puede existir tal estrategia o demostrar lo contrario?

Answer 1

Es imposible (asumir que solo use comparaciones).Primero, aumentamos todos los elementos con los índices: $ a [i] \ a (a [i], i) $ .Lo necesitaremos cuando eliminemos la secuencia de la matriz en tiempo lineal.

Considere el siguiente algoritmo de clasificación:

def sort(a):
    subseq = get_sorted_subseq(a)  # Your function. Assume takes O(n) time
    b = a.exclude(subseq)          # Since we know indices, takes O(n) time
    return merge(subseq, sort(b)). # Takes O(n) time (see merge sort) + recursive call of size <= n/2

En el resultado, el tiempo de ejecución es $ o (n + \ frac n2 + \ frac n4 + ...)= O (n) $ , que violaun límite inferior bien conocido para la clasificación.