Wie zählt man im linearen Zeit-Worst-Case?

Diese Frage und diese Frage haben mich ein wenig zum Nachdenken gebracht. Um ein Array der Länge mit eindeutigen Elementen in sortieren , müssen wir in der Lage sein, die Anzahl der Werte im Array zu speichern. Es gibt einige Vorschläge, aber ich suche nach einer Möglichkeit, dies im schlimmsten Fall der linearen Zeit zu tun. Genauer:$n$$k$$O(n + k \log k)$

Bestimmen Sie bei einer Liste von n Elementen mit k verschiedenen Elementen eine Liste der Tupel U = \ {(x_i, c_i) \} ^ k aller eindeutigen Elemente x_i \ in A, so dass c_i die Anzahl der Elemente x_i in A ist .$A$$n$$k$$U = \{(x_i, c_i)\}^k$$x_i \in A$$c_i$$x_i$$A$

Hier sind einige (fehlgeschlagene) Ideen, die ich hatte und die vorgeschlagen wurden:

1. Ausgewogener binärer Suchbaum - Damit wird $O(\log k)$ , um in den Baum einzufügen und die Werte zu erhöhen. Nach dem Einfügen konnten wir in $O(k)$ eine Baumdurchquerung durchführen . Somit ergibt sich eine Gesamtzeit von $O(n \log k)$ die zu langsam ist.
2. Hash Map - Damit können wir $O(1)$ erwartete Einfügungen und damit $O(n)$ erwartete Zeit erhalten. Dies ist jedoch immer noch nicht der schlimmste Fall von $O(n)$ .
3. Der leere Raum Mapping - Finden Sie die minimale und maximale Element in $A$ . Weisen Sie genügend Speicher zu ( initialisieren Sie ihn jedoch nicht ), um diesen Bereich abzudecken. Verwenden Sie diesen Speicher grundsätzlich als Hash-Map und fügen Sie einen zufälligen Hash hinzu, damit wir nicht versuchen, auf beschädigten Speicher zuzugreifen. Diese Strategie wirft Probleme auf. (1) Es ist probabilistisch mit sehr, sehr geringer Ausfallwahrscheinlichkeit, aber immer noch nicht garantiert. Die Verwendung eines solchen Speichers beschränkt uns auf Gleitkomma- oder Ganzzahlbeschränkungen.
4. Assoziative Arrays - Es gibt viele andere assoziative Arrays, die verwendet werden können, ähnlich wie Hash-Maps und BSTs, aber ich finde keine, die diesen Einschränkungen entsprechen.

Vielleicht fehlt mir eine offensichtliche Methode, aber ich denke auch, dass dies möglicherweise nicht möglich sein könnte. Was sind deine Gedanken?

Das ist eine schöne Frage.

Im Vergleichsmodell oder allgemeiner im algebraischen Entscheidungsbaummodell hat das Problem der Elementunterscheidbarkeit im schlimmsten Fall eine Untergrenze von $\Theta(n\log n)$ Zeitkomplexität, wie in diesem Wikipedia-Artikel erwähnt . Es gibt also keinen Algorithmus, um im schlimmsten Fall verschiedene Elemente in linearer Zeit zu zählen, auch ohne die Duplizitäten zu zählen.

Es ist jedoch nicht klar, ob dies in einem anderen Rechenmodell möglich ist. In einem vernünftigen deterministischen Rechenmodell erscheint dies unwahrscheinlich.

Es gibt randomisierte Algorithmen, deren erwartete Laufzeit $O(n)$ ; oder wo die Wahrscheinlichkeit, dass die Laufzeit länger als $cn$ dauert, in $c$ exponentiell klein ist .

Wählen Sie insbesondere zufällig eine 2-universelle Hash-Funktion aus und verwenden Sie sie dann, um alle Elemente des Arrays zu hashen. Dadurch werden die angegebenen Laufzeiten erreicht, wenn Sie die Länge der Ausgabe des 2-Universal-Hash entsprechend auswählen.

Als weiteres Beispiel, können Sie einen randomisierten Algorithmus Worst-Case , deren Zeit aufbauen können ausgeführt ist $O(n)$ (es läuft immer in der linearen Zeit, egal was) und hat eine Irrtumswahrscheinlichkeit von höchstens $1/2^{100}$ . (Wie? Führen Sie den obigen Algorithmus aus und beenden Sie ihn, wenn er für ein entsprechend ausgewähltes c länger als $cn$ Schritte läuft .) In der Praxis ist dies gut genug, da die Wahrscheinlichkeit, dass Ihr Computer aufgrund einer kosmischen Strahlung die falsche Antwort ausgibt, bereits besteht viel höher als 1 / 2 100 .$c$$1/2^{100}$

Ihr Ansatz 3 kann mit einer Lösung für Übung 2.12 von Aho, Hopcroft und Ullman (1974), Entwurf und Analyse von Computeralgorithmen, wie beispielsweise unter Verwenden von nicht initialisiertem Speicher für Spaß und Gewinn beschrieben, sicher gemacht werden .

Grundsätzlich haben Sie zusätzlich zu Ihrem Array von N Elementen mit den Zählwerten zwei Arrays von N Elementen und einen Hilfszähler, um eine spärliche Menge zu erstellen, die angibt, welche der Zählungen gültig sind.

Im C-ähnlichen Pseudocode:

uint* a = malloc(n);
uint* b = malloc(n);
uint* c = malloc(n);
uint len = 0;

get_count(uint x) {
    uint idx = a[x];
    return idx >= 0 && idx < len && b[idx] == x ? c[idx] : 0;
}

increment_count(uint x) {
    uint idx = a[x];
    if (idx < 0 || idx >= len || b[idx] != x) {
        idx = len;
        len++;
        a[x] = idx;
        b[idx] = x;
        c[idx] = 0;
    }
    c[idx]++;
}

Die praktische Implementierung des Sparse-Sets wird in dieser StackOverflow-Antwort erläutert .