Plane-Sweeping
lima-city → Forum → Programmiersprachen → Sonstige Programmiersprachen
algorithmus
beachten
brauch
element
frage
genauen sinn
geometrischen problemen
http
information
jemand
log
machen
sortierte liste
sortierung
steig
untergrenze
url
vortrag
ziel
zusatzinformation
-
Hi,
ich wollte fragen ob mir jemand den genauen Sinn, also das Ziel dieses Verfahrens und die detaillierte Funktionsweise erklären kann?
Ich hab einmal dazu diesen Wikipediaeintrag durchgelesen und in meinem Informatikduden die Seiten dazu gelesen allerdings steig ich irgendwie nicht richtig dahinter!
http://de.wikipedia.org/wiki/Sweep_(Informatik)
deshalb dachte ich mir vllt versteht es jemand von euch besser und kann es mir erklären.
(Ich brauch dies, da ich ein Vortrag dazu halten soll, dies kann ich allerdings nur wenn ich es überhaupt verstehe)
Thx before -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Die sweep-line oder plane algorithmen werden meistens bei Geometrischen Problemen genutzt.
Man Sortiert die Elemente und durchläuft dann die sortierte Liste.
Dabei macht man sich zusätzliche Informationen zunutze, die durch die Sortierung bekannt sind.
Durch diese Zusatzinformationen ist dann die Laufzeitkomplexität meistens besser.
Allerdings muss man beachten, dass es durch die Sortierung eine Untergrenze gibt.
Wenn man also eine vorherige Sortierung benötigt hat das Verfahren im Allgemeinen die Best-Case Laufzeitkomplexität O(n log n),
da dies die Best-Case Laufzeit von allgemeinen Sortierverfahren ist. -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage