Compromis spatio-temporel pour un problème d'élément manquant

Voici un problème bien connu.

Étant donné un tableau $A[1\dots n]$ d'entiers positifs, affichez le plus petit entier positif ne figurant pas dans le tableau.

Le problème peut être résolu dans l' espace et le temps $O(n)$ : lire le tableau, garder une trace dans l' espace $O(n)$ que $1,2,\dots,n+1$ soient produits, rechercher le plus petit élément.

J'ai remarqué que vous pouvez échanger de l'espace contre du temps. Si vous avez mémoire uniquement, vous pouvez le faire enrounds et obtenir le temps. Dans un cas particulier, il existe évidemment un algorithme à temps quadratique à espace constant. $O(\frac{n}{k})$ $k$ $O(k n)$

Ma question est:

Est-ce le compromis optimal, c'est-à-dire que le ? En général, comment prouver un tel type de bornes? $\operatorname{time} \cdot \operatorname{space} = \Omega(n^2)$

Supposons un modèle RAM, avec arithmétique bornée et accès aléatoire aux tableaux dans O (1).

Inspiration pour ce problème: compromis temps-espace pour les palindromes dans le modèle à une bande (voir par exemple ici ).

complexity-theory time-complexity space-complexity sdcvvc
la source

Non, vous pouvez trier votre tableau dans

puis trouver le numéro manquant (le premier nombre devrait être 1, le second devrait être 2, ... sinon vous le trouverez) dans O (n), ce tri pourrait être fait avec inplace mergesort, des moyens de

de l' espace supplémentaire, de sorte que le temps

espace appartient à

. Je ne sais pas si j'ai eu votre problème exactement ou non (à cause de cela, je n'y ai pas répondu, je ne sais pas non plus s'il y a une meilleure limite).

O (n \log n)

$O(n \log n)$

O (1)

$O(1)$

\cdot

$\cdot$

O (n \log n)

$O(n \log n)$

Je suppose que l'entrée est en lecture seule. (Si ce n'est pas le cas, le problème peut être résolu de manière optimale dans l' espace

temps /

: multipliez l'entrée par 2 et utilisez la parité pour simuler l' algorithme

)

O (n)

$O(n)$

O (1)

$O(1)$

O (n) / O (n)

$O(n)/O(n)$

sdcvvc

Quel est l'algorithme à espace constant? Il semble que vous auriez besoin d'

espace

pour la version

qui est "évidente" pour moi

\log n

$\log n$

n^{2}

$n^2$

Xodarap

Dans ce modèle, les entiers de taille de mot prennent

; si c'est plus pratique, vous pouvez répondre à n'importe quelle variante de la question avec le

O (1)

$O(1)$

pour une constante

time \cdot space = Ω (\frac{n^{2}}{\log^{k} n})

$\operatorname{time} \cdot \operatorname{space} = \Omega(\frac{n^2}{\log^k n})$

k

$k$

sdcvvc

@sdcvvc, je ne comprends pas votre algorithme

, le décririez-vous un peu plus? (il suffit de noter que la lecture en bits prend

O (n) / O (1)

$O(n)/O(1)$

O (\log n)

$O(\log n)$

Réponses:

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

Disons qu'il y a $n_0$ pairs et $n_1$ nombres impairs dans la plage $[1, n + 1]$ (donc $n_0 \approx n_1$ et $n_0 + n_1 = n + 1$ ). Alors il y a $b \in \{0, 1\}$ tel qu'il y ait au plus $n_b - 1$ valeurs avec parité $b$ en entrée. En effet, sinon il y a au moins pair et au moins $n_0$ $n_1$ valeurs impaires en entrée, ce qui signifie qu'il y a au moins $n_0 + n_1 = n + 1$ valeurs en entrée, contradiction (il n'y en a que $n$ ). Cela signifie que nous pouvons continuer à rechercher le nombre manquant uniquement parmi les nombres pairs ou impairs. Le même algorithme peut également être appliqué à des bits supérieurs de notation binaire.

Donc, notre algorithme ressemblera à ça:

Supposons que nous avons déjà maintenant qu'il n'y a que $x$ valeurs en entrée avec le reste modulo $2^b$ égal à $r \in [0, 2^b)$ mais qu'il y a au moins $x + 1$ nombres dans la plage $[1, n + 1]$ qui ont reste $r$ modulo $2^b$ (au départ on sait que pour $b = 0, r = 0$ ).
Disons 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 nombres en un seul passage à travers l'entrée). Clairement, $x_0 + x_1 = x$ . De plus, comme il y a au moins $x + 1$ nombres en 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$ .
Nous avons trouvé le nombre manquant lorsque $2^b \geqslant n + 1$ : il n'y a qu'un seul nombre dans la plage $[1, n + 1]$ qui peut avoir le reste $r$ modulo $2^b$ ( $r$ lui-même s'il est dans la plage), donc il y a à la plupart des valeurs nulles dans l'entrée qui ont un tel reste. Il manque donc $r$ .

De toute évidence, l'algorithme s'arrête en $O(\log n)$ étapes, chacun d'eux a besoin de $O(n)$ temps (passage unique sur le tableau d'entrée). De plus, seuls $O(1)$ mots de mémoire sont nécessaires.

Kaban-5
la source

Je suis heureux de voir la réponse à la question après cette heure :)

sdcvvc

Si je comprends vos définitions, cela peut se faire en temps linéaire avec un espace constant. C'est évidemment la borne la plus basse, car nous devons au moins lire l'intégralité de l'entrée.

La réponse donnée dans cette question est satisfaisante.

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

En termes de votre question générale, je ne connais pas de bons théorèmes qui vous aideront à prouver les compromis espace-temps. Cette question semble indiquer qu'il n'y a pas de réponse facile (connue). Fondamentalement:

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

est inconnue, et une réponse forte résoudrait beaucoup de problèmes ouverts (notamment sur SC), ce qui implique qu'aucune solution facile n'existe.

EDIT: Ok, avec répétition (mais je suppose toujours qu'avec une entrée de taille le nombre maximum possible est ). $n$ $n+1$

Observez que notre algorithme doit pouvoir différencier au moins réponses possibles. Supposons qu'à chaque passage dans les données, nous puissions obtenir au plus éléments de données. Ensuite, nous aurons besoin de passes pour différencier toutes les réponses. En supposant que alors nous courons en $n$ $k$ $n/k$ $k=n/s$ temps. Je pense donc que cela prouve ce que vous voulez. $\frac{n}{n/s}n=sn$

La difficulté est de montrer qu'à chaque fois, nous n'obtenons que bits. Si vous supposez que notre seule opération légale est =, alors nous sommes bons. Cependant, si vous autorisez des opérations plus complexes, vous pourrez obtenir plus d'informations. $k$

Xodarap
la source

La question que vous avez liée suppose que chaque numéro apparaît au plus une fois. Je ne fais pas cette hypothèse, donc la solution ne s'applique pas. Merci pour le deuxième lien.

sdcvvc

@sdcvvc: Mon erreur, j'ai supposé que vous utilisiez la version que je connais. Je n'ai pas de réponse complète, mais c'est trop long pour un commentaire - j'espère que ma modification est utile.

Xodarap

Je n'achète pas votre argument après "EDIT". Même si vous ne pouvez collecter que

bits en une seule passe, cela suffit en principe pour distinguer

sorties possibles. Cet argument ne peut donc impliquer qu'une limite inférieure de

passes, pas

k

$k$

2^{k}

$2^k$

n / 2^{k}

$n/2^k$

n / k

$n/k$

JeffE