Laufzeit der Tiefensuche |
| 27.05.2008, 21:40 | Akteur | Auf diesen Beitrag antworten » | ||
| Laufzeit der Tiefensuche ich wollte wissen , ob die Laufzeit der Tiefensuche (und auch der Breitensuche) Exponentialzeitzeit hat oder nicht. Ich habe zwar schon selber versucht zu suchen, doch das Ergebnis nach etlichen Stunden mit Google und Brockhaus hat mich nicht wirklich weitergebracht. Also bei den meisten Texten steht diese Laufzeit: O(|V|+|E|) Nun ist das Problem jetzt, dass ich irgendwo gelesen habe, dass die Notation nicht auf die Exponentialzeit hindeutet, doch für mich sieht es doch ziemlich linear aus. Also schon mal Danke für die Antwort. |
||||
| 27.05.2008, 21:43 | Dual Space | Auf diesen Beitrag antworten » | ||
RE: Laufzeit der Tiefensuche
Was ist |V|? Was ist |E|? |
||||
| 27.05.2008, 22:39 | Akteur | Auf diesen Beitrag antworten » | ||
V ist die Anzahl der Knoten und E ist die Anzahl der Ecken des Graphen. |
||||
| 28.05.2008, 18:09 | sdf | Auf diesen Beitrag antworten » | ||
| RE: Laufzeit der Tiefensuche ich bin nicht wirklich fit in dem thema, aber mal rein vom trial-n-error prinzip: deine formel zugrunde gelegt: wenn du 5 knoten hast, hast du 4 kanten = O(5+4) = O(9) wenn du 10 knoten hast, hast du 9 kanten = O(10 + 9) = O(19) wenn du 20 knoten hast, hast du 19 kanten = O(20+19) = O(39) sieht mir dann nach ~O(2n) aus, wobei n die knotenanzahl ist, also nicht exponentiel |
||||
| 19.08.2010, 03:02 | sorcen | Auf diesen Beitrag antworten » | ||
Ist Linear O(n) wobei n die anzahl an Knoten ist (|V|). Lässt sich einfach mathematisch Bewiesen. Maximale Anzahl Kanten in einem ungerichteten Graphen ohne self-loops und parallele Kanten (also keine Kante (u,u) erlaubt und jede Kante (u,v) kann nur einmal vorkommen) ist "Anzahl Knoten" - 1 (n-1) -> O(|V|+|E|) = O(n + n -1) = O(2n) = O(n) |
||||
| 22.12.2016, 15:41 | Kantenzahl | Auf diesen Beitrag antworten » | ||
| Kantenzahl Die Kantenzahl ist nicht beschränkt durch n-1. In jedem Kreis sind schon n Kanten enthalten. Maximal hat jder Knoten eine Kante zu jedem Knoten, also n-1 + n-2 + n-3 + ... + n-(n-1) Kanten, also (n^2-n)/2, also O(n^2) Kanten. |
||||
| Anzeige | ||||
|
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
