In einer klassischen Arbeit untersuchen Munro und Paterson das Problem, wie viel Speicher erforderlich ist, damit ein Algorithmus den Median in einem zufällig sortierten Array findet. Insbesondere konzentrieren sie sich auf das folgende Modell:
Die Eingabe wird P-mal von links nach rechts gelesen.
Es wird gezeigt, dass Speicherzellen ausreichen, die entsprechende Untergrenze jedoch nur für P = 1 bekannt ist. Ich habe kein Ergebnis für P> 1 gesehen. Kennt jemand solche Untergrenzen?
Beachten Sie, dass die Hauptschwierigkeit hier darin besteht, dass die Eingabe beim zweiten Durchgang nicht mehr in zufälliger Reihenfolge erfolgt.
ds.algorithms
space-bounded
data-streams
MassimoLauria
quelle
quelle
Das erste Papier, das Grenzen für mehr als einen Durchgang nachweist, war mein Papier mit Jayram und Amit von SODA'08. Dann gibt es das von Warren erwähnte Papier, das die Grenzen durch einen saubereren Proof verbessert.
Kurz gesagt, wir verstehen die Abhängigkeit, wenn Sie Konstanten vor der Anzahl der Durchgänge zulassen. Natürlich sind diese Konstanten im Exponenten, also können Sie um ein genaues Verständnis bitten. Meine Hauptbeschwerde ist, dass das Modell des Multipass-Streamings nicht allzu gut motiviert ist.
Die interessantere Frage ist, ob wir eine untere Schranke eines Verzweigungsprogramms nachweisen können. Kann es sein, dass selbst für einen Algorithmus mit begrenztem Speicherplatz, der nach Belieben auf den Speicher zugreifen kann, die beste Strategie darin besteht, nur Multipass-Streaming durchzuführen?
Die Antwort scheint positiv zu sein, und wir haben teilweise Fortschritte gemacht, um dies zu beweisen.
quelle