Zeitraum Kompromiss für fehlende Elementprobleme

Question

Hier ist ein bekanntes Problem.

Bei einem Array $ a [1 dots n] $ $ positive Ganzzahlen geben die kleinste positive Ganzzahl nicht im Array aus.

Das Problem kann in $ O (n) $ Space and Time gelöst werden: Lesen Sie das Array, behalten Sie den Überblick über $ o (n) $ space, ob $ 1.2, dots, n+1 $ auftreten, scannen nach kleinstem Element.

Mir ist aufgefallen, dass Sie Raum für die Zeit tauschen können. Wenn Sie nur $ o ( frac {n} {k}) $ Memory haben, können Sie dies in $ k $ Runden tun und Zeit $ O (KN) $ erhalten. In einem Sonderfall gibt es offensichtlich quadratische Zeitalgorithmus mit konstantem Raum.

Meine Frage ist:

Ist dies der optimale Kompromiss, dh $ operatorname {time} cdot operatorname {space} = omega (n^2) $? Wie beweist man im Allgemeinen eine solche Art von Grenzen?

Nehmen Sie das RAM -Modell mit begrenzten arithmetischen und zufälligen Zugriff auf Arrays in O (1) an.

Inspiration für dieses Problem: Zeitraum-Kompromiss für Palindrome im Ein-Tape-Modell (siehe zum Beispiel, hier).

Answer 1

Dies kann in erledigt werden in $ O (n log n) $ Wortoperationen und $ O (1) $ Erinnerungswörter (jeweils $ O (n log^2 n) $ Zeit und $ O ( log n) $ Speicher in Bit-Level-RAM-Modell). In der Tat basiert die Lösung auf der folgenden Beobachtung.

Sagen, es gibt $ n_0 $ sogar und $ n_1 $ ungerade Zahlen in Reichweite $ [1, n + 1] $ (Also $ n_0 ca. n_1 $ und $ n_0 + n_1 = n + 1 $). Dann ist da $ B in {0, 1 } $ so dass es höchstens gibt $ n_b - 1 $ Werte mit Parität $ b $ im Eingang. In der Tat gibt es mindestens zumindest $ n_0 $ sogar und zumindest $ n_1 $ ungerade Werte in der Eingabe, was bedeutet, dass es zumindest gibt $ n_0 + n_1 = n + 1 $ Werte in der Eingabe, Widerspruch (es gibt nur $ n $ von ihnen). Dies bedeutet, dass wir weiterhin nur unter den ungeraden oder sogar Zahlen nach einer fehlenden Zahl suchen können. Der gleiche Algorithmus kann auch auf höhere Bits der binären Notation angewendet werden.

Unser Algorithmus wird also so aussehen:

1. Angenommen, wir jetzt, dass es nur gibt $ x $ Werte in der Eingabe mit dem Restmodulo $ 2^b $ gleich sein $ r in [0, 2^b) $ aber es gibt zumindest $ x + 1 $ Zahlen im Bereich $ [1, n + 1] $ das haben Rest $ r $ Modulo $ 2^b $ (Zu Beginn wissen wir das mit Sicherheit für $ b = 0, r = 0 $).

2. Sagen, es gibt $ x_0 $ Werte im Eingang mit Rest $ r $ Modulo $ 2^{B + 1} $ und $ x_1 $ Werte im Eingang mit Rest $ r + 2^b $ Modulo $ 2^{B + 1} $ (Wir können diese Zahlen in einem einzigen Durchgang finden). Deutlich, $ x_0 + x_1 = x $. Darüber hinaus, weil es zumindest gibt $ x + 1 $ Zahlen im Eingang mit Rest $ r $ Modulo $ 2^b $, mindestens eines der Paare $ (r, b + 1), (r + 2^b, b + 1) $ erfüllt die Anforderungen des Schritts $1$.

3. Wir haben die fehlende Nummer gefunden, wenn $ 2^B Geqslant n + 1 $: Es gibt nur eine Zahl im Bereich $ [1, n + 1] $ Das kann Rest haben $ r $ Modulo $ 2^b $ ($ r $ selbst wenn es sich im Bereich befindet), so gibt es höchstens Nullwerte in der Eingabe, die einen solchen Rest haben. So $ r $ fehlt in der Tat.

Offensichtlich hält der Algorithmus ein $ O ( log n) $ Schritte, jeder von ihnen braucht $ O (n) $ Zeit (Single -Pass über das Eingangsarray). Außerdem nur $ O (1) $ Speicherwörter sind erforderlich.

Answer 2

Wenn ich Ihre Definitionen verstehe, kann dies in linearer Zeit mit konstantem Raum erfolgen. Dies ist offensichtlich die niedrigste Grenze, da wir zumindest den gesamten Eingang lesen müssen.

Die Antwort in diese Frage zufrieden.

Es ist unmöglich, dies mit weniger Zeit oder Platz zu betreiben, und das Hinzufügen von zusätzlicher Zeit oder Platz ist nutzlos, sodass hier keinen Raum-Zeit-Kompromiss gibt. (Beachten Sie, dass $ n = o (n/k) $, so dass der von Ihnen beobachtete Kompromiss in jedem Fall nicht asymptotisch gilt.)

In Bezug auf Ihre allgemeine Frage kenne ich keine netten Theoreme, die Ihnen helfen, Raum-Zeit-Kompromisse zu beweisen. Diese Frage Scheint darauf hinzudeuten, dass es keine (bekannte) einfache Antwort gibt. Grundsätzlich:

Angenommen, eine gewisse Sprache ist in $ t $ time (unter Verwendung einiger Speicherplatz) und $ s $ space (unter Verwendung einer gewissen Zeit). Können wir $ f, g $ so finden, dass $ l $ um $ m $ läuft, was in $ f (t, s) $ time und $ g (t, s) $ space läuft?

ist unbekannt, und eine starke Antwort würde viele offene Probleme lösen (insbesondere über SC), was bedeutet, dass keine einfache Lösung vorliegt.

---

Bearbeiten: OK, mit Wiederholung (aber ich gehe immer noch davon aus, dass die maximal mögliche Zahl $ n+1 $ ist).

Beachten Sie, dass unser Algorithmus in der Lage sein muss, zwischen mindestens $ n $ möglichen Antworten zu unterscheiden. Angenommen, wir können bei jedem Durchgang die Daten über die höchsten Daten im Wert von $ k $ erhalten. Dann benötigen wir $ N/K $ Pässe, um alle Antworten zu unterscheiden. Angenommen, $ k = n/s $, laufen wir in $ frac {n} {n/s} n = sn $ Zeit. Ich denke, das beweist, was Sie wollen.

Die Schwierigkeit besteht darin, zu zeigen, dass wir jedes Mal nur $ k $ Bit erhalten. Wenn Sie davon ausgehen, dass unsere einzige juristische Operation = ist, sind wir gut. Wenn Sie jedoch komplexere Vorgänge zulassen, können Sie weitere Informationen erhalten.