Bestimmen der bestimmten Zahl in Zeit und Raum (schlimmster Fall)

$\newcommand\ldotd{\mathinner{..}}$ , $A[1\ldotd n]$ sind ganze Zahlen, so dass $0\le A[k]\le m$ für alle $1\le k\le n$ und das Auftreten von jedem Zahl mit Ausnahme einer bestimmten Zahl in $A[1\ldotd n]$ ist eine ungerade Zahl. Versuchen Sie, die Nummer zu finden, deren Vorkommen eine gerade Zahl ist.

Es gibt einen $\Theta(n\log n)$ -Algorithmus: Wir sortieren $A[1\ldotd n]$ in $B[1\ldotd n]$ und $B[1\ldotd n]$ in viele Teile, deren der ist gleich, daher können wir das Auftreten jedes Elements zählen.

Ich möchte einen Worst- Case- $O(n)$ -Zeit- und -O $O(n)$ -Raum-Algorithmus finden.

Angenommen, $m=\Omega(n^{1+\epsilon})$ und $\epsilon>0$ , ist die Radix-Sortierung daher nicht akzeptabel. $\DeclareMathOperator{\xor}{xor}$ Binäre bitweise Operationen sind zulässig, z. B. $A[1]\xor A[2]$ .

algorithms search-algorithms Yai0Phah
quelle

Die Antwort von Aryabhata unten zeigt, dass der allgemeine Fall nicht gut ist, aber vielleicht haben Sie weitere Einschränkungen zur Verfügung? Eine einfache (aber große) Einschränkung wäre, zu erzwingen, dass alle Einträge im Array eine Größe von

O (n)

$O(n)$ haben. Dies würde einen ziemlich trivialen linearen Algorithmus ergeben.

Luke Mathieson

@LukeMathieson: Ich habe diese Antwort gelöscht, da ich noch nicht davon überzeugt bin, dass das von mir zitierte Papier ohne Änderungen funktionieren wird, und außerdem scheint OP nur an dem RAM-Modell mit einheitlichen Kosten interessiert zu sein.

Aryabhata

@ Aryabhata: hehe, nun die Antwort, die dann nicht da ist! Was war Ihrer Meinung nach das Problem bei der Anpassung des Ergebnisses in der Zeitung, das für Frank interessant und vielleicht nützlich war? Ein kurzer Blick darauf deutete darauf hin, dass es zutraf, aber ich habe es offensichtlich nicht gelesen.

Luke Mathieson

@LukeMathieson: Die Tatsache, dass die anderen Elemente im aktuellen Problem ungerade oft vorkommen müssen. Seitdem habe ich auch den Beweis überflogen ...

Aryabhata

Es wäre interessant, wenn Sie an theoretischen Ergebnissen oder praktischen Lösungen interessiert sind. Aus theoretischer Sicht ist meine erste schnelle Antwort, dass Sie eine Liste von ganzen Zahlen schneller als sortieren können . Es gibt einen deterministischen Algorithmus von Han , der in wird. Für randomisierte Algorithmen sind noch bessere Ergebnisse bekannt, z. B. haben Han und Thorup einen Algorithmus erwartete Zeit gefunden. Ich denke jedoch, dass Ihr Problem keine Sortierung erfordern sollte.

O (n \log n)

$O(n\log n)$

O (\log \log n)

$O(\log\log n)$

O (n \sqrt{\log \log n})

$O(n \sqrt{\log\log n})$

A.Schulz

Antworten:

Hier ist eine Idee für einen einfachen Algorithmus; Zähle einfach alle Vorkommen!

Finden . - Zeit $m = \max A$ $\Theta(n)$
Array " . - Zeit ¹ $C[0..m]$ $O(1)$
Iteriere über und erhöhe um eins, wenn du findest . Wenn war , Add zu einer linearen Liste . - Zeit $A$ $C[x]$ $A[\_]=x$ $C[x]$ $0$ $x$ $L$ $\Theta(n)$
Iteriere über und finde das Element mit gerade. - Zeit . $L$ $x_e$ $C[x_e]$ $O(n)$
Sie . $x_e$

Alles in allem erhalten Sie einen linearen Zeitalgorithmus, der (im Sinne einer Zuweisung) viel Speicher verwenden kann. Beachten Sie, dass es hier entscheidend ist, unabhängig von in konstanter Zeit auf zugreifen zu können . $C$ $m$

Ein zusätzliches , das an den Raum gebunden ist, ist bei diesem Ansatz schwieriger; Ich kenne keine Wörterbuchdatenstruktur, die eine -Zeit-Suche bietet . Sie können Hash-Tabellen verwenden, für die hier Implementierungen mit erwarteter Suchzeit ( der Tabellengröße, der Anzahl der gespeicherten Elemente) vorhanden sind, damit Sie mit linearem Raum beliebig gut werden können - erwartungsgemäß. Wenn alle Werte in demselben Hashwert zugeordnet sind, werden Sie geschraubt. $O(n)$ $O(1)$ $O(1 + k/n)$ $n$ $k$ $A$

In einem RAM erfolgt dies implizit. Alles was wir brauchen ist die Startposition und vielleicht die Endposition.

Raphael
quelle

Eine fast triviale Lösung - die jedoch Leerzeichen verwendet - ist die Verwendung einer Hash-Map. Denken Sie daran, dass eine Hash-Map die Laufzeit zum Hinzufügen und Nachschlagen von Elementen amortisiert hat . $\Theta(n)$ $\mathcal{O}(1)$

Daher können wir den folgenden Algorithmus verwenden:

Ordnen Sie eine Hash-Karte . Iterate über . Erhöhen Sie für jedes Element die Anzahl der beobachteten Vorkommen, dh . $H$ $A$ $i \in A$ $H(i)++$
Durchlaufen Sie den Schlüsselsatz der Hash-Map und überprüfen Sie, welcher der Schlüssel eine gleichmäßige Anzahl von Vorkommen aufweist.

Dies ist ein einfacher Algorithmus, der keinen großen Trick verwendet, aber manchmal reicht sogar dieser aus. Wenn nicht, möchten Sie möglicherweise angeben, welche Speicherplatzbeschränkungen Sie auferlegen.

HdM
quelle

Ich würde immer noch gerne wissen, ob es einen nicht randomisierten -Zeitalgorithmus gibt, der den Polynomraum verwendet. Gibt es insbesondere theoretische Beweise dafür, dass es schwieriger ist, das einzige gerade vorkommende Objekt zu finden, als das einzige ungerade vorkommende Objekt zu finden?

O (n)

$O(n)$

A.Schulz

@ A.Schulz Ich denke, dass es der -erwartete Zeitalgorithmus unter Verwendung der Hash-Tabelle ist. Ich erinnere mich, dass mir jemand einen -Algorithmus (oder für einen speziellen Fall beispielsweise ungerade = 1 und gerade = 2) mit Stapel gesagt hat, aber ich kann mich nicht daran erinnern.

O (n)

$O(n)$

O (n)

$O(n)$

Yai0Phah

Nicht jede Hashtable-Implementierung hat diese Eigenschaft. Normalerweise ist die Suche nicht , nicht einmal amortisiert (afaik). Tatsächlich hat eine vorherige Diskussion keine Implementierung ergeben, die eine konstante Zeitsuche aufweist. Kannst du genauer sein?

O (1)

$O(1)$

Raphael