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?
-
29-09-2020 - |
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?
La solution
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.