Sie erhalten ein großes binäres Array.
Ich möchte zeigen, dass kein Algorithmus Folgendes kann (oder überrascht sein und herausfinden, dass es solche Algorithmen schließlich gibt):
1) Verarbeiten Sie das Eingabearray mit unbegrenzter Zeit, jedoch nur mit -Bits .
2) Beantworten Sie Abfragen in konstanter Zeit, wobei die Abfrage nach der Anzahl der gesetzten Bits zwischen Index und Index im Array fragt .x y
Es scheint, dass die konstante Zeit pro Abfrage dem Algorithmus nicht erlauben sollte, genügend Informationen zu lesen, um die Anzahl der gesetzten Bits zu berechnen.
Wie können wir beweisen, dass es keinen solchen Algorithmus gibt?
Eine allgemeinere Frage wäre:
Welche Untergrenze für die Abfragezeit können wir ableiten , da der Algorithmus -Raum verwenden darf?
Wenn wir Speicherplatz haben, können wir natürlich alle Teilsummen speichern und Abfragen in beantworten , aber was ist, wenn kleiner ist?O ( 1 ) f
Sie können annehmen, dass die Größe eines Speicherworts und wir die Indizes in konstanter Zeit lesen können .x , y
Antworten:
Ich glaube, dass Sie nach einer kompakten Datenstruktur suchen, die die Rangoperation unterstützt. Sehen...
https://en.m.wikipedia.org/wiki/Succinct_data_structure
Insbesondere können Sie die Emils (erste) Lösung ändern, um die Pop-Count-Operation zu entfernen und durch eine Nachschlagetabelle zu ersetzen (Details finden Sie im Wiki-Artikel). Durch Reduzieren der Größe eines Blocks auf (log n) / 2 Bits verwendet die Nachschlagetabelle o (n) Bits.
quelle
Ich wäre mir nicht so sicher, ob es einen solchen Algorithmus nicht gibt. Es gibt sicherlich Algorithmen, die sehr nahe kommen. Unten ist , ist , ist , iterierter Logarithmus , und ist .logn log2n log(k)n log…logk timesn log∗n O~(t(n)) O(t(n)polylog(t(n)))
Die Algorithmen arbeiten wie folgt. Es gibt Parameter und Abhängigkeit von . Wir spalten die Size- Eingangs Array in Size- Blöcke (Stufe 1); Wir teilen jeden Block der Ebene 1 in Blöcke der Größe (Ebene 2) auf. und so weiter bis Level . (Stellen wir uns vor, alle sind Potenzen von , um Probleme mit der Teilbarkeit zu vermeiden.) Dann:k>0 n=b0>b1>⋯>bk>0 n b0 b1 b2 k bi 2
Für jedes und jeden Level- Block speichern wir die Anzahl der gesetzten Bits im Intervall vom Beginn des Blocks bis zur nächsten Level- -Blockgrenze .i=1,…,k i (i−1)
Um eine Abfrage aufzulösen, addieren wir die gespeicherten Zahlen, die dem Index entsprechen, und zählen die gesetzten Bits vor dem Index in seinem Level- Block. Wir machen das alles für und getrennt und subtrahieren die Ergebnisse.k k x y
(Wenn die Parameter nicht einfach zu berechnen sind, können wir sie auch speichern.)bi
Diese Anordnung verwendet den Raum und die Abfragezeit
In dem Satz für 1. lassen wir konstant sein und setzen für , .k bi=log(i)n 0<i<k bk=1
Für 2. können wir und Der Raum wird dann durch ungefähr für eine Konstante .k=log∗n
quelle
Es stellt sich heraus, dass dies nicht nur in Speicherbits möglich ist, wie in Benjamin Sachs Antwort vorgeschlagen, sondern auch in Bits.n ≤ ( 1 + o ( 1 ) )O(n) n⋅(1+o(1))
Die Idee ist, sich die Bit-Eingabe als den charakteristischen Vektor einer Teilmenge von (dh das Bit wird gesetzt, wenn in der Menge ist). Dann können wir einfach ein prägnantes Wörterbuch verwenden , um die Menge mit der erforderlichen Anzahl von Bits darzustellen.{ 1 , 2 , … , n } i ' t h in {1,2,…,n} i′th i
quelle