Dies ist eine Ausgliederung dieser Frage von StackOverflow
Angenommen, Sie haben eine feste Anzahl k von Speicherorten und Platz für zwei Zähler. Sie erhalten n Objekte in zufälliger Reihenfolge (alle Permutationen der n Objekte sind gleich wahrscheinlich). Nachdem Sie jedes Objekt empfangen haben, können Sie es entweder an einem der k Standorte speichern (einen der zuvor gespeicherten Werte verwerfen) oder das Objekt verwerfen. Sie können auch einen der Zähler erhöhen oder verringern. Ein verworfenes Objekt kann nicht abgerufen werden.
Die Fragen sind
Offensichtlich, wenn k & gt; n / 2 können wir den Median finden. Im Allgemeinen scheint es, dass die gleiche Strategie, zu versuchen, die Anzahl verworfener hoher Werte gleich der Anzahl verworfener niedriger Werte zu halten, optimal sein sollte, aber ich bin mir nicht sicher, wie ich es beweisen und wie ich die Wahrscheinlichkeit herausfinden soll der Median.
Interessant ist auch der Fall, in dem wir n nicht kennen, aber die Wahrscheinlichkeitsverteilung von n kennen.
Bearbeiten: Nehmen Sie jetzt an, dass die Werte eindeutig sind (keine Duplikate.) Wenn Sie jedoch auch den nicht eindeutigen Fall lösen können, wäre das beeindruckend.
Munro und Paterson haben dieses Problem im Wesentlichen in ihrem Papier Auswahl und Sortieren mit begrenztem Speicher untersucht . Sie zeigen, dass Ihr Algorithmus erfordert, dass k = Ω (√ n) mit konstanter Wahrscheinlichkeit erfolgreich ist und dass dies asymptotisch optimal ist, indem grundlegende Ergebnisse über eindimensionale zufällige Wege angesprochen werden.
Wenn ich absolute Optimalität beweisen wollte, würde ich zuerst versuchen, einen willkürlichen Algorithmus A zu betrachten und dann seine Ausführung mit einem Algorithmus A 'zu koppeln, von dem A das erste Mal abweicht Ihr Algorithmus, würde Ihr Algorithmus stattdessen tun und dann versuchen, A so genau wie möglich zu folgen.
Eine wilde Schätzung: Verwerfen Sie das Element, das am weitesten von dem Mittelwert der aktuell gespeicherten Werte entfernt ist.
Der Vergleich mit dem aktuellen Median funktioniert nicht, wenn die Werteverteilung multimodal ist und wir zuerst Werte aus einem nicht dominanten Modus erhalten.
Tags und Links algorithm probability