compromis entre l'espace-temps pour le problème de l'élément manquant

Question

Voici un problème bien connu.

Etant donné une matrice A $ [1 \ n points] $ des nombres entiers positifs, la sortie plus petit entier positif pas dans le tableau.

Le problème peut être résolu en O $ (n) $ espace et du temps: lire la matrice, de garder trace de O $ (n) $ espace soit 1,2 $, \ dots, n + 1 $ est survenue, le balayage pour les plus petits élément.

Je remarqué que vous pouvez échanger l'espace pour le temps. Si vous avez $ O (\ frac {n} {k}) $ la mémoire seulement, vous pouvez le faire en $ k tours $ et obtenir du temps $ O (k n) $. Dans un cas particulier, il y a évidemment l'espace constant algorithme quadratique temps.

Ma question est:

  

Est-ce le compromis optimal, à savoir le fait $ \ operatorname {time} \ cdot \ operatorname {espace} = \ Omega (n ^ 2) $?   En général, comment peut-on prouver ce type de limites?

Supposons modèle de RAM, avec l'arithmétique bornée et un accès aléatoire à des tableaux en O (1).

L'inspiration pour ce problème: compromis entre l'espace-temps pour palindromes dans le modèle d'une bande (voir par exemple, ).

Answer 1

Cela peut se faire dans O $ (n \ log n) $ opérations de mots et de $ O (1) $ mots de mémoire (respectivement $ O (n \ log ^ 2 n) $ temps et $ O (\ log n) $ mémoire dans le modèle de RAM au niveau du bit). En effet, la solution sera basée sur l'observation suivante.

Dites il y a $ n_0 $ même et $ n_1 $ nombres impairs dans la gamme $ [1, n + 1] $ (donc $ n_0 \ environ n_1 $ et $ b \ in \ {0, 1 \} $ tel qu'il y ait au plus $ n_b - $ 1 avec des valeurs de parité $ b $ dans l'entrée. En effet, sinon il y a au moins $ n_0 $ même et au moins $ n_1 $ valeurs impaires dans l'entrée , ce qui signifie qu'il ya au moins $ n_0 + n_1 = n + 1 $ valeurs dans l'entrée, la contradiction (il y a seulement $ n $ d'entre eux). Cela signifie que nous pouvons continuer à chercher le numéro manquant seulement parmi les nombres impairs ou même seulement. Le même algorithme peut être appliqué à des bits supérieurs de notation binaire ainsi.

Donc, notre algorithme ressemblera que:

1. Supposons que nous avons déjà maintenant qu'il ya seulement $ x $ valeurs dans l'entrée avec modulo reste 2 $ ^ b $ est égale à $ r \ in [0, 2 ^ b) $ mais il y a au moins $ x + 1 $ nombres dans la gamme $ [1, n + 1] $ qui ont la classe reste $ r $ modulo 2 $ ^ b $ (au début, nous savons qui est sûr pour $ b = 0, r = 0 $ ).

2. dire qu'il y a $ x_0 $ valeurs dans l'entrée avec le reste $ r $ modulo $ 2 ^ {b + 1} $ et $ x 1 $ valeurs dans l'entrée avec le reste $ r + 2 ^ b $ modulo 2 $ ^ {b + 1} $ (nous pouvons trouver ces chiffres en une seule passe par l'entrée). De toute évidence, x_0 $ + = x 1 x $ . De plus, comme il existe au moins $ x + 1 $ chiffres dans l'entrée avec le reste $ r $ modulo $ 2 ^ b $ , au moins une des paires $ (r, b + 1), (r + 2 ^ b , b + 1) $ satisfait aux exigences de l'étape $ 1 $ .

3. Nous avons trouvé le nombre manquant lorsque 2 $ ^ b \ geqslant n + 1 $ : il n'y a qu'un seul numéro dans la gamme $ [1, n + 1] $ qui peut avoir reste $ r $ modulo $ 2 ^ b $ ( $ r $ elle-même si elle est dans la gamme), de sorte qu'il y a au plus des valeurs nulles dans l'entrée qui ont autant. Donc $ r $ manque en effet.

Il est clair que les arrêts d'algorithme dans $ O (\ log n) $ étapes, chacun d'eux a besoin de O $ ( n) $ temps (seul passage sur le tableau d'entrée). En outre, seule O (1) $ $ mots de mémoire sont nécessaires.

Answer 2

Si je comprends vos définitions, cela peut se faire dans le temps linéaire avec un espace constant. Ceci est évidemment la limite la plus basse, parce que nous devons au moins lire l'entrée entière.

La réponse en satisfait cette question.

Il est impossible d'exécuter ce avec moins de temps ou de l'espace, et en ajoutant de temps ou de l'espace est inutile, donc il n'y a pas de compromis entre l'espace-temps ici. (Remarquez que $ n = O (n / k) $, de sorte que le compromis entre vous avez observé ne tient pas asymptotiquement, en tout cas.)

En ce qui concerne votre question générale, je ne sais pas de tout beau théorèmes qui désinvolture vous aidera à prouver compromis espace-temps. Cette question semble indiquer qu'il n'y a pas un ( connu) réponse facile. En gros:

  

Supposons un langage est décidable en $ t temps $ (en utilisant une certaine quantité d'espace) et l'espace $ de $ (en utilisant une certaine quantité de temps). Peut-on trouver $ f, g $ tel que $ L $ est décidable par $ M $ qui fonctionne en $ f (t, s) $ temps et $ g (t, s) $ l'espace?

est inconnue, et une réponse forte résoudrait beaucoup de problèmes ouverts (notamment à propos de SC), ce qui implique que pas de solution facile existe.

---

EDIT: Ok, avec la répétition (mais je suppose encore que, avec une entrée de taille $ n $ le nombre maximal possible est n $ + 1 $).

Notez que nos besoins de l'algorithme pour pouvoir faire la différence entre au moins $ n $ réponses possibles. Supposons qu'à chaque passage à travers les données que nous pouvons obtenir dans la plupart des morceaux de $ k $ de de données. Ensuite, nous aurons besoin $ n / k $ passe pour différencier toutes les réponses. En supposant $ k = n / s $, alors nous courons en $ \ frac {n} {n / s} n = sn temps $. Je pense donc que cela prouve ce que vous voulez.

La difficulté est à démontrer que chaque fois que nous obtenons par seulement k $ bits $. Si vous supposez que notre seule opération juridique =, alors nous sommes bien. Toutefois, si vous permettez des opérations plus complexes, alors vous serez en mesure d'obtenir plus d'informations.