Alle Zyklen finden

Ich habe eine endliche Menge , eine Funktion und insgesamt um auf . Ich möchte die Anzahl der verschiedenen Zyklen in .$S$$f:S\to S$$<$$S$$S$

Für ein gegebenes Element Ich kann Floyd-Algorithmus (oder Brent, etc.) verwenden , um die Länge des Zyklus zu finden , dass die wiederholte Anwendung von sendet an; Mit etwas mehr Aufwand kann ich diesen Zyklus identifizieren (zB durch sein -minimales Element). Eine schlechte Methode zur Lösung des Problems wäre, jedes Element zu wiederholen, die resultierenden minimalen Elemente zu sortieren, Duplikate zu verwerfen und die Anzahl zurückzugeben. Dies beinhaltet jedoch möglicherweise viele Durchgänge über dieselben Elemente und einen großen Platzbedarf.$s\in S$$f$$s$$<$

Welche Methoden haben eine bessere Zeit- und Raumleistung? Ich bin mir nicht einmal sicher, wie der benötigte Speicherplatz am besten gemessen werden kann. Wenn die Identitätsfunktion ist, verwendet jede Methode, die alle Zyklen speichert, Speicherplatz.$f$$\Omega(n)$

Wenn Sie nur die Anzahl der Zyklen zählen möchten, können Sie dies mit 2 | tun S | Bits (plus Änderung) im Wert von Platz. Es ist unwahrscheinlich, dass Sie viel besser abschneiden können, wenn nicht S oder f nicht besonders bequeme Eigenschaften haben.

Beginnen Sie mit einem Array A, in dem ganze Zahlen {0,1,2} gespeichert sind - eine pro Element von S - auf Null initialisiert; wir werden diese als angeben (unexplored), (partially explored)und (fully explored). Initialisieren Sie einen Zykluszähler auf Null.  Gehen Sie für jedes Element s ∈  S der Reihe nach wie folgt vor:

1. Wenn A [ s ] = (fully explored) , fahren Sie mit Schritt 6 fort.
2. Setze A [ s ] ←  (partially explored)und setze einen Iterator j  ←  f (s) .
3. Während A [ j ] =  (unexplored), setze A [ j ] ←  (partially explored)und setze j  ←  f (j) .
4. Wenn A [ j ] =  (partially explored), haben wir einen neuen Zyklus geschlossen; Erhöhen Sie c um 1. (Wenn Sie einen Vertreter dieses Zyklus aufzeichnen möchten, ist der aktuelle Wert von j eine willkürliche Wahl. Dies ist natürlich nicht unbedingt das minimale Element im Zyklus, das Sie bevorzugen order <.) Andernfalls haben wir A [ j ] =  (fully explored), was bedeutet, dass wir eine vorerkundete Umlaufbahn entdeckt haben, die in einem bereits gezählten Zyklus endet; nicht erhöhen c .
5. Um anzuzeigen, dass die Umlaufbahn, die bei s beginnt, jetzt vollständig erkundet wurde, setzen Sie j  ←  s .
   Während A [ j ] =  (partially explored), setze A [ j ] ←  (fully explored)und setze j  ←  f (j) .
6. Fahren Sie mit dem nächsten Element s  ∈  S fort .

Somit wird jeder Zyklus unter den durch f induzierten Bahnen einmal gezählt; Alle Elemente, die Sie als Repräsentanten aufzeichnen, sind Elemente unterschiedlicher Zyklen. Der Speicherbedarf beträgt 2 | S | für das Array A, O (log | S. |) für die Zykluszahl und andere Gewinnchancen.

Jedes Element s  ∈  S wird mindestens zweimal besucht: einmal, wenn der Wert von A [ s ] von (unexplored)bis geändert wird (partially explored), und einmal für die Änderung von (fully explored). Die Gesamtzahl der Wiederholungen von Knoten nach dem Aufrufen (fully explored)wird oben durch die Anzahl der Versuche begrenzt, neue Zyklen zu finden, die dies nicht tun, dh höchstens | S | - ergibt sich aus der Hauptschleife, die alle Elemente von S durchläuft . Wir können also erwarten, dass dieser Prozess höchstens 3 | umfasst S | Knoten-Durchquerungen, die alle Zeiten zählen, zu denen Knoten besucht oder erneut besucht werden.

Wenn Sie repräsentative Elemente der Zyklen verfolgen möchten und wirklich möchten, dass sie die minimalen Elemente sind, können Sie die Anzahl der Knotenbesuche auf 4 | beschränken S |, wenn Sie in Schritt 4 eine zusätzliche "Runde um den Zyklus" hinzufügen, um einen Vertreter zu finden, der kleiner ist als der, in dem Sie die Schleife schließen. (Wenn die Bahnen unter f bestehen nur aus Zyklen, diese zusätzliche Arbeit vermieden werden könnte, aber das ist nicht wahr willkürlichen f .)

Wenn Sie nur sehr wenige Zyklen haben, finden Sie hier einen Algorithmus, der weniger Speicherplatz benötigt, dessen Beendigung jedoch wesentlich länger dauert.

[Bearbeiten.] meiner vorherigen Laufzeitanalyse wurden die entscheidenden Kosten für die Feststellung, ob die von uns besuchten Knoten zu den zuvor untersuchten gehören, übersehen. Diese Antwort wurde etwas überarbeitet, um dies zu korrigieren.

Wir wieder durchlaufen alle Elemente von S . Während wir die Umlaufbahnen der Elemente s  ∈  S untersuchen , nehmen wir eine Stichprobe von den Knoten, die wir besucht haben, um zu überprüfen, ob wir wieder auf sie stoßen. Wir führen auch eine Liste von Proben von "Komponenten" - Vereinigungen von Umlaufbahnen, die in einem gemeinsamen Zyklus enden (und daher den Zyklen entsprechen) -, die zuvor besucht wurden.

