LCA N-ary Tree
-
Und was machst du bei der nächsten Anfrage?
-
Vorher den Zähler wieder auf 0 setzen.
Oder meinst Du im allgemeinen Fall, wenn ich einfach Markierbarkeit annehme? Dann führ ich noch eine Liste mit in die alle Knoten kommen, deren Markierung ich zurücksetzen muss und tue das nach der Anfrage. Oder ich verwende als Markierung gleich einen Timestamp, den ich vor jeder Anfrage erhöhe, dann muss ich nicht demarkieren.
Beantwortet irgendwas davon Deine Frage?
-
Jester schrieb:
Oder meinst Du im allgemeinen Fall, wenn ich einfach Markierbarkeit annehme? Dann führ ich noch eine Liste mit in die alle Knoten kommen, deren Markierung ich zurücksetzen muss und tue das nach der Anfrage. Oder ich verwende als Markierung gleich einen Timestamp, den ich vor jeder Anfrage erhöhe, dann muss ich nicht demarkieren.
Beantwortet irgendwas davon Deine Frage?
Ja, das wollte ich wissen. Aber dann ist die Markierung doch nicht mehr O(1).
-
Wieso sollte das Markieren dadurch nicht mehr O(1) sein?
ps: Man muss auch nichtmal eine Liste mitführen.
Man kann den ganzen Vorgang auch einfach wiederholen, und statt Nodes zu markieren die Markierung dabei wieder entfernen bis man die (dann ja bereits bekannte) LCA Node findet.
Dadurch verdoppelt man den Aufwand genau. Was aber an der Komplexität nichts ändert.
-
SeppJ schrieb:
Ja, das wollte ich wissen. Aber dann ist die Markierung doch nicht mehr O(1).
Für jeden Knoten den ich markiere fällt folgender Aufwand an:
- O(1) für markieren
- O(1) für Einfügen in Aufräumliste
- O(1) für Rücksitzen der Markierung am Ende
- O(1) für entfernen aus der Aufräumlistemacht insgesamt O(1) pro Knoten den ich irgendwann mal markiere. Natürlich nicht alles auf einmal sondern halt ein bisschen über die Laufzeit verteilt (amortisiert). Ich fasse ja am Schluss beim Rücksetzen nur Knoten an, die ich ohnehin vorher schonmal angefasst habe. Und das waren nur so viele wie eben erlaubt.
-
Jester schrieb:
SeppJ schrieb:
Ja, das wollte ich wissen. Aber dann ist die Markierung doch nicht mehr O(1).
Für jeden Knoten den ich markiere fällt folgender Aufwand an:
- O(1) für markieren
- O(1) für Einfügen in Aufräumliste
- O(1) für Rücksitzen der Markierung am Ende
- O(1) für entfernen aus der AufräumlisteAhh, so war das mit der Liste gemeint. Da hatte ich dich nicht richtig verstanden.
