Pouvons-nous obtenir une sous-séquence de taille $ \ ge \ lfloor \ frac {n} {2} \ rfloor $ dans un ordre trié à partir d'une séquence de temps linéaire?

Question

donné une séquence $ a $ de $ n $ nombres entiers distincts, existe-t-il une stratégie pourObtenez au moins une sous-séquence avec la taille $ \ geq \ lfloor \ frac {n} {2} \ rfloor $ de la séquence dans l'ordre trié dans $ o (n) $ temps?

Par exemple, disons que $ A= [4, 11, 6, 2, 9, 7] $ .Ensuite, une des séquences requises peut être $ [2, 7, 11] $ , qui est la version triée de la section suivante $ [11, 2, 7] $ .Votre stratégie peut donner une telle recherche dans une ordonnance triée.

Oui, je pense que c'est impossible à 99,99%.Mais je ne sais pas avec certitude.Quelqu'un peut-il montrer qu'il ne peut exister pas une telle stratégie ou prouver autrement?

Answer 1

C'est impossible (en supposant que vous utilisez uniquement des comparaisons).Tout d'abord, nous augmentations tous les éléments avec des indices: $ a [i] \ to (a [i], i) $ .Nous aurons besoin de cela lorsque nous allons supprimer la séquence du tableau en temps linéaire.

Considérez l'algorithme de tri suivant:

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 résultat, le temps d'exécution est $ O (n + \ frac n2 + \ frac n4 + ...)= O (n) $ , qui violeune liaison inférieure bien connue pour le tri.