Initialisieren Sie eine leere Liste von Komponenten complist. Jede Komponente wird durch eine Sammlung von Proben dieser Komponente dargestellt. Wir pflegen auch einen Suchbaum, in samplesdem alle Elemente gespeichert sind, die als Beispiele für die eine oder andere Komponente ausgewählt wurden. Sei G eine Folge von ganzen Zahlen bis zu n , für die die Zugehörigkeit durch Berechnung eines booleschen Prädikats effizient bestimmbar ist; Zum Beispiel Potenzen von 2 oder perfekte p- ^te Potenzen für eine ganze Zahl p .  Gehen Sie für jedes s ∈  S wie folgt vor:

1. Wenn s in istsamples aktiviert , fahren Sie mit Schritt 5 fort.
2. Initialisieren Sie eine leere Liste cursample, einen Iterator j  ← f ( s ) und einen Zähler t  ← 1.
3. Während j nicht in ist samples:
   - Wenn t  ∈  G ist , füge j in beide cursampleund ein samples.
   - Inkrementiere t und setze j  ←  f (j) .
4. Überprüfen Sie, ob j in ist cursample. Wenn nicht, sind wir auf eine zuvor untersuchte Komponente gestoßen: Wir überprüfen, zu welcher Komponente j gehört, und fügen alle Elemente von cursamplein das entsprechende Element von ein complist, um sie zu erweitern. Andernfalls sind wir erneut auf ein Element aus der aktuellen Umlaufbahn gestoßen, was bedeutet, dass wir mindestens einmal einen Zyklus durchlaufen haben, ohne auf Vertreter zuvor entdeckter Zyklen zu stoßen: Wir fügen cursampleals Sammlung von Proben einer neu gefundenen Komponente in eincomplist .
5. Fahren Sie mit dem nächsten Element s  ∈  S fort .

Für n  = | S |, sei X (n) eine monoton ansteigende Funktion, die die erwartete Anzahl von Zyklen beschreibt ( z. B.  X (n) =  n ^1/3 ), und sei Y (n) = y (n)  log ( n ) ∈ Ω ( X (n)  log ( n )) ist eine monoton ansteigende Funktion, die ein Ziel für die Speichernutzung bestimmt ( z. B.  y (n) =  n ^1/2 ). Wir benötigen y (n)  ∈ Ω ( X (n) ), da mindestens X (n)  log ( n ) Speicherplatz benötigt wird, um eine Probe von jeder Komponente zu speichern.

• Je mehr Elemente einer Umlaufbahn wir abtasten, desto wahrscheinlicher ist es, dass wir am Ende einer Umlaufbahn schnell eine Probe im Zyklus auswählen und dadurch diesen Zyklus schnell erkennen. Aus asymptotischer Sicht ist es dann sinnvoll, so viele Abtastwerte zu erhalten, wie unsere Speichergrenzen zulassen: Wir können G genauso gut so einstellen , dass ein erwartetes y (n) -Element vorliegt, das kleiner als n ist .
  - Wenn erwartet wird, dass die maximale Länge einer Umlaufbahn in S L ist , können wir G die ganzzahligen Vielfachen von L  /  y (n) sein lassen .
  - Wenn es keine erwartete Länge gibt, können wir einfach alle n  /  y (n) einmal probieren.Elemente; Dies ist in jedem Fall eine Obergrenze für die Intervalle zwischen den Proben.

• Wenn wir bei der Suche nach einer neuen Komponente beginnen, Elemente von S zu durchlaufen, die wir zuvor besucht haben (entweder von einer neuen Komponente, die entdeckt wurde, oder von einer alten, deren Endzyklus bereits gefunden wurde), dauert es höchstens n  /  y ( n) Iterationen, um auf ein zuvor abgetastetes Element zu stoßen; Dies ist dann eine Obergrenze für die Häufigkeit, mit der wir bei jedem Versuch, eine neue Komponente zu finden, redundante Knoten durchlaufen. Da wir n solche Versuche machen, werden wir dann Elemente von S insgesamt höchstens n ²  /  y (n) Mal redundant besuchen .

• Die zum Testen der Mitgliedschaft erforderliche Arbeit samplesist O ( y (n)  log  y (n) ), die wir bei jedem Besuch wiederholen: Die kumulierten Kosten dieser Überprüfung betragen O ( n ²  log  y (n) ). Es gibt auch die Kosten für das Hinzufügen der Proben zu ihren jeweiligen Sammlungen, die kumulativ O ( y (n)  log  y (n) ) sind. Schließlich müssen wir jedes Mal, wenn wir auf eine zuvor entdeckte Komponente stoßen, bis zu X (n)  log *  y (n) Zeit aufwenden, um zu bestimmen, welche Komponente wir wiederentdeckt haben. Da dies bis zu n Mal vorkommen kann, ist die kumulative Arbeit durch n X (n)  log  y (n) begrenzt .

Somit dominiert die kumulative Arbeit bei der Überprüfung, ob die von uns besuchten Knoten zu den Stichproben gehören, die Laufzeit: Dies kostet O ( n ²  log  y (n) ). Dann sollten wir y (n) so klein wie möglich machen, dh O ( X (n)) ).

Somit kann man die Anzahl der Zyklen (die der Anzahl der Komponenten entspricht, die in diesen Zyklen enden) im Raum O ( X (n)  log ( n )) aufzählen, wobei O ( n ²  log  X (n) ) genommen wird. Zeit dafür, wobei X (n) die erwartete Anzahl von Zyklen ist.

$s$$s$$f(s)$